简单介绍

什么是 HashMap？

HashMap 是Java日常开发常用的一个集合类。Map集合即Key-Value的集合，前面加个Hash，即散列，无序的。所以HashMap是一个用于存储Key-Value键值对的无序集合，每一个键值对也叫做Entry。

HashMap 的特性

这里我们先做回答，解决几个面试常问的HashMap问题，借此方式来初步了解HashMap的特性。

HashMap的底层是怎么实现的？&& HashMap的扩容机制？

在JDK1.8之前，HashMap采用数组+链表实现，即使用拉链法解决hash冲突。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值查找要遍历链表，时间复杂度为O(N)，效率较低。因此JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树），搜索的时间复杂度为O(logN)，这样大大减少了查找时间。

为什么说HashMap是线程不安全的？

HashMap在put的时候，插入的元素超过了容量（由负载因子决定）的范围就会触发扩容操作，就是rehash，这个会重新将原数组的内容重新hash到新的扩容数组中，在多线程的环境下，存在同时其他的元素也在进行put操作，如果hash值相同，可能出现同时在同一数组下用链表表示，造成闭环，导致在get时会出现死循环，所以HashMap是线程不安全的。

HashMap的长度为什么是2的幂次方？

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。Hash 值的范围值-2147483648 到 2147483647，前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash”。（n 代表数组长度）。这也就解释了 HashMap 的长度为什么是 2 的幂次方。

其他的特性？

• HashMap 允许 null 键和 null 值
• HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。

HashMap 源码分析

这里我们主要的阅读材料是JDK1.8的HashMap源码

底层数据结构

在网上找到一张很好的图

可以说HashMap就是一个桶数组，当桶内数据超过八个之后，桶内存储结构会由链表变成红黑树。

大体结构我们了解了，接下来是具体编码了

类的属性：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { // 序列号 private static final long serialVersionUID = 362498820763181265L; // 默认的初始容量是16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; // 默认的填充因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 当桶(bucket)上的结点数大于这个值时会转成红黑树 static final int TREEIFY_THRESHOLD = 8; // 当桶(bucket)上的结点数小于这个值时树转链表 static final int UNTREEIFY_THRESHOLD = 6; // 桶中结构转化为红黑树对应的table的最小容量 static final int MIN_TREEIFY_CAPACITY = 64; // 存储元素的数组，总是2的幂次倍 transient Node<k,v>[] table; // 存放具体元素的集 transient Set<map.entry<k,v>> entrySet; // 存放元素的个数，注意这个不等于数组的长度。 transient int size; // 每次扩容和更改map结构的计数器 transient int modCount; // 临界值(容量*填充因子) 当实际大小超过临界值时，会进行扩容 int threshold; // 加载因子 final float loadFactor;
 }

HashMap内部链表节点类的实现：

static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key;
         V value;
         Node<K,V> next;
 
         Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next;
         } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value);
         } public final V setValue(V newValue) {
             V oldValue = value;
             value = newValue; return oldValue;
         } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) {
                 Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) &&
                     Objects.equals(value, e.getValue())) return true;
             } return false;
         }
     }

