HashMap 是 Java 中常用的一种数据结构，它实现了 Map 接口，用于存储键值对。HashMap 的底层实现原理是数组和链表/红黑树，通过哈希函数将键映射到数组中的某个位置，如果位置上已经有元素，则使用链表进行存储。

HashMap 的扩容机制是 HashMap 中的重要的算法，它通过调整 HashMap 的容量来控制 HashMap 的大小，以减少空间浪费和提高查询效率。一般来说，每次扩容，HashMap 存储链表/红黑树的数组的长度都会变为 2 倍。在 HashMap 实现中，这个数组是一个成员变量 table。

为什么要这么设计？我们首先要知道一个好的 Hash 函数至少应该满足什么条件：

  1. 均匀分布 ：经过哈希函数的计算，每个元素应该尽可能均匀地分布到数组中。具体地说，要保证每个 table 下标都有可能命中
  2. 快速计算 ：哈希函数的计算应该尽可能高效
  3. 离散分布 ：哈希函数的计算结果应该尽可能的离散，减少碰撞。具体地说，要保证每个 table 下标中的元素数量都差不多

带着这些条件，我们看看 Java 的 HashMap 具体是怎么实现的。 以下源码来自 JDK 21。

深入源码看看 HashMap 的 put 方法

我们知道，只有往 HashMap 中添加元素，才会触发扩容机制。因此我们需要从 put 方法出发，看看它具体做了什么。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with {@code key}, or
 *         {@code null} if there was no mapping for {@code key}.
 *         (A {@code null} return can also indicate that the map
 *         previously associated {@code null} with {@code key}.)
 */
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

看来 put 和 putIfAbsent 等方法底层都是调用了 putVal 这个方法，那我们先跳过 hash() 这个方法，继续往下看：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Implements Map.put and related methods.
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 如果 table 为空，或者 table 的长度为 0，那么就需要进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 如果当前 table 中 i 位置为空，直接插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
      ...
    }
    ...
}

注意这段代码 i = (n - 1) & hash ，这里是计算元素在 table 数组中的位置，n 是 table 数组的长度。

为什么是 2 的幂次方？

我们知道，table 数组的长度是 2 的幂次方。这里的 (n - 1) & hash 是为了保证计算出来的位置在数组的范围内，也就是说，i = (n - 1) & hash 等价于 i = hash % n 。

前面我们说过， 均匀分布 是一个好的哈希函数的特点。这就要求我们每次通过 hash 计算出来的下标要尽可能的覆盖到整个数组，不能超出数组的范围。那么最直观的方式就是直接取模 i = hash % n。但是在计算机中，取模运算是比较耗时的，这不符合 快速计算 这一 hash 函数要求；而相对应的，位移运算可以说是效率最高的运算方式之一了。

如果我们以 table 数组的长度 n 是 2 的幂次方为前提，那么 (n - 1) & hash 就相当于 hash % n，我举个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// hash 指是 int 类型，因此有 32 位，我们假设下方是我们待计算的 hash 值
h = 0b 1101 1010 1011 1100 1011 1101 1010 1011

// 假设 table 的长度是 16，即 n = 16，那么
n = 0b 0000 0000 0000 0000 0000 0000 0001 0000

// 如果直接计算 hash % n，那么其余数显然只和后 4 位有关，即
i = h % n = 0b 0000 0000 0000 0000 0000 0000 0000 1011

// 我们再来看看 n - 1 的二进制表示，它将后面的数位全部置为 1，即
n - 1 = 15 = 0b 0000 0000 0000 0000 0000 0000 0000 1111

// 这就能很容易看出，(n - 1) & hash 就相当于 hash % n，即
h = 0b 1101 1010 1011 1100 1011 1101 1010 1011
&
n - 1 = 0b 0000 0000 0000 0000 0000 0000 0000 1111
=
i = 0b 0000 0000 0000 0000 0000 0000 0000 1011

因此，我们可以说 (n - 1) & hash 这段计算 hash 落点的代码，同时实现了 HashMap 中 hash 函数的 快速计算 和 均匀分布 的两种能力。

保证 hash 映射的离散分布

上一节我们谈到，通过 (n - 1) & hash ，我们高效地获取了 hash 映射的落点。但是，这只是保证了 hash 映射的 均匀分布 （每个 table 下标都有可能命中），而没有保证 hash 映射的 离散分布 （每个 table 下标命中的元素数量都差不多）。那么 HashMap 又是怎么做才保证了 hash 映射的 离散分布 的呢？

在上文 h = 0b 1101 1010 1011 1100 1011 1101 1010 1011 的例子中，我们只取了 hash 的后 4 位 0b 1011 来计算 hash 落点，前 28 位没有参与计算。这显然是不合理的，因为这相当于我们只拿了 hash 的很小一部分来代表整个 hash 值对应的元素。少数人怎么能代表多数人呢？🤯

那么 JDK 是怎么解决这个问题的呢？我们来看看先前跳过的 hash() 函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash
 * to lower.  Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这段代码就相对清晰了，(h = key.hashCode()) ^ (h >>> 16) 所做的事情就是将 hash 的高 16 位和低 16 位进行 异或 运算，这样就能保证 hash 的高位和低位都参与到计算中，进而保证了 hash 映射的 离散分布 。

再拿之前的例子来看：

1
2
3
4
5
6
7

// 假设 key.hashCode() 是我们先前使用的 hash 值
h = 0b 1101 1010 1011 1100 1011 1101 1010 1011
^
h >>> 16 = 0b 0000 0000 0000 0000 1101 1010 1011 1100
=
0b 1101 1010 1011 1100 0110 0111 0001 0111

这么算完后，假设 table 的长度是 16，那么 0b 0111 才是真正参与计算的值，而不是之前的 0b 1011。这样就保证了 hash 映射的 离散分布 。

你可能会问，为什么是 16 位？这主要是因为绝大多数的 HashMap table 长度是不会超过 $2^{16} = 65536$ 的。因此这样的计算足够满足大多数场景下，尽可能公平地考虑高位（本来不参与 hash 的）和低位（本来就要参与 hash 的）对 hash 的影响。

本文参考文章：