9.1 hash() 方法的原理

hash() 方法也叫扰动函数，使用扰动函数就是为了减少碰撞。

基于 JDK 1.8，扒一下 HashMap 的 hash() 方法的源码：

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

我们都知道，key.hashCode() 是用来获取键位的哈希值的，理论上，哈希值是一个 int 类型，范围是 [-2 ^ 31, 2 ^ 31 - 1]，也就是 [-2147483649, -2147483647]。前后加起来大概有 40 亿的映射空间，只要哈希值映射的比较均匀松散，一般是不会出现哈希碰撞的。

但是，40 亿长度的数组，内存是放不下的。HashMap 扩容之前的数组初始大小只有 16，所以这个哈希值是不能直接拿来用的，用之前要和数组的长度做取模运算，用的到的余数来访问数组下标才行。这其实也就解释了 HashMap 的长度为什么是 2 的幂次方。

取模运算有两处：

1. 往 HashMap 中 put() 的时候（调用 putVal() 方法）：

   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;
       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{
       	...
       }
   }
   

2. 从 HashMap 中 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;
       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) {
               if (first instanceof TreeNode)
                   return ((TreeNode<K,V>)first).getTreeNode(hash, key);
               do {
                   if (e.hash == hash &&
                       ((k = e.key) == key || (key != null && key.equals(k))))
                       return e;
               } while ((e = e.next) != null);
           }
       }
       return null;
   }
   

其中的 (n - 1) & hash就是取模运算，把哈希值和（数组长度 - 1）做 “与” 运算。

但是，取模运算符应该用 %，为什么要用 & 呢？

因为 & 比 % 运算符更加高效，并且当 b 为 2 的 n 次方时，存在这样一个公式：

a % b = a & (b - 1)

可以验证一下：假设 a = 14，b = 8，也就是 14 % 8 = 6；14 的二进制位是 1110，8 的二进制位是 1000，(b - 1) 的二进制位是 0111，1110 & 0111 = 0110 = 6。

这也正好解释了为什么 HashMap 的数组长度（length）要取 2 的整次方？

因为（数组长度 - 1）正好相当于一个 “低位掩码”，这个掩码的低位最好全是 1（比如：0111 的 低位就是 111），这样 & 操作才有意义，否则结果就肯定是 0，那么 & 操作就没有意义了。

位掩码：将整数的二进制表示法用作数据结构的方法就是位掩码（bitmask）；
低位掩码：2 的整数次幂 - 1 后的位掩码，相当于最高位变成 0，低位全为 1。

2 的整数次幂刚好是一个偶数，偶数 - 1 是奇数，奇数的二进制最后一位是 1，保证了 hash & (length - 1) 的最后一位可能是 0，也可能是 1（这取决于 hash 的值），也就是 & 运算后的结果可能为偶数，也可能为奇数，这样就可以保证哈希值的均匀性了。

& 操作的结果就是将哈希值的高位全部归零，只保留低位值，用来做数组下标访问。

假设某个哈希值为 10100101 11000100 00100101，用它来做取模运算：HashMap 的初始长度为 16（内部是数组），16 - 1 = 15，其二进制是 00000000 00000000 00001111（高位用 0 来补齐）：10100101 11000100 00100101 & 00000000 00000000 00001111 = 00000000 00000000 00000101

因为 15 的高位全部是 0，所以 & 运算后的高位结果肯定是 0，只剩下 4 个低位 0101，也就是十进制的 5，也就是将哈希值为 10100101 11000100 00100101 的键放在数组的第五位。

整明白了取模运算后，再次扒一下 put() 方法和 get() 方法的源码：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

它们在调用 putVal() 和 getNode() 方法之前，都会先调用 hash() 方法，然后将结果当做参数传给 putVal()：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

为什么取模运算之前要调用 hash() 方法呢？

如上图所示，某哈希值为 11111111 11111111 11110000 1110 1010，将它右移 16 位（h >>> 16），刚好是 00000000 00000000 11111111 11111111，再进行异或操作（h ^ (h >>> 16)），结果是 11111111 11111111 00001111 00010101。

异或（^）运算是基于二进制的位运算，采用符号 XOR 或者 ^ 来表示，运算规则是：同值取 0，异值取 1。

由于混合了原来哈希值的高位和低位，所以低位的随机性加大了（掺杂了部分高位的特征，高位的信息也得到了保留）。

结果再与数组长度 - 1（16 的二进制表示）做取模运算（hash & (n - 1)），得到的下标就是 00000000 00000000 00000000 00000101，也就是 5。

上文中假设的某个哈希值为 10100101 11000100 00100101，在没有调用 hash() 方法之前，与 15 做取模运算后的结果也是 5。现在将这个哈希值先调用 hash() 方法之后再做取模运算：00000000 10100101 11000100 00100101右移 16 位（h >>> 16）是 0000000 00000000 00000000 10100101，再进行异或操作（h ^ (h >>> 16)），结果是 00000000 10100101 00111011 10000000，也就是 0。结果再与数组长度 - 1 做取模运算，得到的是 00000000 00000000 00000000 00000000 00000000，也就是 0。

综上所述，hash() 方法是用来做哈希值优化的，把哈希值右移 16 位，也就正好是自己长度的一半，之后与原哈希值做异或运算，这样就混合了原哈希值中的高位和低位，增大了随机性。

换句话说，hash() 方法就是为了增加随机性，让数据元素更加均衡的分布，减少碰撞。

9.2 HashMap 底层数据结构

HashMap 是基于哈希表的 Map 接口的非同步实现，常见的数据结构有堆栈、队列、数组、链表和红黑树。

Java 中最基本的数据结构有两种：一种是数组，一种是引用。可以说其他所有的数据结构都可以从这两个最基本结构构造而来，当然 HashMap 也不例外。

HashMap 实际上是一个 “链表散列” 的数据结构，即数组和链表的结合体，所以说 HashMap 的底层其实就是一个数据结构，被称为哈希表结构，数组中的每一项又是一个链表。

当新建一个 HashMap 的时候，内部就会初始化一个数组。Entry 就是数组中的一个元素，每个 Map.Entry 其实就是一个key-value（键值对数据），每个节点包含当前元素的 hash、key、value 和指向下一个元素的引用，这就构成了链表。

01、JDK 1.7 和 JDK 1.8 中 HashMap 的区别

JDK 1.8 是对 HashMap 的重大革新。

JDK 1.7 中 HashMap 是由数组+链表（散列链表）组成的，但是在 JDK 1.8 中引入了一种新的数据结构—红黑树，所以 JDK 1.8 中的 HashMap 是由数组+链表+红黑树组成的。

同时，元素实例的名称也发生了改变，在 JDK 1.7 中叫 Entry，在 JDK 1.8 中叫做 Node（节点），因为红黑树中存储的数据全部是节点。

但是实际上，Node 节点实现了 Map.Entry 接口：

static class Node<K,V> implements Map.Entry<K,V> {
   final int hash;
   final K key;
   V value;
   Node<K,V> next;
   ...
}

02、JDK 1.8 中 HashMap 涉及的数据结构

1. 数组（位桶）

   transient Node<K,V>[] table;
   

2. 数组节点元素 Node<K, V> 实现了 Map.Entry 接口

   static class Node<K,V> implements Map.Entry<K,V> {
   	// hash值
       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) {
       	// 使用 == 比较的是内存地址，相等就返回 true
           if (o == this)
               return true;
           if (o instanceof Map.Entry) {
               Map.Entry<?,?> e = (Map.Entry<?,?>)o;
               // 使用 equals 比较的是值，只有 key 和 value 都相等才返回 true
               if (Objects.equals(key, e.getKey()) &&
                   Objects.equals(value, e.getValue()))
                   return true;
           }
           return false;
       }
   }
   

3. 红黑树 red-black Tree

   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 TreeNode<K,V> root() {
           for (TreeNode<K,V> r = this, p;;) {
               if ((p = r.parent) == null)
                   return r;
               r = p;
           }
       }
   }
   

03、JDK 1.8 为什么会引入红黑树？

在 JDK 1.7 中 HashMap 采用的是数组（也称为位桶） + 链表数据结构实现的，而数组的长度是固定的，在固定的长度里我们将每一个元素（键值对）通过 key 进行哈希计算得到对应的 hash 值，但是 hash 本身就存在概率性，也就是说两个不同的 key，比如 “张三” 和 “三张” 通过 hash 计算后，有一定的概率会得到相同的 hash 值，这个时候就会引发一个问题：hash 碰撞（也就是所谓的 hash 冲突），而链表的引入就是为了解决 hash 冲突的（拉链法解决哈希冲突）。

也就是说同一个 hash 值的 Node 都存储在一个链表中，在 JDK 1.7 中使用头插法（在 JDK 1.8 后使用尾插法），在插入时新来的值会占用原有值的位置，而原有值就顺推到了链表的下一个节点，因为写这段代码的作者认为后来插入的值被查找的可能性会更大些，可以提高查找的效率，所以使用了头插法。

那为什么引入红黑树呢？

当位于数组中同一个位置（也就是链表）中的元素较多时，意味着 hash 值相同的元素有很多时，全部加在同一个链表上，链表的长度过长，通过 key 值依次查找的效率会非常低，所以在 JDK 1.8 中引入了红黑树，也就是当数组中某一位置的链表长度大于等于阈值（8）时，将链表转换为红黑树，这样就提高了查找的效率。

链表：需要全部遍历元素才行，时间复杂度为 O(n)。
红黑树：访问性能近似折半查找，时间复杂度为 O(log n)。

