HashMap 的工作原理（JDK1.8）

HashMap 是 Java 和 Android 开发过程中使用频率最高的用于映射(键值对)处理的数据类型，也是面试过程中经常被问到的内容。随着 JDK1.8 版本的更新，HashMap 底层的实现进行了优化，例如引入红黑树的数据结构和扩容的优化等。本文总结了开发和面试过程中常用到的一些内容：

• HashMap 的存储结构
• HashMap 的存取机制
• HashMap 扩容机制

最近换工作过程中，腾讯和 OPPO 的面试都问到了 HashMap 数据结构的知识点，由于平时没有认真学习过数据结构的东西，所以与这些大厂擦肩而过，非常遗憾。现在痛定思痛，好好总结一下。

HashMap 的底层实现有好几个版本的，代码不一，而且看了 Android 包的 HashMap 和 JDK 中的 HashMap 的也不是一样，原来他们没有指定 JDK 版本，很多文章都是旧版本 JDK1.6 和 JDK1.7 的。现在我来分析一下最新的 JDK1.8 的 HashMap 及性能优化。

1 HashMap 的存储结构

如图所示，HashMap 是数组+链表+红黑树（JDK1.8 增加了红黑树部分）实现的，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。简单来讲：

首先有一个每个元素都是链表（可能表述不准确）的数组，当添加一个元素（key-value）时，就首先计算元素 key 的 hash 值，以此确定插入数组中的位置，但是可能存在同一 hash 值的元素已经被放在数组同一位置了，这时就添加到同一 hash 值的元素的后面（俗称 hash 冲突，链表结构出现的实际意义也就是为了解决 hash 冲突的问题），他们在数组的同一位置，但是形成了链表，同一各链表上的 Hash 值是相同的，所以说数组存放的是链表。而当链表长度太长时，链表就转换为红黑树，这样大大提高了查找的效率。

