当前位置： 移动技术网 > IT编程>开发语言>Java > JDK8 HashMap源码分析

JDK8 HashMap源码分析

2020年07月31日  | 移动技术网IT编程  | 我要评论

本文是对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

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网