Java HashMap源码学习

一 HashMap介绍

1. HashMap存储key-value键值对；
2. 关键参数
   • capacity：哈希表中桶的个数
   • loadFactor：加载因子，表示哈希表可以多满。数目大于capacity*loadFactor时，2倍扩容rehash；
3. 实现
   • jdk1.7：数组+链表

   • jdk1.8：数组+链表/红黑树（链表长于8时变为红黑树,红黑树小时变为链表）

     
     

二 HashMap主要函数实现

1）put

• jdk1.7 添加节点时，插入链表头部；

    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
  
        createEntry(hash, key, value, bucketIndex);
    }
  

• jdk1.8 链表添加节点时，插入链表尾部；

  Node<K,V> e; K k;
  // 节点key存在，直接覆盖value
  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);
            //链表长度大于8转换为红黑树进行处理
            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                treeifyBin(tab, hash);
            break;
        }
        // key已经存在直接覆盖value
        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;
  }
  

2）扩容

• jdk1.7：对于每个key-value重新哈希计算位置，注意插入链表头部，链表被反转；

    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }
  

jdk1.7扩容例图.png

• JDK1.8：计算哈希位置优化
  由于是2倍扩容，只需要考虑对应增长的这一位是0还是1,如果是0桶的位置不变化，如果是1桶的位置+oldCapcity；
  因此不需要每一个重新计算哈希值

  
  
  

  final Node<K,V>[] resize() {
  ... 
        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) { // 桶index不变化
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {                        // 桶index变化
                                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;
    }
  

3）安全性问题

1. JDK1.7实现，多线程重哈希会导致循环链表问题。 疫苗：JAVA HASHMAP的死循环
   原因在于：rehash时，node节点会插入链表头部

   do {
     Entry<K,V> next = e.next; // <--假设线程一执行到这里就被调度挂起了
     int i = indexFor(e.hash, newCapacity);
     e.next = newTable[i];
     newTable[i] = e;
     e = next;
   } while (e != null);
   

   线程2执行完毕后效果：

   
   
   

   线程1恢复继续执行，产生循环链表；

   
   

2. JDK1.8实现，我认为不会出现循环链表的问题，多线程不安全是肯定的；
   JDK1.8桶中链表的顺序会维持，因此不会出现1.7中后节点移到前节点的前边，循环链表的风险。

     //某个桶里的链表处理过程：
       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;
       }
   

参考：Java 8系列之重新认识HashMap

---

@梦工厂 2018.3.20