2 HashMap 的存取机制 2.1 HashMap 如何 put(key，value)

    public V put(K key, V value) {          return putVal(hash(key), key, value, false, true);      }       /**      * Implements Map.put and related methods      *      * @param hash hash for key      * @param key the key      * @param value the value to put      * @param onlyIfAbsent if true, don't change existing value      * @param evict if false, the table is in creation mode.      * @return previous value, or null if none      */      final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                     boolean evict) {          Node[] tab;           Node p;           int n, i;          if ((tab = table) == null || (n = tab.length) == 0)              n = (tab = resize()).length;          /*如果 table 的在（n-1）&hash 的值是空，就新建一个节点插入在该位置*/          if ((p = tab[i = (n - 1) & hash]) == null)              tab[i] = newNode(hash, key, value, null);          /*表示有冲突,开始处理冲突*/          else {              Node e;               K k;              /*检查第一个 Node，p 是不是要找的值*/              if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))                  e = p;              else if (p instanceof TreeNode)                  e = ((TreeNode)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 个，看是否需要改变冲突节点的存储结构，　　　　　　　　　　　　　                          //treeifyBin 首先判断当前 hashMap 的长度，如果不足 64，只进行                          //resize，扩容 table，如果达到 64，那么将冲突的存储结构为红黑树                          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                              treeifyBin(tab, hash);                          break;                      }                      /*如果有相同的 key 值就结束遍历*/                      if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))                          break;                      p = e;                  }              }              /*就是链表上有相同的 key 值*/              if (e != null) { // existing mapping for key，就是 key 的 Value 存在                  V oldValue = e.value;                  if (!onlyIfAbsent || oldValue == null)                      e.value = value;                  afterNodeAccess(e);                  return oldValue;//返回存在的 Value 值              }          }          ++modCount;           /*如果当前大小大于门限，门限原本是初始容量*0.75*/          if (++size > threshold)              resize();//扩容两倍          afterNodeInsertion(evict);          return null;      }

添加键值对 put(key,value) 的过程,如代码中所示：

1. 判断键值对数组 tab[] 是否为空或为 null，否则以默认大小 resize() ；
2. 根据键值 key 计算 hash 值得到插入的数组索引 i，如果 tab[i]==null ，直接新建节点添加，否则转入 3
3. 判断当前数组中处理 hash 冲突的方式为链表还是红黑树( check 第一个节点类型即可),分别处理

2.2 HashMap 如何 get(Object key) 值

public V get(Object key) {          Node e;          return (e = getNode(hash(key), key)) == null ? null : e.value;      }        /**      * Implements Map.get and related methods      *      * @param hash hash for key      * @param key the key      * @return the node, or null if none      */      final Node getNode(int hash, Object key) {          Node[] tab;//Entry 对象数组      Node first,e; //在 tab 数组中经过散列的第一个位置      int n;      K k;      /*找到插入的第一个 Node，方法是 hash 值和 n-1 相与，tab[(n - 1) & hash]*/      //也就是说在一条链上的 hash 值相同的          if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {      /*检查第一个 Node 是不是要找的 Node*/              if (first.hash == hash && // always check first node                  ((k = first.key) == key || (key != null && key.equals(k))))//判断条件是 hash 值要相同，key 值要相同                  return first;        /*检查 first 后面的 node*/              if ((e = first.next) != null) {                  if (first instanceof TreeNode)                      return ((TreeNode)first).getTreeNode(hash, key);                  /*遍历后面的链表，找到 key 值和 hash 值都相同的 Node*/                  do {                      if (e.hash == hash &&                          ((k = e.key) == key || (key != null && key.equals(k))))                          return e;                  } while ((e = e.next) != null);              }          }          return null;      }

获取键值对 get(key) 的过程,如代码中所示：

先计算 hash&(n-1) 得到在链表数组中的位置 first = tab[(n - 1) & hash] ,先判断 first 的 key 是否与参数 key 相等，不等就遍历后面的链表找到相同的 key 值返回对应的 Value 值即可

3 HashMap 扩容机制 resize()

首先我们需要了解一下，构造 hash 表时，如果不指明初始大小，默认大小为 16（即 Node 数组大小 16 ），如果 Node[]数组中的元素达到（填充比* Node.length ）重新调整 HashMap 大小 变为原来 2 倍大小,需要注意的是，扩容很耗时。

其中默认的填充比为 0.75

在扩容的过程中，使用的是 2 次幂的扩展(指长度扩为原来 2 倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动 2 次幂的位置。看下图可以明白这句话的意思，n 为 table 的长度，图（a）表示扩容前的 key1 和 key2 两种 key 确定索引位置的示例，图（b）表示扩容后 key1 和 key2 两种 key 确定索引位置的示例，其中 hash1 是 key1 对应的哈希与高位运算结果。

元素在重新计算 hash 之后，因为 n 变为 2 倍，那么 n-1 的 mask 范围在高位多 1bit(红色)，因此新的 index 就会发生这样的变化：

因此，我们在扩充 HashMap 的时候，只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就好了，是 0 的话索引没变，是 1 的话索引变成“原索引+ oldCap ”，可以看看下图为 16 扩充为 32 的 resize 示意图：

这样我们既省去了重新计算 hash 值的时间，而且同时，由于新增的 1 bit 是 0 还是 1 可以认为是随机的，因此 resize 的过程，均匀的把之前的冲突的节点分散到新的槽中啦。

有一点注意区别，JDK1.7 中 rehash 的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8 不会倒置

我们来看一下 JDK 1.8 的源码：

/**     * Initializes or doubles table size.  If null, allocates in     * accord with initial capacity target held in field threshold.     * Otherwise, because we are using power-of-two expansion, the     * elements from each bin must either stay at same index, or move     * with a power of two offset in the new table.     *     * @return the table     */     final Node[] resize() {         Node[] oldTab = table;         int oldCap = (oldTab == null) ? 0 : oldTab.length;         int oldThr = threshold;         int newCap, newThr = 0;          /*如果旧表的长度不是空*/         if (oldCap > 0) {              // 超过最大值就不再扩充了，就只好随你碰撞去吧           if (oldCap >= MAXIMUM_CAPACITY) {                 threshold = Integer.MAX_VALUE;                 return oldTab;             }              /*没超过最大值,把新表的长度设置为旧表长度的两倍，newCap=2*oldCap*/             else if ((newCap = oldCap = DEFAULT_INITIAL_CAPACITY)                   /*把新表的门限设置为旧表门限的两倍，newThr=oldThr*2*/                 newThr = oldThr  0) // initial capacity was placed in threshold             newCap = oldThr;         else {               // zero initial threshold signifies using defaults             newCap = DEFAULT_INITIAL_CAPACITY;             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);         }         // 计算新的 resize 上限       if (newThr == 0) {             float ft = (float)newCap * loadFactor;//新表长度乘以加载因子             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                       (int)ft : Integer.MAX_VALUE);         }         threshold = newThr;         @SuppressWarnings({"rawtypes","unchecked"})          /*下面开始构造新表，初始化表中的数据*/         Node[] newTab = (Node[])new Node[newCap];         table = newTab;//把新表赋值给 table         if (oldTab != null) {//原表不是空要把原表中数据移动到新表中                 /*遍历原来的旧表,把每个 bucket 都移动到新的 buckets 中*/                   for (int j = 0; j < oldCap; ++j) {                 Node e;                 if ((e = oldTab[j]) != null) {                     oldTab[j] = null;                     if (e.next == null)//说明这个 node 没有链表直接放在新表的 e.hash & (newCap - 1)位置                         newTab[e.hash & (newCap - 1)] = e;                     else if (e instanceof TreeNode)                         ((TreeNode)e).split(this, newTab, j, oldCap);                      /*如果 e 后边有链表,到这里表示 e 后面带着个单链表，需要遍历单链表，将每个结点重*/                     else { // preserve order 保证顺序                      //新计算在新表的位置，并进行搬运                         Node loHead = null, loTail = null;                         Node hiHead = null, hiTail = null;                         Node next;                         do {                             next = e.next;//记录下一个结点                              //新表是旧表的两倍容量，实例上就把单链表拆分为两队，  　　　　　　　　　　　　　      //e.hash&oldCap 为偶数一队，e.hash&oldCap 为奇数一对                             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) {//lo 队不为 null，放在新表原位置                             loTail.next = null;                             newTab[j] = loHead;                         }                         if (hiTail != null) {//hi 队不为 null，放在新表 j+oldCap 位置                             hiTail.next = null;                             newTab[j + oldCap] = hiHead;                         }                     }                 }             }         }         return newTab;     }

        //这个函数的功能是对红黑树进行　rehash 操作        final void split(HashMap map, Node[] tab, int index, int bit) {              TreeNode b = this;              // Relink into lo and hi lists, preserving order              TreeNode loHead = null, loTail = null;              TreeNode hiHead = null, hiTail = null;              int lc = 0, hc = 0;      　　　　　//由于　TreeNode 节点之间存在双端链表的关系，可以利用链表关系进行 rehash              for (TreeNode e = b, next; e != null; e = next) {                 next = (TreeNode)e.next;                 e.next = null;                 if ((e.hash & bit) == 0) {                     if ((e.prev = loTail) == null)                         loHead = e;                     else                         loTail.next = e;                     loTail = e;                     ++lc;                 }                 else {                     if ((e.prev = hiTail) == null)                         hiHead = e;                     else                         hiTail.next = e;                     hiTail = e;                     ++hc;                 }             }             //rehash 操作之后注意对根据链表长度进行　untreeify　或　treeify　操作             if (loHead != null) {                 if (lc