HashMap内部红黑树节点类型的实现

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
         TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left;
         TreeNode<K,V> right;
         TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red;
         TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next);
         } /**
          * Returns root of tree containing this node.
          */ final TreeNode<K,V> root() { for (TreeNode<K,V> r = this, p;;) { if ((p = r.parent) == null) return r;
                 r = p;
             }
         } /**
          * Ensures that the given root is the first node of its bin.
          */ static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
         } /**
          * Finds the node starting at root p with the given hash and key.
          * The kc argument caches comparableClassFor(key) upon first use
          * comparing keys.
          */ final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
         } /**
          * Calls find for root node.
          */ final TreeNode<K,V> getTreeNode(int h, Object k) {
         } /**
          * Tie-breaking utility for ordering insertions when equal
          * hashCodes and non-comparable. We don't require a total
          * order, just a consistent insertion rule to maintain
          * equivalence across rebalancings. Tie-breaking further than
          * necessary simplifies testing a bit.
          */ static int tieBreakOrder(Object a, Object b) {
         } /**
          * Forms tree of the nodes linked from this node.
          */ final void treeify(Node<K,V>[] tab) {
         } /**
          * Returns a list of non-TreeNodes replacing those linked from
          * this node.
          */ final Node<K,V> untreeify(HashMap<K,V> map) {
         } /**
          * Tree version of putVal.
          */ final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) {
         } /**
          * Removes the given node, that must be present before this call.
          * This is messier than typical red-black deletion code because we
          * cannot swap the contents of an interior node with a leaf
          * successor that is pinned by "next" pointers that are accessible
          * independently during traversal. So instead we swap the tree
          * linkages. If the current tree appears to have too few nodes,
          * the bin is converted back to a plain bin. (The test triggers
          * somewhere between 2 and 6 nodes, depending on tree structure).
          */ final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable) {
         } /**
          * Splits nodes in a tree bin into lower and upper tree bins,
          * or untreeifies if now too small. Called only from resize;
          * see above discussion about split bits and indices.
          *
          * @param map the map
          * @param tab the table for recording bin heads
          * @param index the index of the table being split
          * @param bit the bit of hash to split on
          */ final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
         } /* ------------------------------------------------------------ */ // Red-black tree methods, all adapted from CLR static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                               TreeNode<K,V> p) {
         } static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                                TreeNode<K,V> p) {
         } static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                     TreeNode<K,V> x) {
         } static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                                    TreeNode<K,V> x) {
         } /**
          * Recursive invariant check
          */ static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
         }
     }

初始容量、负载因子、阈值

一般情况下我们都会使用无参构造 HashMap。但当我们对时间和空间复杂读有要求的时候，我们需要手动调参，以让 HashMap 满足我们的要求。可供我们调整的参数有两个，一个是初始容量 initialCapacity，另一个负载因子 loadFactor。设定这两个参数会影响到阈值的大小。初始阈值 threshold 由 initialCapacity 经过移位操作计算得出。他们的作用分别如下：

相关代码如下：

/**
  * The default initial capacity - MUST be a power of two.
  */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /**
 * The load factor used when none specified in constructor.
 */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /**
 * The next size value at which to resize (capacity * load factor).
 *
 * @serial */ int threshold; /**
 * The load factor for the hash table.
 *
 * @serial */ final float loadFactor;

我们首先从阈值（threshold）开始分析

通过看代码我们知道了HashMap初始容量是16，负载因子是0.75，而阈值我们从注释中知道是由容量乘以负载因子计算得来的。

本着求实的态度，我们查看下HashMap的构造函数：

public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " +
                                            initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY)
         initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " +
                                            loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity);
 }

tableSizeFor方法：

static final int tableSizeFor(int cap) { int n = cap - 1;
     n |= n >>> 1;
     n |= n >>> 2;
     n |= n >>> 4;
     n |= n >>> 8;
     n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
 }

看到这个tableSizeFor方法，似乎与上面说的 threshold=capacity * load factor 有出入。

这个算法的作用就是找到大于或等于 cap 的最小2的幂。过程就是将二进制数从左往右数的第一个1开始右边全部变成1，最后再加上1，就是结果了。

比如我们传入的cap为31，观察n的变化过程：

1 1110(30) -> 1 1111 -> 10 0000(31 + 1) -> 32

事实也是如此：

以上就是初始阈值(threshold)的计算过程了。接着我们看看负载因子(loadFactor)。

先问几个问题：

• 什么是负载因子？

  根据上面的学习我们知道阈值（threshold） = 负载因子（loadFactor） * 容量（capacity）

  loadFactor 是负载因子，表示 HashMap 满的程度，默认值为 0.75f，也就是说默认情况下，当 HashMap 中元素个数达到了容量的 3/4 的时候就会进行自动扩容。

• 为什么要扩容？

  HashMap 在扩容到过程中不仅要对其容量进行扩充，还需要进行 rehash！所以，这个过程其实是很耗时的，并且 Map 中元素越多越耗时。

  rehash 的过程相当于对其中所有的元素重新做一遍 hash，重新计算要分配到那个桶中。

  那么为什么要扩容？HashMap 不是一个数组链表吗？不扩容的话，也是可以无限存储的呀。为啥要扩容？

  原因就在于哈希碰撞！

  哈希碰撞：两个不同的输入值，根据同一哈希函数计算出的哈希值相同的现象叫做碰撞。

  为了解决哈希冲突，HashMap使用了链地址法。

  
  
  
  

