Java编程之HashMap底层源码方法原理（jdk1.8）

HashMap概述

• HashMap是一个存放键值对的集合，每一个键值对称为Entry；
• HashMap的底层实现依旧是一个数组，每一个存放Entry的位置称为一个bucket(桶)；
• 每个bucket都有一个索引，可以进行索引访问快速找到bucket里的Entry元素；
• 一个bucket只能存放一个Entry，但其可以指向另一个Entry从而形成一个链表；
• 当链表元素个数大于等于8个时，java会将其转化为红黑树存储，加快索引速度；
• 当红黑树元素个数小于等于6个时，java也会将其转回为链表存储，节省空间；

Map家族

我们复习一下map都有哪些实现类：

• HashMap：基于哈希表，无序；
• LinkedHashMap：基于哈希表和链表，有序；
• TreeMap：基于树(红黑树)，可排序，无序；
• HashTable：基于哈希表，无序，线程安全；
• ConcurrentHashMap：基于哈希表，无序，线程安全。

注：以上所说的无序、有序，都是指插入和取出的顺序是否相等，如果相等则是有序的

哈希表

我们发现大部分的Map实现类都是基于哈希表的，那么哈希表又是什么东西？
哈希表也称散列表，将键key根据某种函数计算出的一个结果作为索引位置，并将键值对放到该位置上。如果计算出的索引相同，就形成了哈希冲突/哈希碰撞，则会在原元素上添加形成一个链表，当然这也只是解决哈希冲突的一种方法，称为“拉链法”，也是HashMap所用到的。但ThreadLocal则不然，它采用的是“开放寻址法”，即如果当前索引（假设5）被占用了，则他会往下寻址（6.7.8…等等），直到找到未被占用的索引，并存放元素为止。
哈希表既然用到了索引，则底层实现肯定是一个数组，又知道它是可以存放链表的，所以我们可以将哈希表理解为：一个存放Entry元素或Entry链表的数组。
但是如果哈希表中的某个链表长度过长，则查找速度将会大大降低，为此，java将大于等于8个元素的链表转化为红黑树，加快了查找速度。

哈希表扩容

我们想一想，如果无限地往哈希表中添加元素，每个位置上的链表/红黑树会越来越长，效率也会越来越低，因此，哈希表就对其进行了扩容，那么什么情况下才会扩容呢？
这里用到了增长因子（也叫负载因子），就是已用位置数和总位置数的比值，当达到或超过了这个增长因子，则会将哈希表进行扩容。其次就是增长因子一般情况下是默认的，当然也可以自己指定，但是较为麻烦。

构造方法

任何一个集合的使用，肯定第一步都是创建集合，我们先看无参构造方法：

final float loadFactor; static final float DEFAULT_LOAD_FACTOR = 0.75f; public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } 

这里涉及到两个变量：

• loadFactor：增长因子（负载因子）
• DEFAULT_LOAD_FACTOR：默认负载因子，可以看到是0.75

put()方法（第一次插入）

这里仅仅初始化了负载因子，但数组的默认长度是多少呢？它在构造方法里并没有体现，不妨直接put新增一个元素看看就知道了。

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } 

put()方法参数是一个key和value，即一个键值对，该方法调用了putVal()函数（重点），参数分别是hash(key)、key、value、false、true，我们先来看hash(key)这个函数：

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } 

它将传递进来的key值进行了某种运算：当key不为null时，计算key.hashCode()的值赋给h，然后将h与
h的右移16位做异或运算（相同为0，不同为1），最后将该异或计算结果返回。
实际上hash()函数就是获得一个哈希值，注意这里只是哈希值，并不是数组的索引值。
我们再来看put()中的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数组Node<K,V>[] tab，一个Node元素Node<K,V> p，接下来看第一个判断语句：

if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; 

他将table赋给了tab，即上面定义的Node数组，那这里的table是什么：

transient Node<K,V>[] table; 

可以得知这个table数组就是用来存放HashMap的，即底层最重要的一个数组。
因为第一次调用put()方法时数组肯定是空的，所以满足条件，执行tab = resize()。

resize()方法

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; 