红黑树是一种近似平衡的二叉树，其主要的优点就是"平衡"，即左右子树的高度几乎一致，以此来防止树退化为链表，通过这种方式来保证查找的时间复杂度为 O(log n)。

红黑树主要有几个特性：

1. 每个节点要么是红色，要么是黑色，但根节点永远是黑色；
2. 每个红色节点的两个子节点一定是黑色；
3. 红色节点不能连续（也就是说，红色节点的子节点和父节点都不能是红色的）；
4. 从任一节点到其子树中的每个节点的路径都包含相同数量的黑色节点；
5. 所有的叶子节点都是黑色的（这里的叶子节点其实就是上图中的“NIL”节点）。

JDK 1.8 中的 HashMap 是链表与红黑树共存的状态：

04、树化和反树化

当链表长度大于 8 的时候，链表就会变成红黑树；而当长度小于 6 的时候，会从红黑树变回链表。

为什么是 8 和 6 这两个阈值呢？

在 HashMap 的源码文档里，大概在 175 行处，有这么一段描述：

	 * Because TreeNodes are about twice the size of regular nodes, we
     * use them only when bins contain enough nodes to warrant use
     * (see TREEIFY_THRESHOLD). And when they become too small (due to
     * removal or resizing) they are converted back to plain bins.  In
     * usages with well-distributed user hashCodes, tree bins are
     * rarely used.  Ideally, under random hashCodes, the frequency of
     * nodes in bins follows a Poisson distribution
     * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
     * parameter of about 0.5 on average for the default resizing
     * threshold of 0.75, although with a large variance because of
     * resizing granularity. Ignoring variance, the expected
     * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
     * factorial(k)). The first values are:
     *
     * 0:    0.60653066
     * 1:    0.30326533
     * 2:    0.07581633
     * 3:    0.01263606
     * 4:    0.00157952
     * 5:    0.00015795
     * 6:    0.00001316
     * 7:    0.00000094
     * 8:    0.00000006
     * more: less than 1 in ten million

因为 TreeNodes 的大小约是常规节点的两倍，我们只在容器中包含足够的节点时才使用它们（见 TREEIFY_THRESHOLD）。当它们变的太小（由于删除或调整大小）时，它们被转换回普通的容器。在使用分布良好的用户 hashCodes 时，很少使用树容器。理想情况下，在随机 hashCodes 下容器中的节点遵循泊松分布，默认调整阈值为 0.75，参数平均值为 0.5，尽管由于调整粒度而存在很大的差异，忽略方差，列表大小 k 的预期出现次数为

(

e

x

p

(

−

0.5

)

∗

p

o

w

(

0.5

,

k

)

/

∗

f

a

c

t

o

r

i

a

l

(

k

)

)

