HashMap in Java

在 Java 的集合框架中，HashMap 是最常用的键值对存储容器之一。它以 哈希表（Hash Table） 作为底层数据结构，通过哈希算法实现了接近常数时间复杂度的查找和插入操作。

本文将重点介绍 Java 8 之前（主要是 Java 7 及以下版本）HashMap 的底层实现原理，包括其 哈希计算、扩容机制、冲突处理策略 等内容，并对比 Java 8 之后的改进（红黑树结构）。

---

基础使用层的内容

API使用方式（CRUD）

• Create 增加元素 将一个键值对（元素）添加到 HashMap 中，可以使用 put() 方法。例如，将名字和年龄作为键值对添加到 HashMap 中：

final var map = new HashMap<String, Integer>();
map.put("张三", 20);
map.put("李四", 25);

• Delete 删除元素 从 HashMap 中删除一个键值对，可以使用 remove() 方法。例如，删除名字为 "张三" 的键值对：

map.remove("张三");

• Update 修改元素 修改 HashMap 中的一个键值对，可以使用 put() 方法。例如，将名字为 "张三" 的年龄修改为 30：

map.put("张三", 30);

• Read 查询元素 从 HashMap 中查找一个键对应的值，可以使用 get() 方法。例如，查找名字为 "张三" 的年龄：

final var age = map.get("张三");

在实际应用中，HashMap 可以用于缓存、索引等场景。例如，可以将用户 ID 作为键，用户信息作为值，将用户信息缓存到 HashMap 中，以便快速查找。又如，可以将关键字作为键，文档 ID 列表作为值，将文档索引缓存到 HashMap 中，以便快速搜索文档。

HashMap 的实现原理是基于哈希表的，它的底层是一个数组，数组的每个位置可能是一个链表或红黑树，也可能只是一个键值对（后面会讲）。当添加一个键值对时，HashMap 会根据键的哈希值计算出该键对应的数组下标（索引），然后将键值对插入到对应的位置。

当通过键查找值时，HashMap 也会根据键的哈希值计算出数组下标，并查找对应的值。

---

原理层的内容

一、基本结构

在 Java 7 中，HashMap 底层由一个 数组（Entry[] table） 组成，其中每个数组元素称为一个 桶（Bucket）。 每个桶中存放的是一个 单向链表（即哈希冲突后同哈希值的元素被串联起来）。

结构示意如下：

table[0] -> Entry1 -> Entry2 -> Entry3
table[1] -> null
table[2] -> Entry4 -> Entry5
...

每个 Entry 节点的定义（Java 7）大致如下：

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

    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
}

---

二、哈希计算与寻址

HashMap 通过 key 的 hashCode() 来决定元素在数组中的存储位置。 但为了让哈希分布更均匀，Java 7 中还会对哈希值进行“扰动函数（hash扰动）”计算。

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

1. hash() 函数

在 Java 7 中：

final int hash(Object k) {
    int h = k.hashCode();
    return h ^ (h >>> 16);  // 高位扰动
}

这一步的目的是让高位参与低位运算，从而减少哈希冲突。

2. index计算

通过 & (length - 1) 替代 % length 来求模。 因为数组长度总是 2 的幂，用位运算效率更高。

---

三、哈希冲突与链表结构

当两个不同的 key 计算出的哈希索引相同，就会产生 哈希冲突（Hash Collision）。

解决办法：链地址法（Separate Chaining）

即将新元素插入到对应桶的链表中。例如：

Entry<K,V> e = table[index];
table[index] = new Entry<>(hash, key, value, e);

在 Java 7 中，新元素插入链表的头部（头插法），这意味着：

• 插入新节点时，原先的节点成为新节点的 next；
• 导致在多线程环境下扩容时容易出现环形链表问题（死循环）。

---

四、扩容机制（Rehashing）

1. 触发条件

当 HashMap 中的元素数量超过阈值（threshold）时，会触发扩容。 阈值 = capacity * loadFactor。

默认：

initialCapacity = 16
loadFactor = 0.75

→ 阈值 = 16 × 0.75 = 12 即超过 12 个元素就会扩容。

2. 扩容过程

扩容时，HashMap 会创建一个新的数组（容量为原来的 2 倍），并将原有数据重新计算位置。

void resize(int newCapacity) {
    Entry[] oldTable = table;
    Entry[] newTable = new Entry[newCapacity];
    for (Entry<K,V> e : oldTable) {
        while (e != null) {
            Entry<K,V> next = e.next;
            int i = e.hash & (newCapacity - 1);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
    table = newTable;
}

这一步称为 Rehashing，因为每个元素都需要重新计算桶位置。 扩容开销较大，所以频繁扩容会严重影响性能。

---

五、Java 8 中的改进：红黑树（Treeify）

在 Java 8 中，为了解决链表过长导致性能下降的问题，引入了 红黑树结构。

1. 触发条件

当某个桶中的链表长度超过 8，并且数组容量大于 64 时，会将链表转化为红黑树。

if (binCount >= TREEIFY_THRESHOLD - 1)
    treeifyBin(tab, hash);

2. 优势

• 链表查找复杂度：O(n)
• 红黑树查找复杂度：O(log n)

当哈希冲突严重时，性能大幅提升。

3. 节点类型变化

Java 8 引入了 Node（代替 Entry）和 TreeNode 两种结构：

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

当链表过长时，Node 会转换为 TreeNode，形成平衡二叉树结构。

---

六、线程安全问题

需要注意：

• HashMap 在 多线程环境下是不安全的。
• Java 7 使用头插法在扩容时可能导致链表成环，从而死循环；
• Java 8 改为 尾插法，并优化了扩容逻辑，避免了死循环。

多线程环境建议使用：

• ConcurrentHashMap
• 或者通过 Collections.synchronizedMap() 包装。

---

七、总结对比（Java 7 vs Java 8）

特性	Java 7	Java 8
底层结构	数组 + 链表	数组 + 链表 + 红黑树
链表插入方式	头插法	尾插法
扩容时机	超过阈值后	同样，但逻辑优化
冲突处理	链表	链表 + 红黑树优化
hash扰动函数	存在	优化后更简单
线程安全	不安全	不安全（需 ConcurrentHashMap）

---

八、结语

Java 7 的 HashMap 是一个典型的哈希表实现，通过 数组 + 链表 实现高效的存取。 Java 8 在此基础上引入了 红黑树，有效解决了链表过长导致性能退化的问题。 理解 HashMap 的底层原理，不仅能帮助我们编写更高效的代码，也能在排查复杂问题（如扩容引发的死循环、哈希冲突）时提供理论支撑。