HashMap是基于链表的数组的数据结构实现的。

我们知道冲突以后拉链***向对应链表后面添加元素，一旦冲突多了数组的链表就会退化成链表，**查找效率大大降低**。

所以为了保证HashMap的查找效率，我们需要扩容，来保证HashMap的冲突不要太高。

所以负载因子实际是反应了 HashMap 桶数组的使用情况：

• 调低负载因子，HashMap 所能容纳的键值对数量变少。扩容时，重新将键值对存储进新的桶数组里，键与键之间产生的碰撞会下降，链表长度变短。此时，HashMap 的CRUD操作效率会变高，这就是典型的拿空间换时间。
• 增加负载因子（负载因子可以大于1），HashMap所能容纳的键值对数量变多，空间利用率高，但碰撞率也高。这意味着链表长度变长，效率也随之降低，这种情况是拿时间换空间。

正常来说默认的0.75就已经是很合理的解了，如果有特殊需求，可以按照上面讲的进行调整。

hash方法（扰动函数）

HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过(n - 1) & hash判断当前元素存放的位置（这里的n指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

jdk1.8 的 hash 方法

static final int hash(Object key) { int h; // key.hashCode()：返回散列值也就是hashcode // ^ ：按位异或 // >>>:无符号右移，忽略符号位，空位都以0补齐 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }

• 解释

  key.hashCode()是Keyt自带的hashCode()方法，返回一个int的散列值，范围从-2147483648到2147483648。但是这样的散列值是不能直接拿来用的，用之前需要对数组的长度做取模运算。得到的余数才是索引值。

  int index = hash & (arrays.length-1);

  那么这也就明白了为什么HashMap的数组长度是2的整数幂。

  比如以初始长度为16为例，16-1 = 15，15的二进制数位00000000 00000000 00001111。可以看出一个奇数二进制最后一位必然位1，当与一个hash值进行与运算时，最后一位可能是0也可能是1。但偶数与一个hash值进行与运算最后一位必然为0，造成有些位置永远映射不上值。(想尽办法的扰动)

  但是，即使散列函数很松散，但是最后结果我们只取后面几位，碰撞依旧是很严重的。这个时候我们的hash函数的价值体现出来了。

  我们将hashCode与自己右移16位的结果(刚好32bit的一半)进行异或操作。就是为了混合哈希值的高位和低位，增加低位的随机性，并且混合后的值也变相保持了高位的特征。

对比 jdk1.7 的hash方法

static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);
 }

1.7的hash算法扰动了4次，所以相比于1.8的算法是比较慢的。

get方法 (查找)

查找的入口方法在get, 主要逻辑在getNode方法

查找操作，先定位键值对所在的桶位置，然后再对链表或者红黑树进行查找。

public V get(Object key) {
     Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value;
 } final Node<K,V> getNode(int hash, Object key) {
     Node<K,V>[] tab; Node<K,V> first, e; int n; K k; // 1\. 定位键值对所在桶的位置 if ((tab = table) != null && (n = tab.length) > 0 &&
         (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { // 2\. 如果first是TreeNode类型，则使用红黑树查找方法 if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); // 2\. 否则对链表进行查找 do { if (e.hash == hash &&
                     ((k = e.key) == key || (key != null && key.equals(k)))) return e;
             } while ((e = e.next) != null);
         }
     } return null;
 }

查找核心在于getNode()方法。里面已经做了注释。

我们先看到第一步“定位键值对所在桶的位置”，实现代码如下：