(exp(-0.5) * pow(0.5, k) /* factorial (k))

(exp(−0.5)∗pow(0.5,k)/∗factorial(k))。

如果不设置退化的阈值，只能以 8 来树化与退化，那么 8 将成为一个临界值，时而树化，时而退化，这样会非常影响性能。

因此，需要设置一个比 8 小的退化阈值。

如果 TREEIFY_THRESHOLD = 7 的话，并没有比上面的情况好多少，仅仅相差 1 个元素，仍旧会在链表与树之间反复转化。

那为什么是 6 呢？源码中也说了，考虑到内存（树节点比普通节点内存大 2 倍，以及避免反复树化），所以，退化阈值最多为 6。

9.3 HashMap 默认初始化大小是多少？为什么是 2 的幂次方？

01、HashMap 初始值大小

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

DEFAULT_INITIAL_CAPACITY：table 数组的默认初始容量为 16，位运算 1 << 4效率高。

我们在创建 HashMap 的时候，阿里巴巴规范插件也会提示我们最好赋初值，而且最好是 2 的次幂：

但是，初始值为什么选择 16 呢？

因为选择 16 是为了位运算更加方便，位运算比乘法运算效率要高的多，而且选择 16 是为了服务于将 key 映射到 index 的算法：

int index = key.hashCode() & (length - 1);

在上面介绍的 hash() 方法中我们知道：计算数组的下标要先进行 key.hashCode() 来获取键位的哈希值，然后再与数组的长度 - 1 做取模运算，用得到的余数来做为数组的下标。

因为（数组长度 - 1）正好相当于一个 “低位掩码”，这个低位掩码的低位最好全部是1，这样 & 操作才有意义，否则结果就肯定是 0，& 操作就没有意义了。

例如：

十进制：201314
二进制：11 0001 0010 0110 0010

选择数组初始值 length 为 16，那么（length - 1）= 15：

十进制：15
二进制：1111

此时按位与得出下标索引 index 值：

index = 11 0001 0010 0110 0010 & 1111
index = 0010 = 2

从中可以看出来，选择长度为 16，length - 1 为 15，二进制位全为 1，这种情况下，所有 index 的结果就等同于 hashCode() 计算出的 hash 值的最后四位，只要输入的 key 本身分布均匀，hashCode() 计算得出的 hash 值就是均匀分布的，而 hash 算法的最终结果 index 就是均匀分布的，这就是为了实现均匀分布。

实现均匀分布，就是为了减少 hash 碰撞（冲突）的概率，并且提高了 hashMap 的查询速度。

02、为什么是 2 的幂次方？

那么既然 16 可以，是不是只要是 2 的整数次幂就可以呢？答案是可以的。

在上文的 hash() 方法中说过：取余操作（%）中，如果除数是 2 的幂次方则等价于其除数减一的与操作（&），也就是说 hash % length == hash & (length - 1) 的前提是 length 是 2 的 n 次方。并且采用二进制位操作 & ，相对于 % 能够提高运算效率，这就解释了 HashMap 的长度为什么是 2 的幂次方。

那为什么不选择 8、32 呢？

因为是 8 的话，容量太小会很容易触发 map 扩容机制，影响性能；如果是 32 的话稍微太大又会浪费资源，所以就使用 16 作为初始大小最为合适。

综上所述：

1. 为了减少 hash 的碰撞；
2. 提高 map 的查询效率；
3. 避免分配过小容易频繁扩容（影响性能）；
4. 避免分配过大浪费资源。

9.4 HashMap 的负载因子为什么是 0.75？

JDK 1.8 中的 HashMap 是用数组+链表+红黑树实现的，如果要想往 HashMap 中存放数据或者取数据，就需要确定数据在数组中的下标。

先把数据的键进行一次 hash：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

再做一次取模运算确定下标：

i = (n - 1) & hash;

哈希表这样的数据结构容易产生两个问题：

1. 数组的容量过小，经过哈希计算后的下标，容易出现冲突；
2. 数组的容量过大，导致空间利用率不高。

负载因子是用来表示 HashMap 中数据的填满程度：负载因子 = 填入哈希表中的数据个数 / 哈希表的长度。

这就意味着：

1. 负载因子越小，填满的数据就越少，哈希冲突的几率就减少了，但是浪费了空间，而且还会提高扩容的触发几率；
2. 负载因子越大，填满的数据就越多，空间利用率就越高，但哈希冲突的几率就变大了。

所以，就必须在 "哈希冲突" 与 "空间利用率" 之间有所取舍，尽量保持平衡，谁也不碍着谁。

HashMap 是通过拉链法来解决哈希冲突的（这个下面会详细介绍的），为了减少哈希冲突发生的概率，当 HashMap 的数组长度达到一个临界值时，就会触发扩容，扩容后会将之前小数组中的元素转移到大数组中，这是一个相当耗时的操作。

那么，这个临界值由什么来确定呢？

临界值 = 初始容量 * 负载因子

一开始，HashMap 的容量是 16，负载因子是 0.75：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final float DEFAULT_LOAD_FACTOR = 0.75f;

也就是说，当 16 * 0.75 = 12 时，会触发扩容机制。

为什么负载因子会选择 0.75 呢？为什么不是 0.8、0.6呢？

这跟统计学里的一个很重要的原理——泊松分布有关：。

具体是用这么一个公式来表示的：

等号的左边，P 表示概率，N表示某种函数关系，t 表示时间，n 表示数量。

在 HashMap 的源码文档里，大概在 175 行处，有这么一段描述：

	 * Because TreeNodes are about twice the size of regular nodes, we
     * use them only when bins contain enough nodes to warrant use
     * (see TREEIFY_THRESHOLD). And when they become too small (due to
     * removal or resizing) they are converted back to plain bins.  In
     * usages with well-distributed user hashCodes, tree bins are
     * rarely used.  Ideally, under random hashCodes, the frequency of
     * nodes in bins follows a Poisson distribution
     * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
     * parameter of about 0.5 on average for the default resizing
     * threshold of 0.75, although with a large variance because of
     * resizing granularity. Ignoring variance, the expected
     * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
     * factorial(k)). The first values are:
     *
     * 0:    0.60653066
     * 1:    0.30326533
     * 2:    0.07581633
     * 3:    0.01263606
     * 4:    0.00157952
     * 5:    0.00015795
     * 6:    0.00001316
     * 7:    0.00000094
     * 8:    0.00000006
     * more: less than 1 in ten million

大致意思就是：

因为 TreeNode（红黑树）的大小约为链表节点的两倍，所以我们只有在一个拉链已经拉了足够节点的时候才会转为 tree（参考TREEIFY_THRESHOLD）。并且，当这个 hash 桶的节点因为移除或者扩容后 resize 数量变小的时候，我们会将树再转为拉链。如果一个用户的数据的 hashcode 值分布得很均匀的话，就会很少使用到红黑树。

理想情况下，我们使用随机的 hashcode 值，负载因子为 0.75 的情况下，尽管由于粒度调整会产生较大的方差，节点的分布频率仍然会服从参数为 0.5 的泊松分布。链表的长度为 8 发生的概率仅有 0.00000006。

虽然这段话中提到了 0.75 这个负载因子，但是这并不是为什么负载因子等于 0.75 的真正答案。

为什么这样说呢？

因为这个负载因子是从 JDK1.8 引入的，而且还提到了 0.75。看完上面这段话的意思，会很容易就认为这其实就是阐述 0.75 是怎么来的了，然后就简单的把泊松分布与 0.75 的由来联系到 0.75 上去了。然而，这段话的本意其实更多的是表示 JDK1.8 中为什么拉链的长度超过 8 的时候会进行红黑树的转换。这个柏松分布的模型其实就是基于当负载因子为 0.75 时的模型去进行模拟演算的。

先来简单的说一下二项分布：

在做一件事情的时候，其结果的概率只有两种情况，类似于抛硬币，结果不是正面就是反面。

为此，我们做了 N 次实验，那么在每次实验中只有两种可能的结果，并且每次实验是独立的，不同实验之间互不影响，每次实验成功的概率都是一样的。

以此理论为基础，我们来做这样的实验：我们往哈希表中扔数据，如果发生哈希冲突就为失败，否则为成功。

由此可以设想，实验的哈希值是随机的，并且经过哈希运算的键都会映射到哈希表的地址空间上，那么这个结果也是随机的。所以，每次 put 的时候就相当于我们在扔一个 16 面（我们先假设默认长度为16）的骰子，扔骰子实验肯定也是相互独立的。碰撞发生就是扔了 n 次有出现重复数字。

然后，我们的目的是什么呢？

就是掷了 k 次骰子，没有一次是相同的概率，需要尽可能的大些，一般意义上我们肯定要大于 0.5 的。

于是，n 次事件里面，碰撞为 0 的概率由上面公式得：

这个概率值需要大于 0.5，我们认为这样的 hashmap 可以提供很低的碰撞率。所以：

我们对于该公式其实最想求的就是长度为 s 的时候，n 为多少次就应该进行扩容了？而负载因子则是

n

/

s

n/s

n/s 的值。所以推导如下：

可以得到：

这就是一个求 ∞⋅0函数极限的问题，这里我们先令

s

=

m

+

1

（

m

→

∞

）

s = m+1（m \to \infty）

s=m+1（m→∞），则可以转化为：

接着再令

x

=

1

m

（

x

→

0

）

x = \frac{1}{m} （x \to 0）

x=m1​（x→0） 则有：

所以：

考虑到 HashMap 的容量有一个要求：它必须是 2 的 n 次幂。当负载因子选择了 0.75 就可以保证它与容量的乘积为整数：

16 * 0.75 = 12
32 * 0. 75 = 24

除了 0.75，0.5~1 之间还有 0.625（5/8）、0.875（7/8）可选，从中位数的角度来说，挑 0.75 是比较完美的。另外，维基百科上说，拉链法（解决哈希冲突的一种）的负载因子最好限制在 0.7-0.8 以下，超过0.8，查表时的 CPU 缓存不命中（cache missing）会按照指数曲线上升。

综上，0.75 是个比较完美的选择。

9.5 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;
}

Node 节点类：

// 继承自 Map.Entry<K,V>
static class Node<K,V> implements Map.Entry<K,V> {
       final int hash;// 哈希值，存放元素到hashmap中时用来与其他元素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; }
        // 重写hashCode()方法
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
        // 重写 equals() 方法
        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;
        }
}

1. table：也称为位桶，就是 hashmap 中存储数据的数组；

2. bin：就是挂在数组上的链表；

3. binCount：表示发生 hash 冲突的链表上节点的个数，超过阈值 8 就有转化为红黑树的条件（前提是数组长度要 >= 64）；

4. TREEIFY_THRESHOLD ：8，链表转化为红黑树的阈值（前提条件是数组容量大于 64）；

5. TreeNode：红黑树；

   static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
           TreeNode<K,V> parent;  // 父
           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 TreeNode<K,V> root() {
               for (TreeNode<K,V> r = this, p;;) {
                   if ((p = r.parent) == null)
                       return r;
                   r = p;
          }
   }
   

6. initialCapacity： table 数组的默认初始容量为 16；1 << 4 位运算等于 16，因为位运算比乘法运算效率高的多；

7. UNTREEIFY_THRESHOLD : 6，链表长度小于等于 6，红黑树就有转化为链表的机会（反树化）；

8. MIN_TREEIFY_CAPACITY ：链表转化为红黑树时的前提条件，table 数组的最小长度阈值（或者说即使数组中某个链表的长度达到了阈值 8，也不会立即转换结构为红黑树，而是先判断数组长度是否大于 64：如果不足 64，首先是 resize 扩容数组大小为原数组的 2 倍；如果大于 64，那些长度大于阈值 8 的链表结构才会传话为红黑树）；

9. MAXIMUM_CAPACITY：数组的最大容量，1 << 30 左移 30 位；

10. loadFactory：负载因子，是控制数组存放数据的疏密程度。loadFactor 越趋近于 1，数组中存放的数据（entry）就越多，也就越密，会让链表的长度增加；loadFactor 越小，也就是越趋近于 0，数组中存放的数据（entry）就越少，也就越稀疏。

    默认初始值为 0.75f（也就是数组容量的占比为 75%），值太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。

    给定的默认容量为 16，在往 Map 中存放数据的过程中，当数组的容量达到 capacity * loadFactory = 16 * 0.75 = 12时，就会自动 resize 扩容。

11. threshold：衡量数组是否需要扩容的标准。threshold = capacity * loadFactor，当 Size >= threshold 的时候就要考虑对数组的扩容了。

9.6 HashMap 源码分析

01、构造方法

HashMap 中有四个构造方法：

// 默认构造函数。
public HashMap() {
   this.loadFactor = DEFAULT_LOAD_FACTOR; // all   other fields defaulted
}

// 包含另一个“Map”的构造函数
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);//下面会分析到这个方法
}

// 指定“容量大小”的构造函数
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

// 指定“容量大小”和“加载因子”的构造函数
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);
}

putMapEntries() 方法：

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
    	// 判断 table 是否已经初始化
        if (table == null) { // pre-size
        	// 未初始化，s 为 m 的实际元素个数
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            // 计算得到的 t 大于阈值，则初始化阈值
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 已经初始化，并且 m 元素个数大于阈值，进行扩容处理
        else if (s > threshold)
            resize();
        // 将 m 中的所有元素添加至 HashMap 中
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

02、map.put() 方法

当我们往 HashMap 中 put 元素的时候，先根据 key 的 hashCode 重新计算 hash 值，根据 hash 值得到这个元素在数组中的位置（即下标索引）：如果数组在该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的元素放在链表的头部，先前加入的元素都向后顺延一个位置；如果数组在该位置上没有元素，就直接将该元素放到此数组的该位置上。

当系统决定存储 HashMap 中的 key-value（键值对）时，完全没有考虑 Entry 中 value 的值，仅仅只是根据 key 来计算决定每个 Entry 对象的存储位置。我们完全可以把 Map 集合中的 value 当成 key 的附属，当系统决定了 key 的存储位置后，value 随之保存在那里即可。

hash(int h) 方法根据 key 的 hashCode 值重新计算一次散列。此算法加入了高位计算，防止低位不变，高位变化时，造成的 hash 冲突。对于任意给定的对象，只要它的 hashCode() 返回值相同，那么程序调用 hash(int h) 方法所计算得到的 hash 值总是相同的。我们首先想到的就是把 hash 值与数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是 “模” 运算的消耗还是比较大的，在 HashMap 中是这样做的：调用 indexFor(int h，int length) 方法来计算该对象应该保存在 table 数组的哪个索引处：

1. 首先将（k、v）封装到 Node 节点对象当中；
2. 然后底层会调用 k 的 hashCode() 方法得出 hash 值。 通过哈希表函数/哈希算法，将 hash 值转换成数组的下标（用 hash 值与数组的长度进行取模运算或者位运算）。
3. 如果定位到的数组位置没有元素，就直接插入；
4. 如果定位到的数组位置有元素，就要和插入的 key 比较，如果 key 相同就直接覆盖。如果 key 不相同，就判断 p 是否是一个树节点，如果是就调用 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value) 方法将元素添加进去；如果不是就遍历链表插入到链表的头部（JDK1.7）或末尾（JDK1.8）。

在上图中有两个需要注意的点：

1. 直接覆盖之后应该就 return，不会有后续的操作；
2. 当链表长度大于阈值（默认为 8）并且 HashMap 数组长度超过 64 的时候才会执行链表转化成红黑树的操作，否则就只是对数组进行扩容。

前面我们扒过 put() 方法的源码，知道其内部是通过调用 putVal() 方法来实现的：

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 未进行初始化或者长度为 0，进行扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 如果在数组 table[(n - 1) & hash] 处的值为空，则新建一个 Node 节点，插入在该位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
    	// 此处表示有 hash 冲突，开始处理冲突（说明此位置有单向链表存在）
        Node<K,V> e; K k;
        // 检查第一个 Node，p 是不是要找的 hash 值，并逐步对每个节点上的 key 进行 equals
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 此处判断是否为树结构，如果是直接将 key-value 插入树节点中
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
        	// binCount 是记录当前链表发生冲突的节点数
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果发生冲突的节点数大于阈值 8，看是否需要改变冲突节点的存储结构；
                    // treeifyBin 判断当前 HashMap 数组的长度，
                    // 如果不足 64，只对数组 table 进行 resize 扩容，暂且不对冲突节点达到 8 的链表进行结构转换
                    // 如果当扩容后数组 table 的长度达到了 64 后，再将冲突节点数达到 8 的链表的存储结构转化为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果有相同的 key 值就结束遍历，直接将该 key 的 value 值覆盖掉
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等，就跳出循环
                    break;
                // 用于遍历桶中的链表，与前面的 e = p.next 组合，可以遍历链表
                p = e;
            }
        }
        // 表示在桶中找到 key 值、hash 值与插入元素相等的节点
        if (e != null) { // existing mapping for key
        	// 记录 e 的 value
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 访问后回调
            afterNodeAccess(e);
            // 返回存在的 value 值
            return oldValue;
        }
    }
    // 增量
    ++modCount;
    // 如果当前大小大于阈值，新阈值 = table初始容量 * 0.75
    if (++size > threshold)
    	// 扩容 2  倍（新容量 = 旧容量 * 2）
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}

putVal() 方法中调用了 treeifyBin() 方法：

final void treeifyBin(Node<K,V>[] tab, int hash) {
	// 定义的变量：n 是数组长度，index 是索引
    int n, index; Node<K,V> e;
    // 这个 tab 指的是此 HashMap 中的数组，n 为数组长度，如果数组为 null 或者数组长度小于 64
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    	// 直接扩容
        resize();
    // 否则说明满足转化成红黑树的条件了（数组长度 > 64），通过按位与运算取得索引 index，并将该索引对应的 node 节点赋值给 e，e 不为 null 时
    else if ((e = tab[index = (n - 1) & hash]) != null) {
    	// 定义几个变量：hd 代表头节点，tl 代表尾节点
        TreeNode<K,V> hd = null, tl = null;
        do {
        	// 先把 e 节点转成 TreeNode 类型，并赋值给 p
            TreeNode<K,V> p = replacementTreeNode(e, null);
            // 如果尾节点为空，则说明还没有根节点
            // 这里可以想一下，这时的元素数目已经超过 8 个了，还没有尾节点的话，则说明还没有设置根节点
            if (tl == null)
            	// 设置根节点，把 p 赋值给根节点 hd
                hd = p;
            else {
            	// 这两步其实就是 我指向你，你指向我的关系，为了形成双向链表
            	// 把 tl 设置为 p 的前驱节点
                p.prev = tl;
                // 把 p 设置为 tl 的后继节点
                tl.next = p;
            }
            // 把首节点设置成 p 后，把 p 赋值给尾节点 tl，然后会再取链表的下一个节点，转成 TreeNode 类型后再赋值给 p，如此循环
            tl = p;
          // 取下一个节点，直到下一节点为空，也就代表这个链表遍历好了
        } while ((e = e.next) != null);
        // 用新生成的双向链表替代旧的单链表，其实就是把这个数组对应的位置重新赋值成新双向链表的首节点
        if ((tab[index] = hd) != null)
        	// 这个方法里就开始做各种比较，左旋右旋，然后把双向链表变成一个红黑树
            hd.treeify(tab);
    }
}

03、map.get() 方法

get() 方法的步骤大概是这样的：

1. 先调用 k 的 hashCode() 方法得出哈希值，并通过 hash 算法计算出当前 k 在数组中的下标；
2. 通过上一步哈希算法计算出数组的下标后，再通过数组下标快速定位到某个位置上，如果这个位置上什么也没有，则返回 null；如果这个位置上有单向链表，那么就拿着 k 与该链表上每一个节点的 k 进行 equals，如果所有的 equals() 方法返回的都是 false，则 get() 方法返回 null 值；如果其中一个 equals() 方法返回的是 true，那么此时该节点的 value 就是我们要找的对应 value 值了，get() 方法最终会返回这个 value。

前面我门也扒过了 get() 方法的源码，知道其内部其实是通过调用 getNode() 方法来实现的：

final Node<K,V> getNode(int hash, Object key) {
	// tab 是 Entry 对象数组，first 是tab 数组中经过散列的第一个位置
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 通过 hash 值与 (n - 1) 进行位运算得到下标索引，table[(n - 1) & hash]
    // 一条链上的 hash 值是相同的，所以默认得到的是头节点，first = tab[(n - 1) & hash]
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 判断第一个 Node 节点是不是要找的 node
        // 判断条件：hash 值相同、key 值相同
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 如果头节点不是要找的 Node 节点，就判断头节点指向的下一个 Node 节点
        if ((e = first.next) != null) {
        	// 在树中 get
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 在链表中 get
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
              // 此处做 do-while 循环判断该链表上所有节点，直到找到 key 值和 hash 值都相同的节点，然后返回
            } while ((e = e.next) != null);
        }
    }
    return null;
}

04、put()、get() 方法总结

HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象，HashMap 底层采用的是一个 Entry[ ] 数组来保存所有的 key-value（键值对）的。

1. 当需要存储一个 Entry 对象时，会根据 hash 算法来决定其在数组中的存储位置，如果位置上有链表，再根据 equals() 方法决定其在数组中该位置上的链表中的存储位置；
2. 当需要取出一个 Entry 对象时，也会根据 hash 算法找到其在数组中对应的位置，如果位置上有链表，再根据 equals() 方法从该位置上的链表中取出该 Entry 对象的 value 值。

9.7 HashMap 的扩容机制

我们都知道，数组一旦初始化大小就无法改变了，所以就有了 ArrayList 这种动态数组，可以自动扩容。

HashMap 的底层用的也是数组。向 HashMap 里不断地添加元素，当数组无法装载更多元素时，就需要对数组进行扩容，以便装入更多的元素。

但是，数组是无法自动扩容的，所以如果要扩容的话，就需要新建一个大的数组，然后把小数组的元素复制过去。

HashMap 的扩容是通过 resize() 方法来实现的，JDK 8 中引入了红黑树，与 JDK 7 相比比较复杂。先来扒一下 JDK 7 中 resize() 方法的源码：

// newCapacity 为新的容量
void resize(int newCapacity) {
    // 小数组，作为临时过渡
    Entry[] oldTable = table;
    // 扩容前数组的容量
    int oldCapacity = oldTable.length;
    // MAXIMUM_CAPACITY 为最大容量，2 的 30 次方 = 1<<30
    if (oldCapacity == MAXIMUM_CAPACITY) {
        // 容量调整为 Integer 的最大值 0x7fffffff（十六进制）=2 的 31 次方-1
        threshold = Integer.MAX_VALUE;
        return;
    }

    // 初始化一个新的数组（大容量）
    Entry[] newTable = new Entry[newCapacity];
    // 把小数组的元素转移到大数组中
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    // 引用新的大数组
    table = newTable;
    // 重新计算阈值
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

这里的左移 <<< 表示二进制数会变成原来的 2 倍、4 倍、8 倍。

transfer() 方法用来转移，将小数组的元素拷贝到新的数组中：

void transfer(Entry[] newTable, boolean rehash) {
    // 新的数组容量
    int newCapacity = newTable.length;
    // 遍历小数组
    for (Entry<K,V> e : table) {
        while(null != e) {
            // 拉链法，相同 key 上的不同值
            Entry<K,V> next = e.next;
            // 是否需要重新计算 hash
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            // 根据大数组的容量和键的 hash 计算元素在数组中的下标
            int i = indexFor(e.hash, newCapacity);

            // 同一位置上的新元素被放在链表的头部
            e.next = newTable[i];

            // 放在新的数组上
            newTable[i] = e;

            // 链表上的下一个元素
            e = next;
        }
    }
}

e.next = newTable[i]使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置。这样先放在一个索引上的元素终会被放到链表的尾部（如果发生 hash 冲突的话），这点和 JDK 1.8 有区别。

注意：在旧数组中同一个链表上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。

如果不明白这句话什么意思的话，就接着往下看：

假设 hash 算法就是简单的用键的哈希值（是一个 int 值）和数组大小取模，也就是 hashCode % table.length。

这里我们继续假设：

1. 数组 table 的长度为 2；
2. 键的哈希值为 3、7、5。

取模运算后，哈希冲突都到了 table[1] 上了，因为余数为 1。那么扩容前是这样的：

小数组的容量为 2，key 3、7、5 都在 table[1] 的链表上。

现在假设负载因子 loadFactor 为 1，也就是当元素的实际大小大于 table 的实际大小时进行扩容。

扩容后的大数组容量为 4。哈希值与数组长度取模后：

1. key 3 取模后是 3（3 % 4 = 3），放在 table[3] 上；
2. key 7 取模后是 3（7 % 4 = 3），放在 table[3] 上的链表头部；
3. key 5 取模后是 1（5 % 4 = 1），放在 table[1] 上。

按照预期，扩容后的 7 仍然应该在 3 这条链表的后面，但是实际上，7 跑到了 3 这条链表的头部了。针对 JDK 7 中的这个情况，JDK 1.8 做了一些优化：

n 为 table 的长度，默认值为 16。

1. n-1 也就是二进制的 0000 1111 = 15；
2. key1 哈希值的最后 8 位为 0000 0101；
3. key2 哈希值的最后 8 位为 0001 0101（和 key1 不同）；
4. 做与运算后发生了哈希冲突，索引都在（0000 0101）上。

扩容后为 32。

1. n-1 也就是二进制的 0001 1111 = 31，扩容前是 0000 1111 = 15；
2. key1 哈希值的低位为 0000 0101；
3. key2 哈希值的低位为 0001 0101（和 key1 不同）；
4. key1 做与运算后，索引为 0000 0101；
5. key2 做与运算后，索引为 0001 0101。

新的索引就会发生这样的变化：

1. 原来的索引是 5（0 0101），扩容后的索引是 21（1 0101）= 5 + 16（原来的索引 + 原来的容量）；
2. 原来的容量是 16，扩容后的容量是 32；

也就是说，JDK 1.8 不需要像 JDK 1.7 那样重新计算 hash，只需要看原来的 hash 值新增的那个 bit 是 1 还是 0 就OK了：是 0 的话就表示索引没变；是 1 的话索引就变成了 "原索引 + 原来的容量"。

JDK 1.8 的这个设计非常巧妙，既省去了重新计算 hash 的时间，同时由于新增的 1 位是 0 还是 1 是随机的。所以扩容的过程可以均匀地把之前的节点分散到新的位置上。

接着来扒一下 JDK 1.8 中 resize() 方法的源码：

final Node<K,V>[] resize() {
	// 未扩容前的数组
    Node<K,V>[] 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;
        }
        // 没有超过最大值，新数组容量就扩充为旧数组的 2 倍
        // 前提：旧数组长度>=16；新数组长度<最大值
        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
        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);
    }
    // 这里通过扩大 2 倍后的 newCap * loadFactor 计算得出新的阈值
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    // 新建一个数组，容量为 newCap，也就是原数组容量的 2 倍
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 将小数组复制到大数组中
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
        	// 新建 Node 节点
            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
                	// 链表优化，重新 hash 的代码块
                    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;
}

从上面代码中我们可以看出，扩容大致分为两步：

1. 扩容：创建一个新的 Entry 空数组，长度是原数组的 2 倍；
2. rehash：遍历原数组中的所有数据，通过 hash 算法，重新计算出所有数据的下标索引，进行分配存储位置。

但是！为什么要重新 Hash 计算下标呢？不能直接复制过去吗？

其实原理很简单：因为数组长度扩大后，Hash 的规则也随之改变了index = key.HashCode() & (Length - 1)。

9.8 HashMap 解决 hash 冲突的办法？

解决 Hash 冲突的方法有这么几个：

1. 开放定址法：也称为线性探测再散列法，基本思想就是：如果 p = hash（key）出现冲突时，则以 p 为基础，再次 hash，p1 = hash（p），如果 p1 再次出现冲突，则以 p1 位基础，再次 hash，以此类推，直到找到一个不冲突的哈希地址 pi。因此开放定址法所需要的 hash 表的长度要大于所需要存放的元素，而且因为存在再次 hash，所以只能在删除的节点上做标记，而不能真正删除结点。
2. 再哈希法：双重散列、多重散列，提供多种不同的 hash 函数，当 r1 = hash1（key1）发生冲突时，再计算第二种算法 r2 = hash2（key1），直到没有冲突为止。这样虽然不易产生堆集，但增加了计算的时间。
3. 链地址法：也称拉链法，将哈希值相同的元素构成一个同义词的单链表并将哈希表的头指针存放在哈希表的第 i 个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。
   将链表和数组相结合，也就是说创建一个链表数组，数组中每一格就是一个链表。如果遇到哈希冲突，则将冲突的值加到链表中即可。
4. 建立公共溢出区：将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。

HashMap采用的是链地址法（即拉链法）。

9.9 为什么 JDK 1.8 之前使用头插法，JDK 1.8 之后改成了尾插法？

头插法：就是每次在一个链表中 put() 新值时，新的键值对会占用头指针指向的旧数据的位置，也就是说新来的值会占用原有值的位置，而原有值就顺推到了链表的下一个节点，因为写这段代码的作者认为后来插入的值被查找的可能性会更大些，可以提高查找的效率，所以使用了头插法。

尾插法：单从字面理解就是新插入的值会依次插入链表的下一个位置，不会改变原来所有数据的位置。

那为什么 JDK 1.8 之前使用头插法，JDK 1.8 之后改成了尾插法？

我们先来看一个例子：现在往一个容量大小为 2 的数组中 put() 两个值，负载因子默认为 0.75，而 2 * 0.75 = 1.5，取整为 1。显然，当 put() 第二个值的时候，数组就要触发 resize() 扩容机制了。

现在我们要在容量为 2 的容器里面用 “不同线程” 插入 A(K1, V1)、B(K2, V2)、C(K3, V3)，在 resize() 之前打个断点，那就意味着数据都插入了，但是还没有扩容，那么扩容前可能会出现这样的情况：

由此可见，链表的指向为：A->B->C。

因为 resize() 方法的扩容方式，在 JDK 1.8 前使用的是单链表的头插法，同一位置上的新元素总是会被放在链表的头部位置。如果发生扩容，在旧数组中同一个 Entry 单链表上的元素，通过 rehash 重新计算每个 Entry 的索引位置后，有可能被放到新数组中的不同位置上：

由此可见，不光是元素的位置可能发生改变，同一个链表中的引用指向顺序也可能发生改变：原本是 A 指向 B，而现在则是 B 指向了 A。但是 A 在 put() 进旧数组中的时候，A 元素会存储当前键值对数据中的 hash、key、value 和 指向 B 元素的引用，而现在重新计算后，B 指向了 A，说明 B中也有了指向 A 元素的引用，所以一旦几个线程都调整完成，就可能出现环形链表的情况：

这个时候无论去哪个线程取值，都会发生一个悲剧：Infinite Loop（无限循环）。

那为什么 JDK 1.8 之后使用了尾插法？

在上面的头插法中我们知道：使用头插法会改变链表上元素的顺序，但是如果使用尾插法，在扩容后会保持链表元素原本的顺序，就不会出现环形链表的问题了。

就是说，原本 A 指向 B，在扩容后那个链表还是 A 指向 B，顺序和指向引用都不会改变：

总结：

1. JDK 1.8 之前在多线程操作 HashMap 的时候可能会引起死循环，原因是扩容转移前后，链表中元素的顺序混乱倒置，在转移过程中修改了原来链表中节点的引用关系。
2. JDK 1.8 之后在同样的多线程操作 HashMap 时，不会引起死循环，原因是在扩容转移过程中链表中节点指向顺序不会改变，仍然保持之前节点的引用关系。

9.10 HashMap 是线程不安全的

HashMap 线程不安全有三方面原因：多线程下扩容会死循环、多线程下 put 会导致元素丢失、put 和 get并发时会导致 get 到 null。

01、多线程下扩容会造成死循环

在上面的介绍中我们知道，HashMap 是通过拉链法来解决哈希冲突的，也就是当哈希冲突时，会将相同哈希值的键值对通过链表的形式存放起来。

JDK 1.7 时，采用的是头部插入的方式来存放链表的，也就是下一个冲突的键值对会放在上一个键值对的前面（同一位置上的新元素被放在链表的头部）。扩容的时候就有可能出现环形链表，造成死循环。

扒一下 JDK 1.7 中 resize() 方法的源码：

// newCapacity 为新的容量
void resize(int newCapacity) {
    // 小数组，作为临时过渡
    Entry[] oldTable = table;
    // 扩容前数组的容量
    int oldCapacity = oldTable.length;
    // MAXIMUM_CAPACITY 为最大容量，2 的 30 次方 = 1<<30
    if (oldCapacity == MAXIMUM_CAPACITY) {
        // 容量调整为 Integer 的最大值 0x7fffffff（十六进制）=2 的 31 次方-1
        threshold = Integer.MAX_VALUE;
        return;
    }

    // 初始化一个新的数组（大容量）
    Entry[] newTable = new Entry[newCapacity];
    // 把小数组的元素转移到大数组中
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    // 引用新的大数组
    table = newTable;
    // 重新计算阈值
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

transfer() 方法用来转移，将小数组的元素拷贝到新的数组中：

void transfer(Entry[] newTable, boolean rehash) {
    // 新的数组容量
    int newCapacity = newTable.length;
    // 遍历小数组
    for (Entry<K,V> e : table) {
        while(null != e) {
            // 拉链法，相同 key 上的不同值
            Entry<K,V> next = e.next;
            // 是否需要重新计算 hash
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            // 根据大数组的容量和键的 hash 计算元素在数组中的下标
            int i = indexFor(e.hash, newCapacity);

            // 同一位置上的新元素被放在链表的头部
            e.next = newTable[i];

            // 放在新的数组上
            newTable[i] = e;

            // 链表上的下一个元素
            e = next;
        }
    }
}

e.next = newTable[i]使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置。这样先放在一个索引上的元素终会被放到链表的尾部（如果发生 hash 冲突的话），这点和 JDK 1.8 有区别。

假如扩容前是这个样子的：

那么正常扩容后应该是这个样子的（JDK 1.7 中 index = key.hashcode & length）：

也就是说，扩容前到扩容后索引的变化是这样的：

假设现在有两个线程同时进行扩容：

① 线程 A 在执行到 newTable[i] = e; 时被挂起，此时在线程 A 中： e = 3、next = 7、e.next = null（在将小数组中的数据拷贝到大数组中时，从头节点开始拷贝，也就是从 3 开始）：

线程 B 开始执行，并且完成了数据转移：

此时，7 的 next 为 3，3 的 next 为 null。

② 随后，线程 A 获得 CPU 时间片后继续执行 newTable[i] = e，将 3 放入新数组对应的位置，执行完本次循环后线程 A 的情况如下：

执行下一轮循环，此时 e = 7，原本线程 A 中 7 的 next 为 5，但是由于 table 是线程 A 和线程 B 共享的，而线程 B 顺序执行完后，7 的 next 变成了 3，那么此时在线程 A 中，7 的 next 也为 3。

采用头部插入的方式，变成了这样：

这时也没什么问题，此时的 next = 3，e = 3。

这个结果需要看一下源码：

// 同一位置上的新元素被放在链表的头部
e.next = newTable[i];

// 放在新的数组上
newTable[i] = e;

// 链表上的下一个元素
e = next; 

1. 第一步：e.next = newTable[i];就是将 7 的 next 设为 3，此时 next = 3；
2. 第二部：newTable[i] = e;把7 放在新的数组上；
3. 第三步：e = next; 把 e 的值设为 next，此时 e = 3。

③ 进行下一轮循环，但此时由于线程 B 将 3 的 next 变成了 null，所以此轮循环应该是最后一轮了。

接下来当 A 线程执行完 e.next = newTable[i]，即 3.next = 7 后（相当于把 3 插入到链表的头节点）， 3 和 7 之间就相互链接了，执行完 newTable[i] = e 后，3 被头插法重新插入到链表中了：

这个时候就会出现 “套娃”，也就是 3 和 7 会不断地互相链接，而 5 也就成了 “弃婴”。

但是，在 JDK 1.8 中已经修复了这个问题，扩容是会保持链表原来的顺序（尾插法）。

02、多线程下 put 会导致元素丢失

正常情况下，当发生哈希冲突时，HashMap 是这样的（链表）：

但是多线程同时执行 put 操作的时候，如果计算出来的索引位置是相同的，就会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;

	// 步骤 ①：tab 为空则创建
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

	// 步骤 ②：计算 index，并对 null 做处理
    // 如果在数组 table[(n - 1) & hash] 处的值为空，则新建一个 Node 节点，插入在该位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
    	// 此处表示有 hash 冲突，开始处理冲突（说明此位置有单向链表存在）
        Node<K,V> e; K k;

		// 步骤 ③：节点 key 存在，直接覆盖 value
        // 检查第一个 Node，p 是不是要找的 hash 值，并逐步对每个节点上的 key 进行 equals
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;

		// 步骤 ④：判断该链是否为红黑树
        // 此处判断是否为树结构，如果是直接将 key-value 插入树节点中
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        
        // 步骤 ⑤：该链为链表
		else {
        	// binCount 是记录当前链表发生冲突的节点数
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果发生冲突的节点数大于阈值 8，看是否需要改变冲突节点的存储结构；
                    // treeifyBin 判断当前 HashMap 数组的长度，
                    // 如果不足 64，只对数组 table 进行 resize 扩容，暂且不对冲突节点达到 8 的链表进行结构转换
                    // 如果当扩容后数组 table 的长度达到了 64 后，再将冲突节点数达到 8 的链表的存储结构转化为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果有相同的 key 值就结束遍历，直接将该 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);
            // 返回存在的 value 值
            return oldValue;
        }
    }
    ++modCount;

	// 步骤 ⑦：超过最大容量->扩容
    // 如果当前大小大于阈值，新阈值 = table初始容量 * 0.75
    if (++size > threshold)
    	// 扩容 2  倍（新容量 = 旧容量 * 2）
        resize();
    afterNodeInsertion(evict);
    return null;
}

问题就出现在步骤②这里：

if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);

如果两个线程都执行了 if 语句，假设线程 A 先执行了 tab[i] = newNode(hash, key, value, null)，那 table 是这样的：

接着，线程 B 执行了 tab[i] = newNode(hash, key, value, null)，那 table 是这样的：

很明显，3 被干掉了。

03、put 和 get 并发时会导致 get 到 null

线程 A 执行 put 时，因为元素个数超出阈值而出现扩容，线程 B 此时执行 get，有可能导致这个问题。

再来扒一下 resize() 方法的源码：

final Node<K,V>[] resize() {
	// 未扩容前的数组
    Node<K,V>[] 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;
        }
        // 没有超过最大值，新数组容量就扩充为旧数组的 2 倍
        // 前提：旧数组长度>=16；新数组长度<最大值
        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
        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);
    }
    // 这里通过扩大 2 倍后的 newCap * loadFactor 计算得出新的阈值
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    // 新建一个数组，容量为 newCap，也就是原数组容量的 2 倍
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
}

线程 A 执行完 table = newTab;后，线程 B 中的 table 此时也发生了变化，此时去 get 的时候就会 get 到 null 值，因为这个时候元素还没有转移。

9.10 如何解决 HashMap 在多线程环境下存在的线程不安全问题？

解决 HashMap 在多线程环境下存在线程不安全问题有三个办法：

1. Collections.synchronizedMap(Map) 创建线程安全的Map集合；
2. HashTable；
3. ConcurrentHashMap

不过出于线程并发度的原因，一般都会舍弃前两个而使用 ConcurrentHashMap，它的性能和效率明显高于前两个。

01、Collections.synchronizedMap(Map) 创建线程安全的 Map 集合

在 Synchronized 内部维护了一个普通的对象 Map，还有互斥锁 mutex：

private static class SynchronizedMap<K,V>
        implements Map<K,V>, Serializable {
        private static final long serialVersionUID = 1978198479659022715L;

        private final Map<K,V> m;     // Backing Map
        final Object      mutex;        // Object on which to synchronize

        SynchronizedMap(Map<K,V> m) {
            this.m = Objects.requireNonNull(m);
            // 如果没有传入 mutex 参数，则赋值为当前 synchronizedMap 对象
            mutex = this; 
        }

        SynchronizedMap(Map<K,V> m, Object mutex) {
            this.m = m;
            this.mutex = mutex;
        }
        ...
}

在调用这个方法的时候需要传入一个 Map，可以看到有两个构造方法：如果传入了 mutex 参数，则将对象互斥锁赋值为传入的对象；如果没有传入 mutex 参数，则将对象互斥锁赋值为 this，也就是调用 synchronizedMap 对象，就是上面的 Map。

Collections.synchronizedMap(hashMap);
Collections.synchronizedMap(new HashMap<>(16));

创建出 synchronizedMap 之后，就可以对 map 进行操作了，这时的方法都是安全的：

Map<String, String> stringStringMap = Collections.synchronizedMap(hashMap);
stringStringMap.size();
stringStringMap.isEmpty();
stringStringMap.containsKey("青花椒");
stringStringMap.get("qhj");
stringStringMap.put("qhj", "青花椒");
stringStringMap.remove("qhj");
stringStringMap.clear();

扒一下这些操作的源码，会发现在操作 map 的时候，就会对方法上锁：

public int size() {
    synchronized (mutex) {return m.size();}
}
public boolean isEmpty() {
    synchronized (mutex) {return m.isEmpty();}
}
public boolean containsKey(Object key) {
    synchronized (mutex) {return m.containsKey(key);}
}
public boolean containsValue(Object value) {
    synchronized (mutex) {return m.containsValue(value);}
}
public V get(Object key) {
    synchronized (mutex) {return m.get(key);}
}

public V put(K key, V value) {
    synchronized (mutex) {return m.put(key, value);}
}
public V remove(Object key) {
    synchronized (mutex) {return m.remove(key);}
}
public void putAll(Map<? extends K, ? extends V> map) {
    synchronized (mutex) {m.putAll(map);}
}
public void clear() {
    synchronized (mutex) {m.clear();}
}

可以很清晰的看到，如果传入的是 HashMap 对象，其实也是对 HashMap 做的方法做了一层包装，里面使用对象锁来保证多线程场景下操作安全，本质也是对 HashMap 进行全表锁。

但是使用 Collections.synchronizedMap(Map) 方法，在竞争激烈的多线程环境下性能依然也非常差，所以也并不推荐使用。

综上所述，在调用 Collections.synchronizedMap(new HashMap<>());方法初始化 HashMap 时，内部对 Map 的操作全是基于 synchronized 同步锁代码块，所以在多线程下是安全的。

02、Hashtable

与 HashMap 不同之处就在于，HashTable 内部对数据的读取操作也都上了锁，几乎所有的添加、删除、查询方法都加了 synchronized 同步锁。

相当于给整个哈希表加了一把大锁，多线程访问的时候，只要有一个线程访问或者操作该对象，那其他线程只能阻塞等待需要的锁被释放。

在竞争激烈的多线程场景中性能会非常差，所以 Hashtable 不推荐使用。

扒一下 get() 方法的源码：

@SuppressWarnings("unchecked")
public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}

扒一下 put() 方法的源码：

public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }

    addEntry(hash, key, value, index);
    return null;
}

HashTable 是不允许键和值中出现 null 值的，而 HashMap 可以允许键和值均为 null 值。

为什么 HashMap 允许 key 和 value 为 null 值？

首先看一下 HashMap 的 key 和 value 为什么可以为 null 值：

// key
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// value
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

可以看出 HashMap 对 key 为 null 值时做了处理，通过 hash 计算的时候，会判断 key 如果为 null 值，直接返回 hash 结果为 0，所以一个 HashMap 中只允许有一个 null 值的 key，后续的键值对如果 key 为 null 的话，put 时会直接把原来的 value 覆盖替换掉。

为什么 Hashtable 不允许 key 和 value 为空值？

首先是因为 Hashtable 内部对 null 值的 key 和 value 做了异常处理。

因为 Hashtable 使用的是安全失败机制（fail-safe），这种机制会使你此时读到的数据不一定是最新的数据。

如果你使用的是 null 值，就会使其无法判断对应的 key 是不存在还是为空，因为无法再调用一次 contain(key) 来对 key 是否存在进行判断，这里与 ConcurrentHashMap 同理。

快速失败机制（fail-fast）

应用场景：快速失败机制（fail-fast）是 Java 中的一种机制，在的时候，如果遍历过程中对集合对象的内容进行了修改（增删改），则会抛出 ConcurrentModificationException（并发修改异常）异常。

原理：迭代器在遍历时直接访问集合中的内容，并且在遍历的过程中使用一个 modCount 变量：
在中有说过，使用 hashNext()/next() 方法遍历下一个元素前，都会先去检测当前 modCount 值是否为 ExpectedModCount 所预期的值，是的话就返回遍历；否则就抛出异常，终止遍历。

但是，如果集合发生变化时修改过的 modCount 值在判断 modCount != ExpectedModCount 之前又设置成了 ExpectedModCount，那么异常就不会抛出。

因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的 bug。

java.util 包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改），也算是一种安全机制了。

安全失败机制（fail-safe）

应用场景：java.util.concurrent 包下的容器都是安全失败的，可以在多线程下并发使用、并发修改。

原理：采用安全机制的集合容器，在遍历时不是直接在集合内容上访问，而是先将原有集合复制一份，在拷贝的这份集合上进行遍历。所以在遍历的过程中，其他线程对原集合无论做出怎样的修改，都跟迭代过程无关，所以不会触发 ConcurrentModificationException（并发修改异常）异常。

缺点：基于拷贝的内容的优点是避免了 ConcurrentModificationException（并发修改异常）异常，但是同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的拷贝集合，在遍历期间原集合做的任何修改迭代器都不知道。

03、ConcurrentHashMap

以上两种方法，由于都是对方法进行全表锁，所以在多线程环境下容易造成性能差的问题。在开发过程中大都是使用 ConcurrentHashMap，因为它的并发性效率相比前两者好很多。

戳链接。

9.11 HashMap 与 Hashtable、HashSet、TreeMap 的区别

01、HashMap 与 Hashtable 的区别

• key 和 value 是否可以为 null：HashMap 可以存储 null 的 key 和 value，但是 null 作为键只能有一个，null 作为值可以有多个；Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException 异常。

• 实现方式不同：Hashtable 继承了 Dictionary 类，而 HashMap 继承的是 AbstractMap 类。

• 初始化容量大小和扩容机制不同：
  ① 创建时如果不指定容量的初始值，Hashtable 默认的初始化大小为 11，之后每次扩容，容量变为原来的 2n + 1。HashMap 默认的初始化大小为 16，之后每次扩容，容量变为原来的 2 倍。
  ② 创建时如果指定了容量的初始值，Hashtable 会直接使用给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的 tableSizeFor() 方法保证），也就是说 HashMap 总是使用 2 的幂次方作为哈希表的大小。

  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;
  }
  

• 迭代器不同：Hashtable 的 Enumerator 不是快速失败机制（fail-fast），而 HashMap 的 Iterator 迭代器是快速失败机制（fail-fast）。

• 抛出异常不同：HashMap 在多个线程下增加、修改、删除元素时，会抛出 ConcurrentModificationException（并发修改异常）异常；而 Hashtable 则不会。

• 底层数据结构不同：JDK 1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树（转化前会判断：如果当亲数组的长度小于 64，那么会先进行数组扩容，而不是转化为红黑树），以减少搜索时间；Hashtable 没有这样的机制。

02、HashMap 与 HashSet 的区别

HashSet 底层就是基于 HashMap 实现的。HashSet 的源码非常少，因为除了 clone()、writeObject()、readObject() 是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

HashMap	HashSet
实现了 Map 接口	实现了 Set 接口
存储键值对	仅存储对象
调用 put() 方法向 map 中添加元素	调用 add() 方法向 set 中添加元素
HashMap 使用键（key）计算 hashcode	HashSet 使用成员对象来计算 hashcode 值，对于两个对象来说 hashcode 可能相同，所以使用 equals() 方法来判断对象的相等性

03、HashMap 与 TreeMap 的区别

TreeMap 和 HashMap 都继承自 AbstractMap，但是需要注意的是 TreeMap 还实现了 NavigableMap 接口和 SortedMap 接口：

实现 NavigableMap 接口让 TreeMap 有了对集合内元素搜索的能力。

实现 SortedMap 接口让 TreeMap 有了对集合中的元素根据键排序的能力，默认是按照 key 的升序排序的，不过我们也可以指定排序的。

9.12 HashMap 常见的遍历方式

以下内容是参考 guide 哥的文章：

随着 JDK 1.8 Streams API 的发布，HashMap 有了更多的遍历方式，但是应该选择哪种遍历方式也是值得思考的。

HashMap 遍历从大的方向来说可以分为 4 类：

1. 迭代器（Iterator）方式遍历；
2. For Each 方式遍历；
3. Lambda 表达式遍历（JDK 1.8）；
4. Streas API 遍历（JDK 1.8）。

但是每种类型下又有不同的实现方式，因此具体的遍历方式又可以分为 7 种：

1. 使用迭代器（Iterator）EntrySet 的方式进行遍历；
2. 使用迭代器（Iterator）KeySet 的方式进行遍历；
3. 使用 For Each EntrySet 的方式进行遍历；
4. 使用 For Each KeySet 的方式进行遍历；
5. 使用 Lambda 表达式的方式进行遍历；
6. 使用 Streams API 单线程的方式进行遍历；
7. 使用 Streams API 多线程的方式进行遍历。

01、常见的迭代方式

1、迭代器 EntrySet

/**
 * @author QHJ
 * @date 2022/10/24  12:14
 * @description: 迭代器 EntrySet
 */
public class HashMapTest1 {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "JRE");
        map.put(4, "Spring");
        map.put(5, "MyBatis");
        // 遍历
        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());
        }
    }
}

