JDK8 HashMap源码分析

本文是对JDK8下HashMap 进行分析，涉及了默认长长度，数据如何存，如何取， 达到长度后如何扩容。以及对应数组元素下边何时用链表，何时用tree， 以及链表和数组的相互转换，以及数据如何从旧map到新map。

1. 创建HashMap:

1.  
2. public static void main(String[] args) {  
3.           
4.         @SuppressWarnings("unchecked")  
5.         Map<String, String> m = new HashMap();  // 从这里入手
6.           
7.           
8.         m.put("a", "a");          
9.         m.put("b", "b");  
10.           
11.         String v = m.get("a");  
12.           
13.         for(int i = 0; i < 20; i++)  
14.         {  
15.             m.put(""+i, ""+i);            
16.         }  
17. }  

可以看到 new HashMap();

里什么都没有做，只是把负载因子设置成0.75。后边说这个因子的作用。

 

 

2 .添加元素

1. m.put("a", "a");      
2.  
3. 可以看到，这个函数是Map接口中的方法，我们应该看HashMap中的实现

 

我们应该看HashMap中的 put()实现:

从上图中可以看到，put() 调用了putVal()函数。参数中携带了k,v,hashcode值。

当第一个元素添加到map里，是没有空间的，通过resize()函数分配了一个长度为16， 负载因子为0.75的数组。

然后通过  “(n-1)&hash”   【n为数组的size】来计算当前k,v对应该放到数组的哪个位置。

这样一个元素就放到map中了，下次取的时候用同样的规则来找。

 

3. 访问元素

可以看到在用key算出hash后，能找到在数组中的位置，然后看一下是不是只一个元素，如果不是就继续往下找，要么是在链表中找，要么是从树中找。二选一。

 

4.  什么时候数组中的元素后边会跟一条链表和树呢

这就要看下在添加元素的时个数组的size变化时是怎么调整的。重新回到上边put()函数

由于画图有点太慢，我直接把代码加了注释。

可以看到添加元素时：

4.1）首先是根据hashcode找到数组对应的下标。

4.2）如果下标中没有元素，直接new一个node放进去。

4.3） 如果下标中有一个元素，先保存这个节点地址。

4.4）如果下标中有一个treeNode,  顺着root往下找，找到了就保存Node地址，没有找到在tree后边加一个node, 返回来null.

4.5） 如果下标中后有一个链表，也顺着往下找，找到了就保存地址，没有找到new一个node保存k,v.

           4.5.1）这个时候要看一下链表是不是太长，数组是不是不够长。根据相应的规则考虑是把数组扩容还是要变成tree的数据  结构。如果是扩容，那就要涉及到数据搬移。

4.6）前边不是在原map找到节点了吗，还没有修改数据，现在把旧值改成新值。

4.7）再次判断数组的长度有没有超过0.75 *总长， 超了就要扩容，涉及到重新分配数组，把数据搬移过去。

1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {  
2.          Node<K,V>[] tab; Node<K,V> p; int n, i;  
3.          if ((tab = table) == null || (n = tab.length) == 0)  
4.              n = (tab = resize()).length;  
5.          if ((p = tab[i = (n - 1) & hash]) == null)  
6.              tab[i] = newNode(hash, key, value, null);  
7.          else {  
8.              Node<K,V> e; K k;  
9.              if (p.hash == hash &&  
10.                  ((k = p.key) == key || (key != null && key.equals(k))))  
11.                  e = p; // 根节点是我们要找的，把这个节点地址存到 e 中  
12.              else if (p instanceof TreeNode)  
13.                  e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 从tree中找，如果找到了，也保存节点的地址。 如果没有找到，会new一个treeNode, k,v存在其中后，return 回来是Null.  
14.              else {  
15.                  for (int binCount = 0; ; ++binCount) {            // 链表：；   
16.                      if ((e = p.next) == null) {  
17.                          p.next = newNode(hash, key, value, null); // 如果 找到最后，把数据加到最后。  
18.                          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
19.                              treeifyBin(tab, hash);             // 如果链表往下找的次数>= 8了，这个时候 要调整一下。 如果达到了变成tree的标准（64）就转成tree, 如果没有就resize: 扩容，搬移  
20.                          break;  
21.                      }  
22.                      if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) // 如果找到了，就是e节点  
23.                          break;  
24.                      p = e;  
25.                  }  
26.              }  
27.              if (e != null) { // existing mapping for key    
28.                  V oldValue = e.value;                    // 前边如果在原map中找到这个key的节点就，修改value即可。  
29.                  if (!onlyIfAbsent || oldValue == null)  
30.                      e.value = value;  
31.                  afterNodeAccess(e);  // 空函数，应该是为以后扩展用的  
32.                  return oldValue;  
33.              }  
34.          }  
35.          ++modCount;  
36.          if (++size > threshold)  
37.              resize();               // 这个很重要：当超过门限值后，就会重新调整结构： ？？  
38.          afterNodeInsertion(evict);  // 空函数，应该是为以后扩展用的  
39.          return null;  
40.     }  
41.       

 

5.  看下何时会把链表转成tree

     可以看到，当数组的长度<64且链表的长度 > 8时就要扩容。