first = tab[(n - 1) & hash 

这里通过(n-1)&hash可以算出桶在桶数组中的位置。解释一下，HashMap中桶数组的大小 length 总是 2 的幂。此时，(n-1)&hash等价于对length取余。但取余效率没有位运算高，所以(n-1)&hash也是一个小的优化。

假设 hash=143，n=16。计算过程如下：

最终结果为15，刚好就是143%16的结果。

put方法 (插入)

对于插入操作我们先分析大体流程：

首先肯定是先定位要插入的键值对属于哪个桶，定位到桶后，再判断桶是否为空。如果为空，则将键值对存入即可。如果不为空，则需将键值对接在链表最后一个位置，或者更新键值对。

当然插入过程还有很多细节。首先HashMap是变长集合，需要考虑扩容问题。其次，在JDK1.8中，HashMap引入了红黑树优化过长链表，所以这里要考虑优化过程。

插入操作的入口在put(K,V)，核心在V putVal(int, K, V, boolean, boolean)方法中。

首先我们看下插入操作的源码：

public V put(K key, V value) { return putVal(hash(key), key, value, false, true);
 } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
     Node<K,V>[] tab; Node<K,V> p; int n, i; // 初始化桶数组 table，table 被延迟到插入新数据时再进行初始化 if ((tab = table) == null || (n = tab.length) == 0)
         n = (tab = resize()).length; // 如果桶中不包含键值对节点引用，则将新键值对节点的引用存入桶中即可 if ((p = tab[i = (n - 1) & hash]) == null)
         tab[i] = newNode(hash, key, value, null); else {
         Node<K,V> e; K k; // 如果键的值以及节点 hash 等于链表中的第一个键值对节点时，则将 e 指向该键值对 if (p.hash == hash &&
             ((k = p.key) == key || (key != null && key.equals(k))))
             e = p; // 如果桶中的引用类型为 TreeNode，则调用红黑树的插入方法 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); // 如果链表长度大于或等于树化阈值，则进行树化操作 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break;
                 } // 条件为 true，表示当前链表包含要插入的键值对，终止遍历 if (e.hash == hash &&
                     ((k = e.key) == key || (key != null && key.equals(k)))) break;
                 p = e;
             }
         } // 判断要插入的键值对是否存在 HashMap 中 if (e != null) { // existing mapping for key V oldValue = e.value; // onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值 if (!onlyIfAbsent || oldValue == null)
                 e.value = value;
             afterNodeAccess(e); return oldValue;
         }
     }
     ++modCount; // 键值对数量超过阈值时，则进行扩容 if (++size > threshold)
         resize();
     afterNodeInsertion(evict); return null;
 }

putVal的主要逻辑：

1. 当桶数组 table 为空时，通过resize(扩容)的方式初始化 table

2. 如果定位到的数组位置有元素，存在的话如果 key 相同就直接覆盖，如果 key 不相同，就判断 p 是否是一个树节点，如果是就调用putTreeVal将元素添加进入。如果不是就遍历链表插入(插入的是链表尾部)。

3. 如果定位到的数组位置没有元素，则将键值对链入链表中，并根据链表长度决定是否将链表转为红黑树（treeifyBin 树化操作）

4. 判断键值对数量是否大于阈值，大于的话则进行扩容操作resize

可以看出来resize(扩容)在插入操作的逻辑中非常重要，接下来我们就讲HashMap的扩容机制。

扩容机制

resize方法 (扩容主要逻辑)

背景知识：在 HashMap 中，桶数组的长度均是2的幂，阈值大小为桶数组长度与负载因子的乘积。当 HashMap 中的键值对数量超过阈值时，进行扩容。

需要注意：进行扩容，会伴随着一次重新 hash 分配，并且会遍历 hash 表中所有的元素，是非常耗时的。在编写程序中，要尽量避免 resize。

HashMap按照当前桶数组长度的2倍进行扩容，扩容之后，要重新计算键值对的位置，并把它们移动到合适的位置上去。

具体实现：

final Node<K,V>[] resize() {
     Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; // 如果 table 不为空，表明已经初始化过了 if (oldCap > 0) { // 当 table 容量超过容量最大值，则不再扩容 if (oldCap >= MAXIMUM_CAPACITY) {
             threshold = Integer.MAX_VALUE; return oldTab;
         } // 按旧容量和阈值的2倍计算新容量和阈值的大小 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                  oldCap >= DEFAULT_INITIAL_CAPACITY)
             newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold /*
          * 初始化时，将 threshold 的值赋值给 newCap，
          * HashMap 使用 threshold 变量暂时保存 initialCapacity 参数的值
          */ newCap = oldThr; else { // zero initial threshold signifies using defaults /*
          * 调用无参构造方法时，桶数组容量为默认容量，
          * 阈值为默认容量与默认负载因子乘积
          */ newCap = DEFAULT_INITIAL_CAPACITY;
         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
     } // newThr 为 0 时，按阈值计算公式进行计算 if (newThr == 0) { float ft = (float)newCap * loadFactor;
         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                   (int)ft : Integer.MAX_VALUE);
     }
     threshold = newThr; // 创建新的桶数组，桶数组的初始化也是在这里完成的 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) { 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;
                     }
                 }
             }
         }
     } return newTab;
 }