程序执行结果：

1
Java
2
JDK
3
JRE
4
Spring
5
MyBatis

2、迭代器 KeySet

/**
 * @author QHJ
 * @date 2022/10/24  12:45
 * @description: 迭代器 KeySet
 */
public class HashMapTest2 {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "JRE");
        map.put(4, "Spring");
        map.put(5, "MyBatis");
        // 遍历
        Iterator<Integer> iterator = map.keySet().iterator();
        while (iterator.hasNext()) {
            Integer key = iterator.next();
            System.out.println(key);
            System.out.println(map.get(key));
        }
    }
}

程序执行结果：

1
Java
2
JDK
3
JRE
4
Spring
5
MyBatis

3、ForEach EnreySet

/**
 * @author QHJ
 * @date 2022/10/24  12:47
 * @description: ForEach EnreySet
 */
public class HashMapTest3 {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "JRE");
        map.put(4, "Spring");
        map.put(5, "MyBatis");
        // 遍历
        for (Map.Entry<Integer, String> entry : map.entrySet()){
            System.out.println(entry.getKey());
            System.out.println(entry.getValue());
        }
    }
}

程序执行结果：

1
Java
2
JDK
3
JRE
4
Spring
5
MyBatis

4、ForEach KeySet

/**
 * @author QHJ
 * @date 2022/10/24  12:50
 * @description: ForEach KeySet
 */