如果链表>8了，且数组元素>=64了这个时候就要把链表转成tree格式 了

转tree的时候 ，先是转成treeNode链表，然后再转成tree.

1.     final void treeifyBin(Node<K,V>[] tab, int hash) {  
2.         int n, index; Node<K,V> e;  
3.        // 链表的len > 8， 且map的Len < 64时，直接resize. 64 是变成tree的最小门限。
4.         if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)   
5.             resize();  
6.  
7.       // 意思就是当链表中的个数 >8， 且map的长度达到了64 就转到tree.
8.         else if ((e = tab[index = (n - 1) & hash]) != null) {      
9.             TreeNode<K,V> hd = null, tl = null;  
10.             do {  
11.                 TreeNode<K,V> p = replacementTreeNode(e, null);  
12.                 if (tl == null)  
13.                     hd = p;  
14.                 else {  
15.                     p.prev = tl;  
16.                     tl.next = p;  
17.                 }  
18.                 tl = p;  
19.             } while ((e = e.next) != null); // do while里把所有的链表节点变成tree结点。  
20.             if ((tab[index] = hd) != null)  // 把treeNode 构成的链表转成真正的tree  
21.                 hd.treeify(tab);  
22.         }  
23.     }  
24.       
25.       

 

6.  看下扩容是如何扩容的     

扩容的时候是先把数组*2, 门限*2, 然后把老数组中数据用新的Hash 映射到新的数组中，

如果是链表放在  indexOld + oldCapacity 中。 如果是tree放到 indexOld中。  

  /** 

1.      * Initializes or doubles table size.  If null, allocates in 
2.      * accord with initial capacity target held in field threshold. 
3.      * Otherwise, because we are using power-of-two expansion, the 
4.      * elements from each bin must either stay at same index, or move 
5.      * with a power of two offset in the new table. 
6.      * 
7.      * @return the table 
8.      */  
9.     final Node<K,V>[] resize() {  
10.         Node<K,V>[] oldTab = table;  
11.         int oldCap = (oldTab == null) ? 0 : oldTab.length;  
12.         int oldThr = threshold;  
13.         int newCap, newThr = 0;  
14.         if (oldCap > 0) {  
15.             if (oldCap >= MAXIMUM_CAPACITY) {  
16.                 threshold = Integer.MAX_VALUE;  
17.                 return oldTab;  
18.             }  
19.             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && // <= 0X40000000 将原来map的长度 *2  
20.                      oldCap >= DEFAULT_INITIAL_CAPACITY)  // >= 16  
21.                 newThr = oldThr << 1; // double threshold        // 将原来门限的值 * 2  
22.         }  
23.         else if (oldThr > 0) // initial capacity was placed in threshold  
24.             newCap = oldThr;  
25.         else {               // zero initial threshold signifies using defaults  
26.             newCap = DEFAULT_INITIAL_CAPACITY;  
27.             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);  
28.         }  
29.         if (newThr == 0) {  
30.             float ft = (float)newCap * loadFactor;  
31.             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?  
32.                       (int)ft : Integer.MAX_VALUE);  
33.         }  
34.         threshold = newThr;  
35.         @SuppressWarnings({"rawtypes","unchecked"})  
36.             Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //这里重新分配了2倍长的数组  
37.         table = newTab;  
38.         if (oldTab != null) {  
39.             for (int j = 0; j < oldCap; ++j) {  
40.                 Node<K,V> e;  
41.                 if ((e = oldTab[j]) != null) {  
42.                     oldTab[j] = null;  
43.                     if (e.next == null)  
44.                         newTab[e.hash & (newCap - 1)] = e; // 如果找到的元素后边没有根链表或者tree,直接把这个元素放到新的map 对应的下标中（下标已经重新算了）  
45.                     else if (e instanceof TreeNode)  
46.                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 如果找到的位置后边有tree, 就把tree 放到j 对应的下标下，如果tree 节点《 6转成链表。  
47.                     else { // preserve order  
48.                         Node<K,V> loHead = null, loTail = null;  
49.                         Node<K,V> hiHead = null, hiTail = null;  
50.                         Node<K,V> next;  
51.                         do {  
52.                             next = e.next;  
53.                             if ((e.hash & oldCap) == 0) {  
54.                                 if (loTail == null)  
55.                                     loHead = e;  
56.                                 else  
57.                                     loTail.next = e;  
58.                                 loTail = e;  
59.                             }  
60.                             else {  
61.                                 if (hiTail == null)  
62.                                     hiHead = e;  
63.                                 else  
64.                                     hiTail.next = e;  
65.                                 hiTail = e;  
66.                             }  
67.                         } while ((e = next) != null);  
68.                         if (loTail != null) {  
69.                             loTail.next = null;  
70.                             newTab[j] = loHead;  
71.                         }  
72.                         if (hiTail != null) {  
73.                             hiTail.next = null;  
74.                             newTab[j + oldCap] = hiHead;  // 如果原来的节点下有链表，就把原来的链表放到新map的  j+oldCap 对应的位置  
75.                         }  
76.                     }  
77.                 }  
78.             }  
79.         }  
80.         return newTab;           // 返回新的map 结构  
81.     }  

 

本文地址：https://blog.csdn.net/coolfishbone_joey/article/details/107696701