resize方法的主要逻辑：

1. 计算新桶数组的容量 newCap 和新阈值 newThr

   // 第一个条件分支 if ( oldCap > 0) { // 嵌套条件分支 if (oldCap >= MAXIMUM_CAPACITY) {...} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY) {...}
    } else if (oldThr > 0) {...} else {...} // 第二个条件分支 if (newThr == 0) {...}

   分支一：

   • oldCap>0：桶数组table已经被初始化，这种情况下，会将 oldThr 赋值给 newCap，等价于newCap = threshold = tableSizeFor(initialCapacity)。我们在初始化时传入的 initialCapacity 参数经过 threshold 中转最终赋值给了 newCap。

   • oldThr>0：threshold>0, 且桶数组未被初始化，调用 HashMap(int) 和 HashMap(int, float) 构造方法时会产生这种情况，此种情况下 newCap = oldThr，newThr 在第二个条件分支中算出

   • oldCap == 0 && oldThr == 0：桶数组未被初始化，且 threshold 为 0，调用 HashMap() 构造方***产生这种情况。

   嵌套分支：

   • oldCap >= MAXIMUM_CAPACITY：桶数组容量大于或等于最大桶容量 2^30，这个时候不再扩容

   • newCap < MAXIMUM_CAPACITY && oldCap > DEFAULT_INITIAL_CAPACITY：新桶数组容量小于最大值，且旧桶数组容量大于 16

   分支二：

   • newThr == 0：第一个条件分支未计算 newThr 或嵌套分支在计算过程中导致 newThr 溢出归零

2. 根据计算出的 newCap 创建新的桶数组，桶数组 table 也是在这里进行初始化的

3. 将键值对节点重新映射到新的桶数组里。如果节点是 TreeNode 类型，则需要拆分红黑树。如果是普通节点，则节点按原顺序进行分组。该种情况下新阈值 newThr = oldThr << 1，移位可能会导致溢出。

   那么如何链表是重新映射呢？

   往底层数据结构中插入节点时，先通过模运算计算桶位置，接着把节点放入桶中即可。我们可以将重新映射看作是插入操作，JDK1.7确实就是这样做的。

   但在JDK1.8中对过程进行了一定优化，重新映射节点需要考虑节点类型。对于树形节点，需先拆分红黑树再映射。对于链表类型节点，则需先对链表进行分组，然后再映射。需要的注意的是，分组后，组内节点相对位置保持不变。

   看个例子：

   
   
   
   

如果我们对上图桶数组进行扩容，扩容后容量 n =16，重新映射过程如下：

依次遍历链表，并计算节点 `hash & oldCap` 的值。

35&8=0; 27&8!=0; 19&8=0; 43&8!=0;

如果值为0，将 loHead 和 loTail 指向这个节点。如果后面还有节点 hash & oldCap 为0的话，则将节点链入 loHead 指向的链表中，并将 loTail 指向该节点。如果值为非0的话，则让 hiHead 和 hiTail 指向该节点。完成遍历后，可能会得到两条链表，此时就完成了链表分组：

最后将这两条连直接存放到对应的桶中，完成扩容。

JDK1.8的HashMap扩容效率是要高于之前版本的。JDK1.7为了防止因hash碰撞引发的拒绝服务攻击，在计算hash过程中引入随机种子，为了增强hash的随机性，使得键值对均匀分布在桶数组中。在扩容过程中，相关方***根据容量判断是否需要生成新的随机种子，并重新计算所有节点的hash。而在JDK1.8中则通过引入红黑树替代了该方式。从而避免了多次计算hash的操作，提高了扩容效率。

