HashMap 1.8 较 1.7 的改变

核心变化

1. hash 算法优化
2. 链表插入改为尾插法
3. 引入红黑树

hash 算法优化

旨在提升hash计算性能

• JDK1.7 扰动9次
• JDK1.8 扰动2次

        //  1.7
        h ^= k.hashCode();
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    
        // 1.8 
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

链表插入改为尾插法

避免了多线程下链表成环问题

       // 1.7
       Entry<K,V> e = table[bucketIndex];
       table[bucketIndex] = new Entry<>(hash, key, value, e);

       // 1.8
      for (int binCount = 0; ; ++binCount) {
           if ((e = p.next) == null) {
                p.next = newNode(hash, key, value, null);
                ....
           }
            ...
      }

引入红黑树

在极端情况下，碰撞个数达到8时使用红黑树，查询效率从链表的 O(N) 优化为 O(logN)

                  if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) 
                            treeifyBin(tab, hash);      // 构造红黑树
                        break;
                    }