HashMap

JDK8 做了哪些优化

HashMap 底层实现原理是什么？JDK8 做了哪些优化？

HashMap类 - 图1

  1. // Node 为单向链表，实现了 Map.Entry<K,V> 接口
  2. static class Node<K,V> implements Map.Entry<K,V> {
  3.     // 组成：Hash值，键值，下个节点
  4.     final int hash;
  5.     final K key;
  6.     V value;
  7.     Node<K,V> next;
  8.     //构造函数Hash值 键 值 下一个节点  
  9.     Node(int hash, K key, V value, Node<K,V> next) {
  10.         this.hash = hash;
  11.         this.key = key;
  12.         this.value = value;
  13.         this.next = next;
  14.     }
  16.     public final K getKey()        { return key; }
  17.     public final V getValue()      { return value; }
  18.     public final String toString() { return key + "=" + value; }
  20.     public final int hashCode() {
  21.         return Objects.hashCode(key) ^ Objects.hashCode(value);
  22.     }
  24.     public final V setValue(V newValue) {
  25.         V oldValue = value;
  26.         value = newValue;
  27.         return oldValue;
  28.     }
  30.     // 进行比较 判断两个Node值是否相等，若两个key和value都相等，返回true。是自身返回true
  31.     public final boolean equals(Object o) {
  32.         if (o == this)
  33.             return true;
  34.         if (o instanceof Map.Entry) {
  35.             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
  36.             if (Objects.equals(key, e.getKey()) &&
  37.                 Objects.equals(value, e.getValue()))
  38.                 return true;
  39.         }
  40.         return false;
  41.     }
  42. }
  • HashMap相关的面试题还有以下几个
    1. JDK1.8HashMap扩容时做了哪些优化？
    2. 加载因子为什么是0.75？
    3. 当有哈希冲突时，HashMap是如何查找并确认元素？
    4. HashMap源码中有哪些重要的方法？
    5. HashMap是如何导致死循环的？
  • HashMap
    ```java // HashMap 初始化长度 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// HashMap 最长长度 static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认加载因子（扩容因子） static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 转换红黑树的临界值，链表长度大于此值时，会将链表转化为红黑树结构。 static final int TREEIFY_THRESHOLD = 8;

// 转换链表的临界值，当元素小于此值时，会将红黑树结构转变为链表 static final int UNTREEIFY_THRESHOLD = 6;

// 最小树容量 static final int MIN_TREEIFY_CAPACITY = 64;

  2. <a name="IDj1r"></a>
  3. # 查询、新增和数据扩容。
  5. <a name="TDUxA"></a>
  6. ## 查询  
  7. ```java
  8. public V get(Object key) {
  9.     Node<K,V> e;
  10.     // 对key进行哈希操作
  11.     return (e = getNode(hash(key), key)) == null ? null : e.value;
  12. }
  14. final Node<K,V> getNode(int hash, Object key) {
  15.     Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  16.     // 非空操作
  17.     if ((tab = table) != null && (n = tab.length) > 0 &&
  18.         (first = tab[(n - 1) & hash]) != null) {
  19.         // 判断第一个元素是否是要查询的元素。
  20.         if (first.hash == hash && // always check first node
  21.             ((k = first.key) == key || (key != null && key.equals(k))))
  22.             return first;
  23.         // 下一结点非空判断
  24.         if ((e = first.next) != null) {
  25.             // 如果第一节点是树结构，则使用getTreeNode直接获取相应数据
  26.             if (first instanceof TreeNode)
  27.                 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
  28.             do {// 非树结构，循环结点进行判断
  29.                 // hash相等并且key相同，则返回此结点。
  30.                 if (e.hash == hash &&
  31.                     ((k = e.key) == key || (key != null && key.equals(k))))
  32.                     return e;
  33.             } while ((e = e.next) != null);
  34.         }
  35.     }
  36.     return null;
  37. }

新增

  1. public V put(K key, V value) {
  2.      // 对key进行哈希操作
  3.     return putVal(hash(key), key, value, false, true);
  4. }
  6. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  7.                 boolean evict) {
  8.     Node<K,V>[] tab; Node<K,V> p; int n, i;
  9.     // 哈希表为空则创建表
  10.     if ((tab = table) == null || (n = tab.length) == 0)
  11.         n = (tab = resize()).length;
  12.     // 根据key的哈希值计算出要插入的数组索引
  13.     if ((p = tab[i = (n - 1) & hash]) == null)
  14.         // 如果table[i]等于null，则直接插入
  15.         tab[i] = newNode(hash, key, value, null);
  16.     else {
  17.         Node<K,V> e; K k;
  18.         // 如果key值已经存在，直接覆盖value
  19.         if (p.hash == hash &&
  20.             ((k = p.key) == key || (key != null && key.equals(k))))
  21.             e = p;
  22.         // 如果key不存在，则判断是否为红黑树
  23.         else if (p instanceof TreeNode)
  24.             // 红黑树直接插入键值对
  25.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  26.         else {
  27.             // 为链表结构，循环准备插入
  28.             for (int binCount = 0; ; ++binCount) {
  29.                 // 下一个元素为空时
  30.                 if ((e = p.next) == null) {
  31.                     p.next = newNode(hash, key, value, null);
  32.                     // 链表长度大于8转换为红黑树进行处理
  33.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  34.                         treeifyBin(tab, hash);
  35.                     break;
  36.                 }
  37.                 // key已经存在直接覆盖value
  38.                 if (e.hash == hash &&
  39.                     ((k = e.key) == key || (key != null && key.equals(k))))
  40.                     break;
  41.                 p = e;
  42.             }
  43.         }
  44.         if (e != null) { // existing mapping for key
  45.             V oldValue = e.value;
  46.             if (!onlyIfAbsent || oldValue == null)
  47.                 e.value = value;
  48.             afterNodeAccess(e);
  49.             return oldValue;
  50.         }
  51.     }
  52.     ++modCount;
  53.     // 超过最大容量，进行扩容。
  54.     if (++size > threshold)
  55.         resize();
  56.     afterNodeInsertion(evict);
  57.     return null;
  58. }

