HashMap底层原理实现
1.HashMap初始化
jdk1.8版本之后：数组+链表+红黑树实现，先去观看HashMap的构造方法：
-
构造方法：
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }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中的字段值是很重要的。
this.loadFactor = DEFAULT_LOAD_FACTOR;- DEFAULT_LOAD_FACTOR = 0.75f，这个字段表示负载因子的默认大小为0.75，至于为什么这么设计，需要理解容量和阈值之后再去回过头思考这个问题
final float loadFactor;- loadFactor 这个字段用来保存负载因子的大小
而第二个构造函数其实底层调用了第三个构造函数，第一个字段
initialCapacity和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中没有容量这个字段去保存,因此有了另一个字段去保存相应的内容,这个字段就叫
阈值,我是这么理解的,其实用阈值,而其中调用的tableSizeFor方法是一个用于容量辅助的计算方法,这个方法会将传入的容量进行相应的调整,调整成2的幂次方,至于为什么让HashMap容量成为2的幂次方,后面再做理解.先来看tableSizeFor这个方法的内部实现: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; }乍一看这个辅助方法有点眼花缭乱,其实其中几行很有规律,就拿:n |= n >>> 1举例,实际上就是进行移位操作并进行或运算,这段流程用一个具体的实例便可理解:
例如cap = 12:
n |= n >>> 1;: 这一步进行右移1位并进行或运算。计算过程如下：n = 1011 n >>> 1 = 0101 n |= (n >>> 1) = 1111最终的
n变成了1111，表示最高位之后的所有位都被设置为1。然而其实后面的移位操作就没有什么意义了(这里指的是12这个数,如果这个数依旧很大,那可能需要进行后面的移位操作).所以后面无论是移位2,4,8,16最后的结果都是1111,这个结果其实并不是2的幂次方,因此在结果返回是会+1,就保证了结果的返回是2的幂次方.
至于为什么要移位1~16次,其实很容易理解,1+2+4+8+16 = 32,就是一个int类型的整数,而传入的cap就是一个int类型的,因为这个数值并不确定,而为了找到一个最适合的2的幂次数作为容器的值返回,因此需要将整个过程完成,而又因为这个过程其实是逻辑运算,耗时很短很短,所以极其适合.
至此会返回一个合适的容量赋值给阈值.
2.HashMap的数据单元
无论是数组,链表,还是红黑树都需要有相应的结构去表示,因此在HashMap中,数组和链表统一用Node结构去表示,红黑树用TreeNode结构去表示,具体如下:
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
至于内部结构封装的相应方法,没有具体展示,其了解内部封装的内容单元才是重要的,至于数组怎么去用Node表示,在HashMap中被统一成为bucket也就是桶的意思,通过将节点数组化的方式实现:
transient Node<K,V>[] table;
3.HashMap的put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
就是加入键值对时会先计算键的hash值,hash方法的底层是调用hashcode方法,那是一个native方法,获得键的hash值后就通过putVal方法进行赋值操作:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
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);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
代码看起来挺长的,核心思想就是将键值对放入正确的内存单元,只不过其中的实现复杂一些,一步一步看就行
-
设置
Node<K,V>[] tab; Node<K,V> p; int n, i;,tab表示指向数组的引用,而p则表示point也就是指针的作用,期每个节点,即链表的引用.至于n,i,阅读后面代码即可理解 -
if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;用来判断
bucker是不是为空,如果为空的话就利用resize方法进行初始化,同时返回相应的长度,用变量n保存,所以n的作用就是这个 -
if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);- 这个地方挺重要的,重要的点有两个,第一个就是
tab[i = (n - 1) & hash]这个运算方法,也就是为什么数组容量需要定2的幂次方的原因,本质上就是为了计算hash值更方便,通常来说用哈希值计算出来的通常是数组的索引下标,而在数据结构中,我们会采用数组长度求余的方式去计算索引,也就是hash%length,为了性能上更优选择hash & (n-1),为什么这两种方式计算出的结果相等,求余其实对应二进制运算也就是对最高位后面范围的运算,这么说可能不准确,比如十进制数16,转换成二进制10000,但是对于15来说即使1111,而进行&得到的范围一定是0~15,而求余对于16这个结果一定不可能大于15,因此采用&的方法,底层更加高效,而另一方面,这个n也就是数组的容量为什么必须是2的幂次方,如果不是,这个技巧又是否适用其实就很明显了,关键就是2的幂次方他只有一位1,意味着2的幂次方-1也就是处最高位都是1,也就是余数的可表示范围,这种位运算的技巧性确实很高,因此容量才设置为2的幂次方,就是这个原因. - 另一个原因比较简单,p引用其实指向了第一个需要判断的内存单元,如果第一个内存单元为空,则为他申请一个内存单元,其实也就是类似于头元素节点的一个东西,,也就是说
bucker类似于头节点,而内部的next指向了第一个内存单元也就是头元素.然后这个头元素会赋值给相应的键值队.
- 这个地方挺重要的,重要的点有两个,第一个就是
-
else之后就是正常的执行了,
Node<K,V> e; K k,这也很容易理解,e全称element元素的意思,也就是要添加的节点的意思,k也就是键的意思.如果走到这里,说明存在hash冲突了其实,需要添加节点,因此需要键和新加的节点.if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p;- 判断hash值是否相同,如果相同再进行接下来的判断
- ((k = p.key) == key || (key != null && key.equals(k)))) 这一行代码其实逻辑很明显,左边判断是否为同一个引用对象,右边其实也是做这么一个事,不过是判断内部的值是否相同,且判了空,只要有一方成立,就说明找到了键相同的,则让当前e的引用立刻指向此节点,说明此节点的键已存在.
-
在之后就是对节点进行判断,判断此节点是否为红黑树节点,如果是红黑树节点,就用红黑树的查找方法
else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); -
如果不是红黑树的节点,那说明还是链表节点,那就通过遍历的方式去查找相应的节点
else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } }其中有一部分的代码逻辑之前就已经理解过,唯一多的变化就是,如果发现并没有找到相等的key,同时也已经遍历到节点的末尾,则需要一个新的节点,并存放相应的key,value(这里采用的是尾插,同时需要判断链表的节点数如果大于8,那么就调用
treeifyBin方法对链表进行转换).并且break,任务完成 -
而最后一个if条件判断,其实就是为了擦屁股用的,用来处理找到键的情况,对键的值进行替换
if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; }因此HashMap允许插入重复的键,只不过插入之后会替换旧的值
-
之后的操作就是记录修改操作的次数,然后让当前哈希表的元素和阈值比较,用来判断是否需要进行扩容
++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict);
4.HashMap的resize方法
这个方法其实可以用来初始化和扩容,具体的代码实现如下:
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
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
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@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;
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 { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
这个代码看起来依然很长,但其实理解其中的几个声明字段就好
-
声明旧容量,旧阈值,新容量,新阈值
Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0;因为HashMap在进行初始化的时候阈值是设定过的,其实本身容量并没有设定好
-
对旧表的容量进行判断,检查是否需要扩容
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 }如果旧容量大于0,则去判断容量是否超过
MAXIMUM_CAPACITY,如果超过,则将阈值设定为MAX,表示其实已经到极限了,不需要再扩容了,原封不同的返回哈希表就行.下面的else if语句的意思也很直白,就是去判断一下旧容量是否超过
DEFAULT_INITIAL_CAPACITY,这个值也是一个字段,默认16,如果超过,那么就将旧容量扩大两倍赋值给新容量. -
对旧表的阈值进行判断,其实就是判断阈值是否有过初始化
else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr;将阈值赋值给新容量,也就实现了通过阈值赋值给容量,因此在初始化的时候,选择对阈值进行赋值,同样容量也会拿到和阈值一样的值就是这个原因(前提是旧容量等于0,也就是说明这是第一次初始化)
-
走到这,其实也就是空表了说明
else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); }将新容量默认为16赋值,将新阈值赋值给负载因子默认容量,也就是16*0.75 = 12,因此阈值其实就如同一个水阀的门限一样,超过这个门限说明,里面的水很多了(元素很多),因此很多人说负载因子是用来表示密集程度的一个变量.
-
其实这个方法..是因为无参构造(我是这么认为的),所以他需要来判断一下用户有没有进行初始化.
if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); }如果用户采用的无参构造,其实这段代码的实现和有参构造的内部实现逻辑基本是相同的,也就是新阈值最后也会是12.这段代码其实个人认为..多余,因为在前面的if,else语句已经对无参有参进行了判断,所以这段代码应该是旧代码的历史写法.
-
之后就是关于旧表如果不是空表采取的手段了,也就是对表进行扩容.
if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; 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 { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } }-
现在来看第一段逻辑:
Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e;这里声明了节点的一个引用对象e,和前面如出一辙,然后指向这个头元素,看看头元素内部是否有元素,如果有,则让旧表滞空,方便GC去回收,同时去判断这个头元素节点是否有后继节点,没有的话说明这个散列地址只有一个元素,于是就迁移这一个元素就ok了.
-
判断是否为红黑树节点
else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);如果是红黑树节点,就采用红黑树的解决办法去解决.
-
除此之外,说明此hash值的地方存了一个长条子,也就是一个链表
else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); ///// }根据大致条件划分,lohead和loTail很明显是一组链表,而hiHead和hiTail是另一组链表,将节点重新分配的方式,分配的方式就是根据节点的那个hash值和旧容量进行与运算.
这里我一直有一个疑问:竟然是放在一个链表上的节点,就意味着发生了哈希冲突,那他们的哈希值不应该是一样的,重复进行与运算得到的结果会有什么变化?
答案就是:因为扩容的原因,即数组下标的索引范围长度其实也扩大了,导致hash冲突的可能变小了,因此需要重新散列,重新分配位置,就是这个原因.
-
而while之后的操作就是让链表与table进行互连
if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }head对应头,tail对应尾,而头尾之间则是我们重新存放的节点.而这里分为两组链表其实也挺重要的,一组链表其实对应的是原封不动的位置,另一组则是扩容后的重新位置,至于为什么另一组都是一个位置,这个其实需要思考,因为之前的索引位置是根据旧容量去计算(求余),那如今范围变大了,这个数为什么一定加上旧容量,原因就是这种数的关系之间存在某种关系,例如:
假设旧容量
oldCap是 8，对应的二进制是1000。新容量newCap是 16，对应的二进制是10000。考虑一个哈希值为 5 的节点，对应的二进制是
0101。- 在旧数组中，
hash & (oldCap - 1)的结果是0101 & 0111，等于 5，这个节点在索引位置 5 处。 - 在新数组中，
hash & (newCap - 1)的结果是0101 & 01111，等于 5，这个节点在索引位置 5 处。
考虑一个哈希值为 13 的节点，对应的二进制是
1101。- 在旧数组中，
hash & (oldCap - 1)的结果是1101 & 0111，等于 5，这个节点在索引位置 5 处。 - 在新数组中，
hash & (newCap - 1)的结果是1101 & 01111，等于 13，这个节点在索引位置 13 处（旧索引位置 5 加上oldCap）。
换言之如果哈希值为21的节点,其实在未扩容前他也是索引为5的位置,在扩容之后就可以是13的位置,其原因就是因为旧容量限制了他,所以要补偿给他.
- 在旧数组中，
-
5.HashMap的get方法
get这个方法相比之前来说无疑简单太多
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
同样会去计算hash,然后调用getNode方法
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
其大部分的实现逻辑就是,声明一个tab引用和first引用,判断数组是否为空,有没有元素,然后去检查第一个元素,从第一个元素的引用和值去判断是不是你所需要的那个节点,如果是就返回,如果不是,在判断下一个节点是不是红黑树节点,是则通过红黑树的方法去获取,不是则通过链表遍历的方式去拿到节点.如果都没有,说明没这个键值队.