HashMap

HashMap 作为 Java 中最常用的键值对存储容器，在 JDK8 中迎来了重大优化，核心围绕存储结构、插入规则、哈希算法和扩容机制展开，相比 JDK7 大幅提升了高并发场景下的性能和稳定性。

一、核心差异总览

对比维度	JDK7 实现	JDK8 实现
存储结构	数组 + 链表	数组 + 链表 + 红黑树
链表插入方式	头插法（新节点放链表头部）	尾插法（新节点放链表尾部）
HASH 算法	复杂右移（4 次异或运算）	简化右移（仅 16 位高位异或）
扩容时机	插入节点前触发	插入节点后触发
扩容转移方式	逐个元素重新计算下标转移	按哈希高位批量分组转移（低位 + 高位）
潜在问题	多线程扩容可能导致死锁	解决死锁问题，性能更优

二、存储结构差异

1. JDK7：数组 + 链表

JDK7 的 HashMap 仅由「数组（哈希桶）+ 链表」组成：

• 数组：作为哈希表的主体，每个数组元素对应一个链表的头节点，用于快速定位哈希桶位置。
• 链表：用于解决哈希碰撞问题，当多个 key 计算出相同的数组下标时，会以链表形式存储在该哈希桶下。
• 缺陷：当链表过长时，查询效率会退化至 O (n)，大量哈希碰撞场景下性能较差。

2. JDK8：数组 + 链表 + 红黑树

JDK8 引入红黑树优化链表过长的问题，形成「数组 + 链表 + 红黑树」的混合结构：

• 红黑树特性（平衡二叉树的一种）：
  1. 调整规则比 AVL 树（完全平衡二叉树）宽松，插入 / 删除效率更高。
  2. 插入效率比链表低，但查询效率比链表高。查询效率为 O (logn)，介于链表（O (n)）和 AVL 树（O (logn)，调整成本更高）之间，是性能与效率的折中。
  3. 仅在链表长度达到阈值时触发转换，不影响少量数据的存储性能。
• 核心阈值（JDK8 内置常量）：
  1. TREEIFY_THRESHOLD = 8：当链表元素个数超过 8 时，链表自动转为红黑树。
  2. UNTREEIFY_THRESHOLD = 6：当红黑树节点个数小于 6 时，红黑树自动转回链表（避免少量节点时红黑树的调整成本高于查询收益）。

三、核心操作实现差异

在HashMap中，我们最常用的操作大概就是put与get了，来看看核心代码：

1. Put 操作（插入键值对）

JDK7 Put 核心逻辑

JDK7 的 Put 操作流程简洁，核心分为 3 步，采用头插法插入节点：

// 核心步骤伪代码
int hash = hash(key); // 1. 计算 key 的 hash 值
int i = indexFor(hash, table.length); // 2. 通过 indexFor 方法计算数组下标
table[i] = newNode; // 3. 头插法：将 newNode 加入链表，新节点直接覆盖数组下标，原链表挂在新节点后

• 头插法原因：无需遍历链表，插入效率高。
• 缺陷：多线程扩容时，头插法会导致链表反转，可能引发死锁。
• 特殊处理：key 为 null 的元素固定存在数组第 0 个位置，且仅允许一个 null key。

JDK8 Put 核心逻辑

jdk8中引入了红黑树，但并不是说链表并不存在，查阅源码，我们可以发现两个非常关键的值：

static final int TREEIFT_THRESHOLD=8;
static final int UNTREEIFT_THRESHOLD=6;