HashMap类 - 图2

扩容

  1. final Node<K,V>[] resize() {
  2.     // 扩容之前的数组
  3.     Node<K,V>[] oldTab = table;
  4.     // 扩容前大小和阈值
  5.     int oldCap = (oldTab == null) ? 0 : oldTab.length;
  6.     int oldThr = threshold;
  7.     // 预定新数组的大小和阈值
  8.     int newCap, newThr = 0;
  9.     if (oldCap > 0) {
  10.         // 超过最大值，不再扩容
  11.         if (oldCap >= MAXIMUM_CAPACITY) {
  12.             threshold = Integer.MAX_VALUE;
  13.             return oldTab;
  14.         }
  15.         // 扩容两倍，但不超过最大值
  16.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  17.                  oldCap >= DEFAULT_INITIAL_CAPACITY)
  18.             newThr = oldThr << 1; // double threshold
  19.     }
  20.     // 当前数组没有数据，使用初始化值
  21.     else if (oldThr > 0) // initial capacity was placed in threshold
  22.         newCap = oldThr;
  23.     else {               // zero initial threshold signifies using defaults
  24.         // 如果初始化值为0，则使用默认的初始化值
  25.         newCap = DEFAULT_INITIAL_CAPACITY;
  26.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  27.     }
  28.     // 如果初始化容量值为0
  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];
  37.     // 开始扩容，将新容量交给 table
  38.     table = newTab;
  39.     // 原数据不为空，将原数据复制到新 table中
  40.     if (oldTab != null) {
  41.         // 根据容量进行循环复制非空元素给新 table
  42.         for (int j = 0; j < oldCap; ++j) {
  43.             Node<K,V> e;
  44.             if ((e = oldTab[j]) != null) {
  45.                 oldTab[j] = null;
  46.                 // 链表只有一个值，直接进行复制
  47.                 if (e.next == null)
  48.                     newTab[e.hash & (newCap - 1)] = e;
  49.                 else if (e instanceof TreeNode)
  50.                     // 红黑树操作
  51.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  52.                 else { // preserve order
  53.                     // 链表复制，JDK 1.8 扩容优化部分
  54.                     Node<K,V> loHead = null, loTail = null;
  55.                     Node<K,V> hiHead = null, hiTail = null;
  56.                     Node<K,V> next;
  57.                     do {
  58.                         next = e.next;
  59.                         // 原索引
  60.                         if ((e.hash & oldCap) == 0) {
  61.                             if (loTail == null)
  62.                                 loHead = e;
  63.                             else
  64.                                 loTail.next = e;
  65.                             loTail = e;
  66.                         }
  67.                         // 原索引 + oldCap
  68.                         else {
  69.                             if (hiTail == null)
  70.                                 hiHead = e;
  71.                             else
  72.                                 hiTail.next = e;
  73.                             hiTail = e;
  74.                         }
  75.                     } while ((e = next) != null);
  76.                     // 将原索引放到哈希桶中
  77.                     if (loTail != null) {
  78.                         loTail.next = null;
  79.                         newTab[j] = loHead;
  80.                     }
  81.                    // 将原索引 + oldCap 放到哈希桶中
  82.                     if (hiTail != null) {
  83.                         hiTail.next = null;
  84.                         newTab[j + oldCap] = hiHead;
  85.                     }
  86.                 }
  87.             }
  88.         }
  89.     }
  90.     return newTab;
  91. }

确定元素是否需要移动

1、通过高位运算 (e.hash & oldCap) 确定元素是否需要移动

key1信息：

  • key1.hash = 10 0000 1010
  • oldCap = 16 0001 0000

使用 e.hash & oldCap 得到的结果高一位为0

当结果为0时表示元素在扩容时位置不会发生任何变化

key2信息如下：

  • key2.hash = 10 0001 0001
  • oldCap = 16 0001 0000

HashMap类 - 图3

HashMap 死循环分析

以JDK1.7为例

假设HashMap默认大小为2

原本HashMap中有一个元素key(5)

再使用两个线程：

t1添加元素key(3)

t2添加元素key(7)

当元素key(3)和key(7)都添加到HashMap后，线程t1在执行到Entrynext=e.next; 时，交出了CPU的使用权

  1. void transfer(Entry[] newTable, boolean rehash){
  2.         int newCapacity = newTable.length;
  3.         for(Entry<K,V> e : newTable){
  4.             while(null != e) {
  5.                 Entry<K,V> next = e.next; //线程一执行此处
  6.                 if (rehash) {
  7.                     e.hash = null == e.key ? 0 : hash(e.key); 
  8.                 }
  10.                 int i = indexFor(e.hash,newCapacity);
  12.                 e.next = newTable[i];
  14.                 newTable[i] = e;
  15.                 e = next; 
  16.             }
  17.         }
  18.     }

当t1重新获得执行权之后
先执行newTalbe[i]=e把key(3)的next设置为key(7)
而下次循环时查询到key(7)的next元素为key(3)
于是就形成了key(3)和key(7)的循环引用
因此导致死循环的发生

HashMap类 - 图4

  • 在JDK1.7时HashMap是由数组和链表组成的，而JDK1.8则新增红黑树结构。
    当链表的长度大于8时会转换为红黑树存储，以提升元素的操作性能。
    介绍了HashMap的三个重要方法，查询、添加和扩容，以及JDK1.7 resize()在并发环境下导致死循环的原因