这里我们将table数组赋给了oldTab，并且判断oldTab是否为空，如果为空则将oldCap置为0，否则置为oldTab的长度。
因为这里table是空，所以oldCap为0，继续看源码，if语句分别判断了oldCap大于0、小于0和等于0的情况，我们直接来看等于0的情况：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 static final float DEFAULT_LOAD_FACTOR = 0.75f; else {// zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } threshold = newThr; 

这里看到了DEFAULT字样，心里应该窃喜了，总算被我找到初始化数组在哪了吧。我们看看原先newCap的值0，变成了DEFAULT_INITIAL_CAPACITY，他的值是1右移4位，就是16。
我们知道了一个重要信息，如果创建HashMap时不指定容量大小，即使用无参构造方法，则其数组默认大小是16！
紧接着他又计算了newThr的值，0.75 × 16 = 12，其实这就是数组扩容的临界点，当数组占用数达到12之后便会扩容，并将此计算结果赋给了threshold。
threshold：表示HashMap集合的size大于等于threshold时会执行resize()扩容操作。
继续往下看，会看到这一行代码：

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; 

完美，长度为16的新数组创建完成！并将其赋给了table数组，里面的每一个元素也正是Node<K, V>。到此，resize()函数完成，因为他下面的判断实际是进行扩容操作的，我们一会再来看。resize()函数返回newTab数组。
回过头我们返回putVal()函数继续查看：

if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; 

n的值由0变成了16。这个n的作用是什么？我们继续往下看：

if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); 

让数组容量为2次幂的原因

它计算了一个数组索引值：i = (n - 1) & hash，n是前面算出的16，n-1就是15，对应的二进制是1111，有没有发现他很特殊，其实，无论HashMap的容量如何扩充，它肯定是2的幂次方的，就是为了保证他减1后的二进制数为全1，为什么要把初始容量设为16，也就是这个原因。
那为什么要将其置为全1呢？我们继续来看索引是如何计算的(n - 1) & hash，hash值为前面计算出的hash值作为参数传递而来，还记得他怎么计算得的吗？
(h = key.hashCode()) ^ (h >>> 16)。然后与(n - 1)做按位与运算(相同为1，不同为0)，因为n值是固定的，且hash是随机的，要想让计算出的索引平均分布，则必须将前者置为全1，才能保证算出的索引是平均的。
这里举个例子大家就明白了，假设初始容量n是12，则它二进制是1100，(n - 1)的二进制是1011，这样，无论hash值的第3位是0还是1，(n - 1) & hash计算得出的第三位只能是0，导致某些索引一直为空，浪费空间。
计算出索引值i后，将tab[i]赋给了元素p，并判断该索引位置上是否为空，如果为空（即该索引位置没有元素），则新创建一个Node并存放到该索引上：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) { return new Node<>(hash, key, value, next); } 

这里的Node又是什么？

Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } 

该Node元素存放了hash值，key值，value值，以及next指针，因为是该位置是新插入的元素，故next值为null，其他均是有值的，这时候tab里就有新插入的Node元素了。
完成向数组插入元素后，我们继续往下看：

++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; 

这里modCount进行了自增1，之前在ArrayList中讲过，它是记录预计迭代次数的，在迭代器中会进行判断，详情请看我ArrayList的原创文章。
紧接着判断了当前的size+1是否大于扩容标准，如果大于，则需调用resize()扩容，至于扩容细节，我们待会再提。
afterNodeInsertion()函数与我们无关，透露大家它是为LinkedHashMap服务的，用来回调移除最早放入Map的对象（此方法介绍转自https://segmentfault.com/q/1010000009323139）。
最后put()方法返回的是一个null，为什么是null？因为他是新的，无重复。如果已经存在一个相同的key，再插入一个新的相同key的键值对，则会返回覆盖前的key对应的旧value，同时将新的value覆盖旧value；如果不存在相同的key，则直接返回null。
到此为止，第一次put添加键值对已经完成，数组table已经成功存放了一个键值对

---

get()方法

我们已成功存放了一个元素，那我们现在取一个元素看看，使用get()方法：

• public V get(Object key)：返回到指定键所映射的值，或null如果此映射包含该键的映射。

注：get()方法是根据键key来找，而不是值value或者其他。
我们直接获取key所对应的元素，此key为刚刚插入元素的key，看看底层是如何实现的：

public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } 

首先定义了一个空键值对，然后调用getNode()方法，参数分别为key的hash值和key值，跟进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 = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null
分别判断了当前数组是否为空，当前数组长度是否大于0，当前hash值所计算的索引对应的元素是否为空。如果都不成立，则进入if语句。
进行下一步判断：
first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))
判断当前元素first的哈希值与传递进来的哈希值是否相等，元素对应的key值是否与当前查找的key值相等，key值是否为空，k与当前key做equals()判断是否相等。
总结：判断当前找到索引所对应的元素的key值与我们参数传递的key值是否相等，当前元素的hash值与参数传递进来的hash是否相等，如果都相等则直接返回first元素，否则它将是以链表或红黑树的形式存在，需继续往下移动指针找，继续判断hash值与key值是否相等。