public class HashMapTest4 {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "JRE");
        map.put(4, "Spring");
        map.put(5, "MyBatis");
        // 遍历
        for (Integer key : map.keySet()){
            System.out.println(key);
            System.out.println(map.get(key));
        }
    }
}

程序执行结果：

1
Java
2
JDK
3
JRE
4
Spring
5
MyBatis

5、Lambda

/**
 * @author QHJ
 * @date 2022/10/24  12:52
 * @description: Lambda
 */
public class HashMapTest5 {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "JRE");
        map.put(4, "Spring");
        map.put(5, "MyBatis");
        // 遍历
        map.forEach((key, value) -> {
            System.out.println(key);
            System.out.println(value);
        });
    }
}

程序执行结果：

1
Java
2
JDK
3
JRE
4
Spring
5
MyBatis

6、Streams API 单线程

/**
 * @author QHJ
 * @date 2022/10/24  12:53
 * @description: Streams API 单线程
 */
public class HashMapTest6 {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "JRE");
        map.put(4, "Spring");
        map.put(5, "MyBatis");
        // 遍历
        map.entrySet().stream().forEach((entry) -> {
            System.out.println(entry.getKey());
            System.out.println(entry.getValue());
        });
    }
}

程序执行结果：

1
Java
2
JDK
3
JRE
4
Spring
5
MyBatis

