Java HashMap 的实现分析

发表于 2021-01-30 更新于 2021-03-30 分类于 1- 编程相关， Java 阅读次数： Valine：

在 Java 中，Map 和 Set 接口，最常用的实现类分别为 HashMap 和 HashSet，而 HashSet 的背后实际上就是 HashMap。因此，为探究 Java 实现 Hash 集合类的方法，在这里对 Java HashMap 的源码进行简单的分析。

在 HashMap 中，实际上每个 entry 元素（key-value 对）是存放在一个个的 node 中的，Node 的结构定义在一个静态内部类中，如下：

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

HashMap 中提供了一个静态工具方法 hash() 来计算键值对对应的 Node 中的 int 变量 hash 的值，代码如下：

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

可以看到，return 首先判断 key 是否为 null，如果是 null 对应的 hash 值直接为 0，如果不为 0，hash() 方法将对 hashCode 的低 16位值进行处理，将低16位变为高16位于低16位异或的结果（Note: >>> 为无符号移位，即符号位也移动）。

将键值对包装为 Node 对象后，HashMap 会将这些 node 存放在一个数组中，数组的声明如下：

1	transient Node<K,V>[] table;

每个数组元素称为一个 bucket。数组的大小称为 capacity，在 HashMap 的构造函数或 put 函数中会对数组进行初始化。

随着不断向 map 中添加元素，数组的 capacity 需要动态的进行调整，这里使用一个 load factor 参数来表述 map 中元素个数与数组 capacity 的关系， capacity * (load factor) == Map.size, 即数组大小乘上 load factor 为 map 中元素个数。当 map 中元素的个数超过上述限值的时候，HashMap 会增大 capacity 为原来的一倍（*2）。

将 key-value 对应的 node 放置在 Map 中数组的哪个位置(index)，使用公式 index = (n - 1) & hash 确定，由于 n 为 2 的整数次方，所以该公式的效果就是截取 hash 值的最后 k 位，作为index 值（k为 n 的指数，即 2^k = n， k 为整数）。这里也解释了前面不是直接使用 hashCode 值作为 node 的 hash 值，而是将高16位与低16位异或作为新的低 16 位值，从而让 hash 值的高位和低位都能反映到位号 index 上，以使得元素能够尽量更加均匀的分布在数组中。

上面的流程中，由于只取 hash 值的最后几位，会存在多个具有不同 hashCode 的对象对应到相同的位号的情况，这时，具有不同 hashCode 值但是计算出相同 index 值的元素以链表的形式连接，被放置在同一个 bucket 中（也叫 bin 中）。Java 8 后，对不同元素具有同一个 index 值的情况进行了优化，添加了一个阈值，当同一个 bin 中的 node 数量超过阈值时，会将链表存储结构变为红黑树结构。

上面的文字描述介绍了整个 HashMap 进行元素存储的过程，下面对重要的源码进行简单的分析。

上述分析中涉及的变量初始值定义如下：

// 默认容量大小，一定是 2的次方（a power of two）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 默认负载系数，为 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当 bin 中元素超过该阈值，bin 中存储结构由链表变为树
static final int TREEIFY_THRESHOLD = 8;
// 当 bin 中元素数目小于该阈值，bin 中元素存储结构变回 链表
static final int UNTREEIFY_THRESHOLD = 6;

上述描述的过程可以通过 put 函数更好的进行说明，具体的过程参看下面代码中的注释部分：

// public 的 put 函数
public V put(K key, V value) {
    // 使用 hash 方法计算 node 中的 hash 变量的值
    return putVal(hash(key), key, value, false, true);
}

/**
    * Implements Map.put and related methods.
    *
    * @param hash hash for key
    * @param key the key
    * @param value the value to put
    * @param onlyIfAbsent if true, don't change existing value
    * @param evict if false, the table is in creation mode.
    * @return previous value, or null if none
    */
// 底层调用的 put 函数
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // Step1：初始化。如果 map 的存储单元 table 还没有初始化，首先调用 resize 函数初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // Step2：放置键值对。
    // step2-1: 判断 hash 对应的位号上有没有元素, 如果没有直接放置一个 node 对象
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // step2-2: 如果键值对 hash 值对应的位号上已经有元素
    else {
        Node<K,V> e; K k;
        // step-a: 首先判断是否重复
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // step-b, 判断是一个 tree 还是 list
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 如果是 list
        else {
            // 找到 list 的最末尾元素
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果 list 的长度大于了阈值，将 list 变为 tree
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 判断 list 中的元素是否与添加元素相同
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 如果 e 不为空，说明要添加的键已经存在
        // 此时，根据 onlyIfAbsent 标志位判断是否需要更新 value 值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;    // 更新后返回原来的值
        }
    }
    ++modCount;
    // 如果大于 map 的 size 限制，
    // 调用resize() 函数，将 bucket 数组的容量扩大一倍
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

参考：