get()方法实现原理

根据key计算哈希值，然后计算索引得出数组下标，判断该下标元素的哈希值是否与当前哈希值相同，如果相同则仍不够，需继续判断改下标元素的key值是否与当前key相同，如果都相同才将value结果返回，如果不满足任一条件，则需根据next指针继续向下查找。

put()方法（第二次插入）

我们上面了解了第一次插入时会默认指定数组容量为16，那么第二次插入元素又是怎样的情况？

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } 

这里跟之前无区别，同样是计算key的哈希值，并传递给putVal()函数处理，其他参数还包括key值和value值。

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; } 

当数组中的元素较少时，发生哈希冲突和需要扩容的概率较低，所以插入元素时几乎与第一次插入元素一样，都是计算索引值，判断该位置是否存在元素。如果存在，则判断该key的hash值与内容是否相同，如果都相同，即意味着需要替换，我们看一下它是如何替换的：

if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } 

这里看到了一个onlyIfAbsent变量，这是方法的参数，我们看上一层的put()方法，传递进来的onlyIfAbsent值为false，故这里会执行if语句，将新的value替代了原先的e.value，最后返回旧的oldValue值。
但是如果在判断该索引位置时，有元素，且第一个元素的key不相等，则需要继续往下查找，指针下移，直到找到相同的key（hash值和内容均相同）或找到尾部仍未找到，则在该链表/红黑树末尾（当然红黑树可能不是末尾，需要根据某种算法算出需要添加的位置）添加该元素，最后返回null。

扩容原理

当我们的数组容量size(类的一个表示数组已用大小的变量)大于或等于threshold(扩容起始点)，就需要对数组扩容，具体的代码看下面：

if (++size > threshold) resize(); 

继续看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; } 

因为当前数组table也就是oldTab(原数组)不为空，因此oldCap(原容量)被赋值为table的容量(长度)，也就是16；
当前oldCap原容量大于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 } 

第一个判断不同管他，因为MAXIMUM_CAPACITY很大，是1右移30位的数值，一般情况下用不到；

每次扩容至原来容量的2倍

第二个判断，将newCap(新容量)赋值为oldCap(原容量)左移1位的数值，即容量扩大1倍，例如原来是16，现在是32。
然后将newThr(新扩容起始点)赋值为oldThr(旧扩容起始点)的2倍，假设原来是12，现在的扩容起始点则是24，也正好是0.75倍的容量(32)。
继续往下看：

threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; 

将新扩容起始点重赋给了成员变量threshold，然后创建了新的Node数组，容量为newCap(新容量32)，并把新创建的newTap数组赋给实际存在的table数组。

重新计算索引

接下来是重点了！！！
以为数组扩容了，所以数组中的元素存放位置肯定有所变化。我们想一下，引起扩容原因是因为数组元素多了，哈希冲突多了，必然会导致某一个位置上的链表或红黑树长度过长，操作数组起来较慢，因此才需要扩容。所以扩容时必然会将重新计算每个元素的索引，还记得计算索引的公式吗？
hash & (length - 1)
因为当前的数组length扩大1倍了，也就是说，length - 1对应的二进制实则多了个1。比如原来是16，对应-1二进制是1111；现在扩大1倍了，长度为32，对应-1二进制是11111。
那么重新计算索引值的元素，存放位置会有什么变化呢？我们再来举个例子：
假设当前key值对应的哈希值是10011101，在扩容前与1111做位与运算，得出1101，对应索引是13；但当扩容后与11111做位于运算，得出11101，对应索引是13 + 16 = 29，可以看出得到的索引如果发生了改变，则必然是原索引+扩容量(32 - 16)。
因此这样一操作，成功将原索引上的部分链表或红黑树中的元素转移到另外一个索引上。

如何实现元素移动

我们有没有想过一个问题，如果该位置上的元素不仅仅是单个元素，而是一个链表或红黑树，那他又是怎样的原理呢？
我们直接看移动元素的代码：

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; } } } } } 

代码仍然较多，但细看后，无非就三种情况：
①该索引上元素是单个元素
②该索引上元素是一个红黑树
③该索引上元素是一个链表
我们先看第一种情况，也是最简单的：

if (e.next == null) newTab[e.hash & (newCap - 1)] = e; 

它判断了当前索引的元素的下一个指向是否为空，如果为空，则表示是单个元素，可直接计算索引值放到新数组newTab中。
第二种情况，对红黑树操作：

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; } } 

本文地址：https://blog.csdn.net/y13672651519/article/details/108017928