7、Streams API 多线程

/**
 * @author QHJ
 * @date 2022/10/24  12:55
 * @description: Streams API 多线程
 */
public class HashMapTest7 {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "JRE");
        map.put(4, "Spring");
        map.put(5, "MyBatis");
        // 遍历
        map.entrySet().parallelStream().forEach((entry) -> {
            System.out.println(entry.getKey());
            System.out.println(entry.getValue());
        });
    }
}

程序执行结果：

1
Java
2
JDK
3
JRE
4
Spring
5
MyBatis

02、性能测试

使用 Oracle 官方提供的性能测试工具 JMH（Java Microbenchmark Harness，JAVA 微基准测试套件）来测试这 7 中循环的性能。

首先引入 JMH 框架：

<!-- https://mvnrepository.com/artifact/org.openjdk.jmh/jmh-core -->
<dependency>
    <groupId>org.openjdk.jmh</groupId>
    <artifactId>jmh-core</artifactId>
    <version>1.23</version>
</dependency>
<!-- https://mvnrepository.com/artifact/org.openjdk.jmh/jmh-generator-annprocess -->
<dependency>
    <groupId>org.openjdk.jmh</groupId>
    <artifactId>jmh-generator-annprocess</artifactId>
    <version>1.23</version>
    <scope>provided</scope>