以上我们就讲完了扩容的主体逻辑。扩容后，红黑树节点和普通节点一样是需要重新映射的。于是我们接着就说红黑树的分组和重新映射。(split方法的调用可以在resize方法体中找到。)

split方法 (红黑树拆分)

// 红黑树转链表阈值 static final int UNTREEIFY_THRESHOLD = 6; final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
     TreeNode<K,V> b = this; // Relink into lo and hi lists, preserving order TreeNode<K,V> loHead = null, loTail = null;
     TreeNode<K,V> hiHead = null, hiTail = null; int lc = 0, hc = 0; /* 
      * 红黑树节点仍然保留了 next 引用，故仍可以按链表方式遍历红黑树。
      * 下面的循环是对红黑树节点进行分组，与上面类似
      */ for (TreeNode<K,V> e = b, next; e != null; e = next) {
         next = (TreeNode<K,V>)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;
         }
     } if (loHead != null) { // 如果 loHead 不为空，且链表长度小于等于 6，则将红黑树转成链表 if (lc <= UNTREEIFY_THRESHOLD)
             tab[index] = loHead.untreeify(map); else {
             tab[index] = loHead; /* 
              * hiHead == null 时，表明扩容后，
              * 所有节点仍在原位置，树结构不变，无需重新树化
              */ if (hiHead != null) 
                 loHead.treeify(tab);
         }
     } // 与上面类似 if (hiHead != null) { if (hc <= UNTREEIFY_THRESHOLD)
             tab[index + bit] = hiHead.untreeify(map); else {
             tab[index + bit] = hiHead; if (loHead != null)
                 hiHead.treeify(tab);
         }
     }
 }

重新映射红黑树的逻辑和重新映射链表的逻辑基本一致。不同的地方在于，重新映射后，会将红黑树拆分成两条由 TreeNode 组成的链表。如果链表长度小于 UNTREEIFY_THRESHOLD，则将链表转换成普通链表。否则根据条件重新将 TreeNode 链表树化。

举个例子：

我们对该桶数组进行扩容,扩容后需要重新映射上面的红黑树，映射结果如下：

treeifyBin方法 (链表树化)

JDK1.8对HashMap实现进行了改进。最大的改进就是引入了红黑树。

树化相关的代码:

static final int TREEIFY_THRESHOLD = 8; /**
  * 当桶数组容量小于该值时，优先进行扩容，而不是树化
  */ static final int MIN_TREEIFY_CAPACITY = 64; static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
     TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left;
     TreeNode<K,V> right;
     TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red;
     TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next);
     }
 } /**
  * 将普通节点链表转换成树形节点链表
  */ final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; // 桶数组容量小于 MIN_TREEIFY_CAPACITY，优先进行扩容而不是树化 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
         resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { // hd 为头节点（head），tl 为尾节点（tail） TreeNode<K,V> hd = null, tl = null; do { // 将普通节点替换成树形节点 TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null)
                 hd = p; else {
                 p.prev = tl;
                 tl.next = p;
             }
             tl = p;
         } while ((e = e.next) != null); // 将普通链表转成由树形节点链表 if ((tab[index] = hd) != null) // 将树形链表转换成红黑树 hd.treeify(tab);
     }
 } TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { return new TreeNode<>(p.hash, p.key, p.value, next);
 }

扩容的过程中，树化需要满足两个条件:

1. 链表长度大于等于 TREEIFY_THRESHOLD

   链表长度大于等于了树化阈值，也就是我们面试常考的8，才进行树化。

2. 桶数组容量大于等于 MIN_TREEIFY_CAPACITY

   桶数组容量比较小的时候，应当优先扩容，减少hash碰撞的概率。

HashMap在设计之初，没有考虑到以后会引入红黑树进行优化。所以并没有像TreeMap一样，要求键类实现Comparable接口，或提供对应的比较器。但由于树化的过程需要比较两个键对象的大小，在键类没有实现Comparable接口的情况下，这成了一个问题。HashMap做了三步操作。通过下面三步操作就能知道谁大谁小，最终构造出红黑树了。

1. 比较键与键之间hash的大小，如果hash相同，继续往下比较。
2. 检测键类是否实现了Comparable接口，如果实现调用compareTo方法进行比较
3. 如果仍未比较出大小，据需要进行仲裁了，仲裁方法为tieBreadOrder