当链表的元素超过8时，会自动转成红黑树；当红黑树的节点数小于6时，变回链表。

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 {
        Node<K,V> e; K k;
        //key相等情况，e在最后处理
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //判断是红黑树的树节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //是链表结构 
       else {
            for (int binCount = 0; ; ++binCount) { //binCount是遍历链表过程中计数
                //遍历链表，循环到尾结点，把新元素加在尾部，break
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //判断是否大于变成树的阈值-1,7会变成8，变成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //找到相等元素也break
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //重复key
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

看完这段代码，我们就明白了为什么jdk8中使用的是尾插法。因为在判断是使用链表或红黑树的过程中，要判断是否超过8个元素，至少需要遍历一遍，所以使用尾插法，新元素可以直接插入在尾结点。

JDK8 的 Put 操作（putVal 方法）更严谨，采用尾插法插入节点，并支持红黑树插入：

1. 校验数组是否为空，为空则先扩容（resize()）。
2. 根据 hash 值计算数组下标，若该位置为空，直接插入新节点。
3. 若该位置已有节点，分 3 种情况处理：
   • 节点 key 与插入 key 相同：记录该节点，后续更新 value。
   • 节点是红黑树节点（TreeNode）：调用红黑树插入方法（putTreeVal）。
   • 节点是链表节点：遍历链表至尾部，用尾插法插入新节点；插入后判断链表长度是否超过 7（TREEIFY_THRESHOLD - 1），若是则转为红黑树（treeifyBin）。
4. 若存在重复 key，更新对应节点的 value 并返回旧值。
5. 插入成功后，判断元素数量是否超过扩容阈值，若是则触发扩容。

• 尾插法原因：遍历链表计数（判断是否转红黑树）时，已遍历至尾部，尾插法无需额外开销，同时避免了多线程扩容的死锁问题。

2. Get 操作（查询键值对）

JDK7 Get 核心逻辑

get操作就比较简单了，先找到数组的下标，再比较key是否和给定的key相同，不同则顺着链表找下一个，直到找到或为空。具体通过getEntry()方法，遍历比较hash值是否相等，比较key是否相等。

//key不为null,获取value
final Entry<K,V> getEntry(Object key) {
        if (size == 0) {//判断链表中是否有值
         //链表中没值,也就是没有value
            return null;
        }
       //链表中有值,获取key的hash值
        int hash = (key == null) ? 0 : hash(key);
        // 在“该hash值对应的链表”上查找“键值等于key”的元素
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            //判断key是否相同
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;//key相等,返回相应的value
             }
        return null;//链表中没有相应的key
}

JDK7 的 Get 操作（getEntry 方法）流程简单，仅支持链表查询：

1. 校验数组是否为空，为空则直接返回 null。
2. 计算 key 的 hash 值，通过 indexFor 方法获取数组下标。
3. 遍历该下标对应的链表，依次比较节点 hash 值和 key（== 或 equals），匹配成功则返回节点，否则返回 null。

• 查询效率：链表长度越短，效率越高，最坏情况 O (n)。

JDK8 Get 核心逻辑

get方法大体思路不变，计算下标，然后遍历，只不过是比jdk7中多加上一个判断是否用链表存储还是红黑树存储的步骤：

1. 计算 key 的 hash 值和数组下标，定位到对应哈希桶。
2. 若该位置节点直接匹配 key，返回节点。
3. 若不匹配，判断节点类型：
   • 链表节点：遍历链表查询，O (n)。
   • 红黑树节点：红黑树查找，O (logn)。
4. 未匹配到则返回 null。

• 优化点：红黑树大幅提升长链表场景下的查询效率。

3. Hash 算法差异

JDK7 Hash 算法（复杂）

JDK7 的 Hash 算法包含多次右移和异或运算，目的是让高位参与哈希计算，减少碰撞：

final int hash(Object k){
    int h = hashSeed;
    // 对 String 类型 key 做特殊哈希处理
    if(0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String)k);
    }
    h ^= k.hashCode();
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

• 关键：通过 4 次右移（20、12、7、4）和异或运算，将高位特征融入低位，减少哈希碰撞。

在这当中，暂且不看hash种子，可以看到计算中存在大量的右移操作，那么为什么要进行右移呢，这是考虑到了碰撞性问题。之前提到使用indexFor来计算数组下标：

static int indexFor(int h , int length){    
    return h & (length-1);
}

这里提一点，HashMap的长度一定是一个二的次方数，这点是在它的初始化和扩容中被限定的。这里在计算下表时，一个二的次方数减去1，能够保证它的二进制数的后几位数字全部是1，便于计算下标。

举个例子，HashMap长度为16，这样计算出的hash值与0000 1111做与运算，只需要取后四位，就实现了数组下标的计算。而与操作的计算速度比取余操作是要快上一些的。

回到上面，继续讲为什么要进行大量的右移操作，还是以长度为16来看，如果几个key计算出的hash值为：

1010 0110
0010 0110
0000 0110

我们发现，只要后四位一样，hash值都一样，碰撞性很高，所以这时要引入右移操作，让高位也能参与到与运算。让链表分散，减少链表长度。

JDK8 Hash 算法（简化）

JDK8 精简了 Hash 算法，仅保留 16 位高位右移异或，配合红黑树弥补性能损耗：

static final int hash(Object key) {
    int h;
    // key 为 null 时 hash 值为 0，否则将 hashCode 与高位 16 位异或
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

• 简化原因：数组下标计算仅使用 hash 值的低位，将高位 16 位与低位异或，既保留高位特征，又简化计算。
• 配合优化：红黑树提升了哈希碰撞场景下的查询效率，无需依赖复杂哈希算法减少碰撞。

4. 数组下标计算

JDK7 和 JDK8 均使用 h & (length - 1) 计算数组下标（替代取余运算，效率更高），前提是 HashMap 数组长度为 2 的幂次方（初始化和扩容时强制保证）：

• 原理：2 的幂次方减 1 的二进制形式为「末尾全 1」（如 16-1=15，二进制 1111），与 hash 值做与运算时，仅保留 hash 值的低位，快速定位数组下标。
• 示例：hash 值为 1010 0110，数组长度 16（length-1=15，二进制 0000 1111），与运算结果为 0000 0110，对应数组下标 6。

四、扩容机制差异

扩容是 HashMap 的核心耗时操作，目的是增大数组容量，减少链表长度，提升查询效率。默认扩容因子（负载因子）为 0.75，即当元素数量达到数组容量的 75% 时，触发扩容，容量翻倍。

扩容是对数组进行扩容，而不是链表或红黑树。在初始化时数组的默认长度是16，前面提到当存储的元素很多时会发生hash碰撞。我们扩容的目的是将长链表的长度减短，提高查询效率。

由于扩容的源码比较长，就不贴在这里，只列出核心思想。

1. JDK7 扩容机制

只有当数量大于阈值，且当前插入位置不为空时才会进行扩容，并且容量为原先2倍。

在将老的table转移到新的table时，需要重新计算数组的下标。

扩容后，重新计算下标。以从16位扩容到32位为例：

h      1010 0110
31     0001 1111
结果    0000 0110    （与之前相同）

h     1011 0110
31    0001 1111
结果  0001 0110    （与之前不同，相当于比之前加了16）

扩容后，数组下标可能改变，也可能不变。这时要看扩容的那一位的哈希值是1还是0，如果是1则不同，0则相同。但是在这个过程中，有可能造成死锁问题。

• 扩容时机：元素插入前，当元素数量 > 扩容阈值，且当前插入位置不为空时触发。
• 转移方式：逐个遍历旧数组元素，重新计算 hash 值和数组下标，将元素转移到新数组中（头插法）。
• 潜在问题：多线程下，头插法会导致链表反转，引发死锁；逐个转移效率较低。
• 下标变化：扩容后元素下标可能不变（hash 高位为 0）或变为「原下标 + 旧数组容量」（hash 高位为 1）。

2. JDK8 扩容机制

JDK8扩容中，为了避免之前提到的死锁问题，改进了扩容方法。通过判断这1位是0还是1，是0则不变。如果是1 ，加上原先数组大小。

newTab[j + oldCap] = hiHead;
//oldCap是原先的数组长度

• 扩容时机：元素插入后，当元素数量 > 扩容阈值时触发（无需判断插入位置是否为空）。
• 转移方式：批量分组转移，无需重新计算 hash 值，仅通过 hash 高位判断元素归属：
  1. 遍历旧数组链表 / 红黑树，按 hash 高位是否为 1，将元素分为「低位组」（下标不变）和「高位组」（下标 = 原下标 + 旧数组容量）。
  2. 分别将低位组和高位组批量转移到新数组的对应位置。
• 优化点：
  1. 批量转移效率高于逐个转移，无需重新计算 hash 值。
  2. 尾插法避免了多线程扩容的死锁问题。
  3. 红黑树转移时，直接按高位分组，无需重新构建红黑树（必要时拆分红黑树）。

总结：

• 扩容这一操作非常耗时，默认达到75%按照2倍进行扩容，这个75%也就是factor扩容因子。
• JDK7中扩容是在节点还没有加到HashMap前发生的；JDK8中扩容是在节点加到HashMap后发生的。
• JDK7扩容是一个一个元素计算然后转移，JDK8是先遍历，判断哪些是放到新数组的低位，哪些是高位，然后将low的元素和high的元素分别组合起来，一次性转移到新的数组中。

五、核心总结

1. 存储结构：JDK8 引入红黑树，解决 JDK7 链表过长导致的查询性能退化问题，查询效率从 O (n) 优化至 O (logn)。
2. 插入规则：JDK8 采用尾插法，解决 JDK7 头插法在多线程扩容时的死锁问题，同时配合链表计数逻辑，无额外性能损耗。
3. 哈希算法：JDK8 简化哈希计算，通过红黑树弥补性能损耗，兼顾效率和简洁性。
4. 扩容机制：JDK8 批量分组转移，无需重新计算 hash 值，效率更高，且解决了死锁问题。
5. 性能优化：JDK8 HashMap 在高哈希碰撞、多线程（非并发安全，并发推荐 ConcurrentHashMap）场景下，性能和稳定性均优于 JDK7。
6. 注意事项：扩容操作耗时较高，初始化 HashMap 时，建议根据预估元素数量指定初始容量，减少扩容次数。

参考资料

https://trunks2008.github.io/concurrent/HashMap.html

https://www.cnblogs.com/javawxid/p/15644349.html