</dependency>

然后编写测试代码：

/**
 * @author QHJ
 * @date 2022/10/24  13:08
 * @description:
 */
@BenchmarkMode(Mode.AverageTime) // 测试完成时间
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 2, time = 1, timeUnit = TimeUnit.SECONDS) // 预热 2 轮，每次 1s
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS) // 测试 5 轮，每次 1s
@Fork(1) // fork 1 个线程
@State(Scope.Thread) // 每个测试线程一个实例
public class HashMapCycleTest {
    static Map<Integer, String> map = new HashMap() {{
        // 添加数据
        for (int i = 0; i < 100; i++) {
            put(i, "val:" + i);
        }
    }};

    public static void main(String[] args) throws RunnerException {
        // 启动基准测试
        Options opt = new OptionsBuilder()
                .include(HashMapCycleTest.class.getSimpleName()) // 要导入的测试类
                .output("/MyProjects/jmh-map.log") // 输出测试结果的文件
                .build();
        new Runner(opt).run(); // 执行测试
    }

    @Benchmark
    public void entrySet() {
        // 遍历
        Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Integer, String> entry = iterator.next();
            Integer k = entry.getKey();
            String v = entry.getValue();
        }
    }

    @Benchmark
    public void forEachEntrySet() {
        // 遍历
        for (Map.Entry<Integer, String> entry : map.entrySet()) {
            Integer k = entry.getKey();
            String v = entry.getValue();
        }
    }

    @Benchmark
    public void keySet() {
        // 遍历
        Iterator<Integer> iterator = map.keySet().iterator();
        while (iterator.hasNext()) {
            Integer k = iterator.next();
            String v = map.get(k);
        }
    }

    @Benchmark
    public void forEachKeySet() {
        // 遍历
        for (Integer key : map.keySet()) {
            Integer k = key;
            String v = map.get(k);
        }
    }

    @Benchmark
    public void lambda() {
        // 遍历
        map.forEach((key, value) -> {
            Integer k = key;
            String v = value;
        });
    }

    @Benchmark
    public void streamApi() {
        // 单线程遍历
        map.entrySet().stream().forEach((entry) -> {
            Integer k = entry.getKey();
            String v = entry.getValue();
        });
    }

    @Benchmark
    public void parallelStreamApi() {
        // 多线程遍历
        map.entrySet().parallelStream().forEach((entry) -> {
            Integer k = entry.getKey();
            String v = entry.getValue();
        });
    }
}