untreeify方法 (红黑树链化)

红黑树中仍然保留了原链表节点的顺序。有了这个前提，将红黑树转化成链表，仅需将 TreeNode 链表转换成 Node 类型的链表即可。

final Node<K,V> untreeify(HashMap<K,V> map) {
     Node<K,V> hd = null, tl = null; // 遍历 TreeNode 链表，并用 Node 替换 for (Node<K,V> q = this; q != null; q = q.next) { // 替换节点类型 Node<K,V> p = map.replacementNode(q, null); if (tl == null)
             hd = p; else tl.next = p;
         tl = p;
     } return hd;
 } Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) { return new Node<>(p.hash, p.key, p.value, next);
 }

remove方法 (删除)

HashMap 的删除操作并不复杂，入口方法为remove，主要逻辑在removeNode方法。

删除仅需三个步骤即可完成。第一步是定位桶位置，第二步遍历链表并找到键值相等的节点，第三步删除节点。相关源码如下：

public V remove(Object key) {
     Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
 } final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
     Node<K,V>[] tab; Node<K,V> p; int n, index; if ((tab = table) != null && (n = tab.length) > 0 && // 1\. 定位桶位置 (p = tab[index = (n - 1) & hash]) != null) {
         Node<K,V> node = null, e; K k; V v; // 如果键的值与链表第一个节点相等，则将 node 指向该节点 if (p.hash == hash &&
             ((k = p.key) == key || (key != null && key.equals(k))))
             node = p; else if ((e = p.next) != null) { // 如果是 TreeNode 类型，调用红黑树的查找逻辑定位待删除节点 if (p instanceof TreeNode)
                 node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { // 2\. 遍历链表，找到待删除节点 do { if (e.hash == hash &&
                         ((k = e.key) == key ||
                          (key != null && key.equals(k)))) {
                         node = e; break;
                     }
                     p = e;
                 } while ((e = e.next) != null);
             }
         } // 3\. 删除节点，并修复链表或红黑树 if (node != null && (!matchValue || (v = node.value) == value ||
                              (value != null && value.equals(v)))) { if (node instanceof TreeNode)
                 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); else if (node == p)
                 tab[index] = node.next; else p.next = node.next;
             ++modCount;
             --size;
             afterNodeRemoval(node); return node;
         }
     } return null;
 }

HashMap 的使用

HashMap 的几种遍历方式

总共的遍历方式在查阅后发现有7种。

遍历方式主要分成下面的四个方向：

1. 迭代器（Iterator）方式遍历。

   // 遍历 EntrySet Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator(); while (iterator.hasNext()) { Map.Entry<Integer, String> entry = iterator.next();
        System.out.println(entry.getKey());
        System.out.println(entry.getValue());
    } // 遍历 KeySet Iterator<Integer> iterator = map.keySet().iterator(); while (iterator.hasNext()) {
        Integer key = iterator.next();
        System.out.println(key);
        System.out.println(map.get(key));
    }

2. For Each 方式遍历。

   // 遍历 EntrySet for (Map.Entry<Integer, String> entry : map.entrySet()) {
        System.out.println(entry.getKey());
        System.out.println(entry.getValue());
    } // 遍历 KeySet for (Integer key : map.keySet()) {
        System.out.println(key);
        System.out.println(map.get(key));
    }

3. Lambda 表达式遍历（JDK 1.8+）。

   // 遍历 map.forEach((key, value) -> {
        System.out.println(key);
        System.out.println(value);
    });

4. Streams API 遍历（JDK 1.8+）。

   // 遍历 单线程 map.entrySet().stream().forEach((entry) -> {
        System.out.println(entry.getKey());
        System.out.println(entry.getValue());
    }); // 遍历 多线程 map.entrySet().parallelStream().forEach((entry) -> {
        System.out.println(entry.getKey());
        System.out.println(entry.getValue());
    });

entrySet的性能比keySet的性能高，所以我们还是尽量使用entrySet来遍历HashMap。

小结

HashMap是Java学习者绕不过去的一道坎，无论是应付面试或者是实际的应用都要经常和这个数据结构打交道。本文参考了很多前人的分析并由自己消化，最终呈现出来。