HashMap

内部结构

HashMap 本质上是一个哈希表（hash table），采用数组+链表/红黑树结构（JDK 1.8 之前是数组+链表），示意图如下所示：

HashMap 内部对应的变量如下所示：

transient Node<K,V>[] table;
transient int size;        // key-value 的总个数

散列

如果我们要向 HashMap 中插入一个 entry，首先要做的就是根据 key 将 entry 散列到对应的 hash slot。这个动作分为两步进行。

一是求 key 的 hash 值， HashMap 通过内部的 hash() 方法来完成，源码如下所示：

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

二是对 hash 值进行散列，源码如下所示：

// putVal() method
int i = (table.length - 1) & hash;    // 进行按位与，而非对 table.length 取模

注意 hash() 是允许 key 为 null 的，如果为 null ，则返回 0。

扩容机制

扩容机制的目的就是减少哈希碰撞，其方法就是增加 hash slot 的数量，但在实现时需要考虑以下两个问题：

• 什么时候扩容
• 如何兼顾空间和时间的效率

对于何时扩容，最简单的回答就是：当 table.length > threshold 时，调用 resize() 方法将 table 变为原来的 2 倍大。

对于如何兼顾空间和时间， HashMap 的做法是：如果一个哈希桶内的 entry 数量 binCount >= treeify_threshold - 1 时，就调用 **treeifyBin()** 方法。

默认设置

上面在介绍扩容机制时，并未说明具体的阈值数额，你可以自己在实例化 HashMap 对象时传入，也可以使用默认的设置。

首先，threshold = capacity * loadFactor，其中 capacity = table.length，而 loadFactor 为一个 float 类型常量。capacity 的默认初始化值为 16，loadFactor 的默认初始化值为 0.75，因此默认的初始扩容阈值为 12，即当 table.length > 12 时，就会进行第一次扩容。

树形化

如上所言，如果 binCount >= treeify_threshold - 1，就会调用 treeifyBin() 方法，其中 treeify_threshold 的默认设置为 8 ，但要想真正树形化，还需要满足 table.length >= MIN_TREEIFY_CAPACITY（默认值为 64），否则会执行 resize() 方法扩容。

key 的唯一性与 null

对于 HashMap 来说，key 的唯一性是由 hashCode() 和 equals() 方法保证的，key 和 value 都允许为 **null** 。

扩容的稳定性

最后需要指出的是， HashMap 扩容前后，哈希桶内 entry 的先后顺序是不变的，即扩容是稳定的，你可以查看 resize() 方法的源码，这里不再赘述。