内容简介：开局一张图结构图描述
开局一张图
要点
-
Java8对 Java 7的HashMap做了修改，最大的区别就是利用了红黑树。
-
Java7的结构中，查找数据的时候，我们会根据hash值快速定位到数组的具体下标。但是后面是需要通过 链表 去遍历数据，所以查询的速度就依赖于链表的长度，时间复杂度也自然是O(n)
-
为了减少2中出现的问题，在Java8中，当链表的个数大于8的时候，就会把链表转化为红黑树。那么在红黑树查找数据的时候，时间复杂度就变味了O(logN)
结构
结构图
描述
-
数组中存放的是节点。
-
如果是链表，就是Node节点，红黑树的话则是TreeNode节点。
-
在Node节点中，都是keyt,value,hash,next这几个属性，和Java7的基本一样。
-
我们根据存放在数组中的节点的类型，判断是红黑树还是链表
构造方法
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
复制代码
这个构造方法初始化了阈值和负载因子。
在构造方法中，是不会指定HashMap的容量大小的，就算是用 HashMap(int initCapacity) 的构造方法，传入的数运算之后的结果后面只是初始化阈值，并没有马上构建内部的数组，至于初始化内部数组只有第一次put的时候才会执行，初始化阈值是用来方便后面put的时候初始化数组。具体的还得需要读者往下看， 只是说明下内部数组并不是在构造函数执行就已经初始化了。
tableSizeFor
这个函数就是将传进来的数向上取到最接近2的幂次的数(包括等于)。比如传入15，返回则是16；传入18，返回32。传入32，返回32。我们来看看他如何实现吧！
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
复制代码
解释
在解释源码之前我先说一下，传入一个cap，可能它不是2的几次幂，要找到大于等于cap的最小的2的幂
怎么找呢？我们看看开始举的例子(这里先把18-1先，至于这个-1后面会讲)
00000000，00000000， 00000000， 0001 0001 十进制：17
00000000，00000000， 00000000， 0010 0000 十进制：32
再看32-1的二进制是多少，和32和17的对比一下
00000000，00000000， 00000000， 00 10 0000 十进制：32
00000000，00000000， 00000000， 000 1 1111 十进制：31
00000000，00000000， 00000000， 000 1 0001 十进制：17
我们看到只要将17的后面5位全部变为1，那么就成31的二进制，后面再+1就可以变为32，这就达到我们的目的了！一句话说，这个函数的目的就是从 最左边的1开始往右，都要变为1，后面再+1就可以达到我们想要的目的了！
过程
n|=n>>>1
由于n大于0，那么在二进制中高位肯定有一位是1，那么无符号右移1位与自己相或，那么肯定是接近原来数的后面的数变为1.比如10xxxx，那么运算 n|= n>>>1之后，肯定是11xxxx。
n|=n>>>2
在上面的例子中，n已经由10xxxx变为11xxxx了。那么我们们要让后面xxxx继续变为1，此时有两位是1，那么就让xxxx的前两位继续和11相或呗。所以无符号右移两位再与自己相或，就可以从11xxxx变为1111xx了。
那么现在有4个1，那么后面就移4位。变为8个1，就移8位....
依次类推。
如果要把32位变为全1的话，只要先把前16位变为1，那么后面右移16位就可以把32位全部变为1啦。
我们也可以看到，32位的1肯定是超过MAXIMUM_CAPACITY(1<<30),那么后面结果就会变为MAXIMUM_CAPACITY啦。
给大家看个图把，或许会更加清楚(用的是别人图)。其实上面说得很清楚啦！
概括
这里说下为什么传进来要先减1。有前面我们都知道，
相信上面的解释和例子中你都应该理解吧！ 二进制最左边的1开始往右，都要变为1 。如果传进来的刚好是2的m次幂，那么后面的n的二进制会变为1+上m个1，那返回的时候再+1的话，就变为1加上m+1个0了。 那么就变为传进来的数字的两倍了 。比如说传进32，二进制为1 00000 ,1后面5个0。后面是n变为1 11111 ，返回的时候+1，那么就返回1 000000 ，对应的十进制就是64了。这显然不符我们的逻辑。
至于其它不是2的几次幂的数，不管减不减1，只要最 左边的那个1位置没变 ，右边不管是什么，到后面都是可以变为大于等于传进来的数的最小的2的幂的。
所以综上，传进来的cap-1，就是为了防止传进来的cap是刚好的2的幂次数，避免后面返回的时候翻倍。
Put
public V put(K key, V value) {
//关于hash函数，后面会说
return putVal(hash(key), key, value, false, true);
}
//---------putVal
//onlyIfAbsent如果为true的表示的是：如果key不存在就存入，存在就不存入
//为false：key存在也存入，只不过会覆盖旧值，然后把旧值返回
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//第一次put，会执行下面的if里面的 resize()
//第一次resize就是相当于初始化， 一般都会设置为16，后面扩容就不一样了。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//假设是第一次扩容，(n-1) & hash 相当于 hash对 n 求模
//这里也就是将hash值对15求模就可以随机得到一个下标啦
//如果这个位置没有值，那么就直接初始化一下Node并且放在hash映射到的位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//这里hash映射的数据已经有节点啦
else {
Node<K,V> e; K k;
//如果第一个节点就是我们想要找的那个节点，那么e就执行这第一个节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果第一个节点是红黑树的根节点的话，就调用红黑树的放入操作，本文不再赘述
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//到这里，就是想要放入的key可能在第一个节点后边或者这个key在链表中也不存在
else {
//这里binCount进行计数，主要是为了记录是否到达8个节点从而进行变形为红黑树
for (int binCount = 0; ; ++binCount) {
//如果到达最后一个节点，也就是这个key不存在的情况
if ((e = p.next) == null) {
//新键节点放在链表的尾节点的后面，此时e已经为null
p.next = newNode(hash, key, value, null);
//如果此时节点已经到达7个，那么加入这个节点就成为8个了，那么就进行转化为红黑树啦
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
//这里有两种情况 1 是成功加入链表尾部，并且总数没超过8 ，2是 加入节点之后，总数到达8，那么就转为红黑树，就退出循环了
break;
}
//put的时候，如果key已经存在在链表中，那么就退出，后面再进行 覆盖 操作
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//这里是一直没找到，遍历链表的操作
p = e;
}
}
//这里e不为null的情况就是put的key已经在之前的链表中，
//为null的话就是不在之前的链表中并且已经加入到之前链表的尾部
if (e != null) {
V oldValue = e.value;
//1 这个onlyIfAbsent之前也说过，为false就可以 覆盖 旧值
//2 或者之前就没有值
//1 或者 2 就执行下面的if
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//这个函数只在LinkedHashMap中用到, 这里是空函数
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//如果增加这个节点之后，超过了阈值，那么就进行扩容
if (++size > threshold)
resize();
//这个函数只在LinkedHashMap中用到, 这里是空函数
afterNodeInsertion(evict);
return null;
}
复制代码
hash方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
复制代码
在java中, hash函数是一个native方法, 这个定义在Object类中, 所以所有的对象都会继承.
public native int hashCode(); 复制代码
因为这是一个本地方法, 所以无法确定它的具体实现, 但是从函数签名上可以看出, 该方法将任意对象映射成一个整型值.调用该方法, 我们就完成了 Object -> int 的映射
在hash的实现中我们看到
-
如果key为null，那么这个值就是放在数组的第一个位置的。
-
如果key不为null，那么就会先去key的hashCode右移16位然后再与自己异或。
大家可能关于第2点有点疑问
其实也就是说，通过让hashcode的高16位和低16位异或，通过高位对低位进行了干扰。目的就是为了让hashcode映射的数组下标更加平均。下面这段是引用论坛的匿名用户的解释，个人觉得解释得很详细
作者：匿名用户
链接： www.zhihu.com/question/20…
来源：知乎
我们创建一个hashmap，其entry数组为默认大小16。 现在有一个key、value的pair需要存储到hashmap里，该key的hashcode是0ABC0000（8个16进制数，共32位），如果不经过hash函数处理这个hashcode，这个pair过会儿将会被存放在entry数组中下标为0处。下标=ABCD0000 & (16-1) = 0。 然后我们又要存储另外一个pair，其key的hashcode是0DEF0000，得到数组下标依然是0。 想必你已经看出来了，这是个实现得很差的hash算法，因为hashcode的1位全集中在前16位了，导致算出来的数组下标一直是0。于是，明明key相差很大的pair，却存放在了同一个链表里，导致以后查询起来比较慢。 hash函数的通过若干次的移位、异或操作，把hashcode的“1位”变得“松散”，比如，经过hash函数处理后，0ABC0000变为A02188B，0DEF0000变为D2AFC70，他们的数组下标不再是清一色的0了。 hash函数具体的做法很简单，你画个图就知道了，无非是让各数位上的值受到其他数位的值的影响。
在源码中我们看到 h&(n-1) 的操作，其实这样是和 h % n 一样的。只不过是一个很大的求模的时候会影响效率，但是通过位运算就快很多啦！
resize
-
resize()用于HashMap的 初始化数组 和 数组扩容 .
-
数组扩容之后，容量都是之前的2倍
-
进行数据迁移
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//如果是初始化，oldTab肯定null，反之就不是null
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//记录之前的阈值
int oldThr = threshold;
//定义新的容量和新的阈值
int newCap, newThr = 0;
//这里说明是进行扩容，因为之前就已经有容量了
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//到这里，前面的容量就已经扩大一倍
//阈值也扩大了一倍
newThr = oldThr << 1; // double threshold
}
//这里调用new HashMap(initCapacity)，第一次put
else if (oldThr > 0)
//指定了容量,比如initCapacity指定了22，那么newCap就是32
newCap = oldThr;
//这里调用new HashMap(),第一次put
else {
//容量就是默认类内部指定的容量，也就是16
newCap = DEFAULT_INITIAL_CAPACITY;
//默认的加载因子是0.75，所以阈值就是16*0.75 = 12
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//这里的情况是 调用了new HashMap(initCapacity)或者
//new HashMap(initCapacity,loadFactor)的情况
//因为上面的两个构造函数都会初始化 loadFactor
//就是根据新的容量初始化新的阈值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//创建新的数组，赋给table,也就是实现了扩容
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//遍历原数组进行数据转移
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//获取对应数组位置的节点，如果为null表示没节点
//否则就转移
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
//这里表示对应的位置只有一个节点，那就直接让
//这个节点对新的数组的长度求模呗
newTab[e.hash & (newCap - 1)] = e;
//如果是红黑树的情况
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
//这里定义了两个链表，lo和hi
//此时 e 就是数组所对应的第一个节点
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//下面这个do-while就是遍历数组当前位置的链表，然后
//根据某些规则，把链表的节点放在扩容后的数组的不同位置
do {
//获取e的下一个节点
next = e.next;
//下面的解释可能有点难懂，待会看下面的解释再看这里即可
//1 如果节点hash运算后是老位置，那么就用lo链表存储
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//2 那么就是新位置，就用hi链表存储
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//这里很简单，lo链表不为空，那么数组的老位置就放lo的头结点
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//hi链表不为空，那么数组的老位置就放hi的头结点
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
复制代码
下面用一张图解释下数据转移的过程。
扩容解释
现在来解释下resize源码中的疑问
大家可能对 (e.hash & oldCap) == 0 这个判断有点迷糊，下面就来解释下。
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
由put方法的这两个语句我们知道，这里是通过 hash和数组的长度-1相与 得到节点映射到数组的哪个位置的。
一：
其实很简单，n就是数组的长度，我们都知道，在HashMap中的数组长度肯定是2的m方。那么n-1在二进制中就是m个全1咯，比如说数组的长度是16，16就是2的4次方，那么16-1 = 15 就是4个全1（2进制） “1111”
-
没扩容前就是用hash（key）之后得到的hash值 与 (n-1)相与 得到位置， 在上面的例子中也就是取出hash值的低4位 ，结果为a。(结果肯定在0-15之间)
-
扩容后，数组变为之前的2倍，那么数组的长度就成为32了，二进制就是100000，那么照葫芦画瓢， 同一个 hash值 与(32-1)相与得到位置。也就是 取出hash值的低5位 ，结果为b。(结果肯定在0-31之间)
二：
由1和2得知， b的二进制比a的二进制多了1位 ，前面4位是相同的。并且在二进制中，不是0就是1。
- 如果多出的1位是0，那么b和a是一样的。比如a 为1001，b是01001，那么a和b是相等的，也就是说 同一个节点在新数组的位置就是旧数组的原来的位置。
- 如果多出的1位是1，那么b比a就是多了2的m次方。比如a 也是1001，十进制是9，b是11001，十进制是25，那么b就比a多了2的4次方，而这个2的4次方刚好就是原来数组的长度oldCap。也就是说 也就是说同一个节点在新数组的位置就是旧数组的原来的位置加上2的4次方(没扩容的数组的长度（oldCap) )。
所以我们得出结论，只要我们可以判断扩容之后b比a多的那一位是1还是0(在例子中也就是第5位)，就可以得出同一个节点在新数组的哪个位置了，一句话总结就是。 数组扩容后，同一个节点要么在原来的位置，要么在原来的位置加上没扩容的数组的长度（oldCap） 。
那么我们如何得到b比a多的那一位到底是啥呢？很简单，就是 用hash值和oldCap相与即可 ！比如说这里的oldCap为16，那么二进制就是1后面加上m个0，也就是10000，也就是第m+1位为1，用hash值与oldCap相与， 就可以得出hash值的第5位是啥啦 ，那么就可以根据前面的"二"去判断节点到底在新数组哪个位置啦。
读者们看到这里，就可以继续回到源码的1处去看，这时候应该就会豁然开朗啦！
扩容总结
扩容时,会将原table中的节点re-hash到新的table中, 但节点在新旧table中的位置存在一定联系: 要么下标相同, 要么相差一个 oldCap (原table的大小).
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