所有被添加了 @Benchmark 注解的方法都会被测试，测试结果如下：

其中 Units 为 ns/op 的意思是执行完成时间（单位为纳秒），而 Score 列为平均执行时间，± 符号表示误差。

从以上结果可以看到，两个 entrySet 的性能相近，并且执行速度最快，接下来是 stream，然后是两个 keySet，性能最差的是 KeySet。

所以说，entrySet 的性能比 keySet 的性能高出了一倍多，因此在开发中应该尽量使用 entrySet 来实现 Map 集合的遍历。

03、字节码分析

将测试代码通过 javac 编译成字节码来看：

//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by Fernflower decompiler)
//

package com.example;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;

public class HashMapTest {
    static Map<Integer, String> map = new HashMap() {
        {
            for(int var1 = 0; var1 < 2; ++var1) {
                this.put(var1, "val:" + var1);
            }

        }
    };

    public HashMapTest() {
    }

    public static void main(String[] var0) {
        entrySet();
        keySet();
        forEachEntrySet();
        forEachKeySet();
        lambda();
        streamApi();
        parallelStreamApi();
    }

    public static void entrySet() {
        Iterator var0 = map.entrySet().iterator();

        while(var0.hasNext()) {
            Entry var1 = (Entry)var0.next();
            System.out.println(var1.getKey());
            System.out.println((String)var1.getValue());
        }

    }

    public static void keySet() {
        Iterator var0 = map.keySet().iterator();

        while(var0.hasNext()) {
            Integer var1 = (Integer)var0.next();
            System.out.println(var1);
            System.out.println((String)map.get(var1));
        }

    }

    public static void forEachEntrySet() {
        Iterator var0 = map.entrySet().iterator();

        while(var0.hasNext()) {
            Entry var1 = (Entry)var0.next();
            System.out.println(var1.getKey());
            System.out.println((String)var1.getValue());
        }

    }

    public static void forEachKeySet() {
        Iterator var0 = map.keySet().iterator();

        while(var0.hasNext()) {
            Integer var1 = (Integer)var0.next();
            System.out.println(var1);
            System.out.println((String)map.get(var1));
        }

    }

    public static void lambda() {
        map.forEach((var0, var1) -> {
            System.out.println(var0);
            System.out.println(var1);
        });
    }

    public static void streamApi() {
        map.entrySet().stream().forEach((var0) -> {
            System.out.println(var0.getKey());
            System.out.println((String)var0.getValue());
        });
    }

    public static void parallelStreamApi() {
        map.entrySet().parallelStream().forEach((var0) -> {
            System.out.println(var0.getKey());
            System.out.println((String)var0.getValue());
        });
    }
}

可以看出，除了 Lambda 和 StreamsAPI 之外，通过迭代器循环和 for 循环遍历的 EntrySet 最终生成的代码是一样的，它们都是在循环中创建了一个遍历对象 Entry。

而 KeySet 的两种遍历方式的代码也是类似的。

所以，在使用迭代器或者 for 循环 EntrySet 时，它们的性能都是相同的，因为它们最终生成的字节码基本都是一样的；同理，keySet 的两种遍历方式也是类似的。

04、性能分析

EntrySet 之所以比 KeySet 的性能高是因为，KeySet 在循环时使用了 map.get(key)，而 map.get(key) 相当于又遍历了一遍 Map 集合去查询 key 所对应的值。

在使用迭代器或者 for 循环时，其实已经遍历了一遍 Map 集合了，因此再使用 map.get(key) 查询时，相当于遍历了两遍。

而 EntrySet 只遍历了一遍 Map 集合，之后通过Entry<Integer, String> entry = iterator.next()把对象的 key 和 value 值都放入到了 Entry 对象中。因此再获取 key 和 value 值时就无需再遍历 Map 集合，只需要从 Entry 对象中取值就可以了。

所以，EntrySet 的性能比 KeySet 的性能高出了一倍，因为 KeySet 相当于循环了两遍 Map 集合，而 EntrySet 只循环了一遍。

05、安全性测试

把以上的遍历分为四类进行测试：迭代器方式、For 循环方式、Lambda 方式和 Stream 方式。

1、迭代器方式

/**
 * @author QHJ
 * @date 2022/10/24  15:47
 * @description:
 */
public class HashMapSafeTest {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "JRE");
        map.put(4, "Spring");
        map.put(5, "MyBatis");

        Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Integer, String> entry = iterator.next();
            if (entry.getKey() == 1){
                System.out.println("del:" + entry.getKey());
                iterator.remove();
            }else{
                System.out.println("show:" + entry.getKey());
            }
        }
    }
}

程序执行结果：

del:1
show:2
show:3
show:4
show:5

迭代器中循环删除数据安全。

2、For 循环方式

/**
 * @author QHJ
 * @date 2022/10/24  15:47
 * @description:
 */
public class HashMapSafeTest {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "JRE");
        map.put(4, "Spring");
        map.put(5, "MyBatis");

        for (Map.Entry<Integer, String> entry : map.entrySet()) {
            if (entry.getKey() == 1){
                System.out.println("del:" + entry.getKey());
                map.remove(entry.getKey());
            }else{
                System.out.println("show:" + entry.getKey());
            }
        }
    }
}

程序执行结果：

For 循环中删除数据不安全。

3、Lambda 方式

/**
 * @author QHJ
 * @date 2022/10/24  15:47
 * @description:
 */
public class HashMapSafeTest {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "JRE");
        map.put(4, "Spring");
        map.put(5, "MyBatis");

        map.forEach((key, value) -> {
            if (key == 1){
                System.out.println("del:" + key);
                map.remove(key);
            }else{
                System.out.println("show:" + key);
            }
        });
    }
}

程序执行结果：

Lambda 循环中删除数据不安全。

Lambda 删除的正确方式：

// 根据 map 中的 key 去判断删除
map.keySet().removeIf(key -> key == 1);
map.forEach((key, value) -> {
    System.out.println("show:" + key);
});

程序执行结果：

show:2
show:3
show:4
show:5

由此可见，可以先试用 Lambda 的 removeIf 删除多余的数据，再进行

4、Stream 方式

/**
 * @author QHJ
 * @date 2022/10/24  15:47
 * @description:
 */
public class HashMapSafeTest {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "JRE");
        map.put(4, "Spring");
        map.put(5, "MyBatis");

        map.entrySet().stream().forEach(entry -> {
            if (entry.getKey() == 1){
                System.out.println("del:" + entry.getKey());
                map.remove(entry.getKey());
            }else{
                System.out.println("show:" + entry.getKey());
            }
        });
    }
}

程序执行结果：

Stream 循环中删除数据非安全。

Stream 循环的正确方式：

map.entrySet().stream().filter(m -> 1 != m.getKey()).forEach(entry ->{
    if (entry.getKey() == 1){
        System.out.println("del:" + entry.getKey());
    }else{
        System.out.println("show:" + entry.getKey());
    }
});

程序执行结果：

show:2
show:3
show:4
show:5

由此可见，可以使用 Stream 中的 filter 过滤掉无用的数据后，再进行遍历，这也是一种安全的操作集合的方式。

5、总结

我们不能在遍历中使用集合 map.remove() 来删除数据，这是非安全的操作方式，但是我们可以使用迭代器的 iterator.remove() 方法来删除数据，这是安全的删除集合的方式。

同样的，我们也可以使用 Lambda 中的 removeIf 来提前删除数据，或者使用 Stream 中的 filter 过滤掉要删除的数据进行循环，这样都是安全的。当然也可以在 for 循环前删除数据后，再遍历，这样也是安全的。

从综合性能和安全性来看，应该尽量使用迭代器（Iterator）来遍历 EntrySet 的遍历方式来操作 Map 集合，这样就既安全又高效了。