当前位置：首页 > article >正文

说说 Java 中 HashMap 的原理？

article 2025/2/4 15:25:13

回答重点

HashMap 是基于哈希表的数据结构，用于存储键值对（key-value）。其核心是将键的哈希值映射到数组索引位置，通过数组 + 链表（在 Java 8 及之后是数组 + 链表 + 红黑树）来处理哈希冲突。

HashMap 使用键的 hashCode() 方法计算哈希值，并通过 indexFor 方法（JDK 1.7 及之后版本移除了这个方法，直接使用 (n - 1) & hash）确定元素在数组中的存储位置。哈希值是经过一定扰动处理的，防止哈希值分布不均匀，从而减少冲突。

HashMap 的默认初始容量为 16，负载因子为 0.75。也就是说，当存储的元素数量超过 16 × 0.75 = 12 个时，HashMap 会触发扩容操作，容量 x2 并重新分配元素位置。这种扩容是比较耗时的操作，频繁扩容会影响性能。

参考答案拆解

1. 核心结构分层解析

HashMap 基于数组 + 链表/红黑树实现，核心设计围绕哈希函数、碰撞解决和动态扩容展开。以下是核心原理拆解：

// 源码核心字段（JDK8+）
transient Node<K,V>[] table; // 哈希桶数组
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; // 扰动后的哈希值
    final K key;
    V value;
    Node<K,V> next; // 链表结构
}

2. 关键技术点详解

（1）哈希扰动函数

// JDK8的哈希计算（高位参与运算）
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

设计意图：将原始哈希码的高 16 位与低 16 位异或，让高位特征参与索引计算
数组定位：(n-1) & hash（等价取模，但效率更高）

（2）链表树化条件

// 树化阈值（链表长度>=8且数组长度>=64）
static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;

平衡策略：树化提升查询效率（O(n)→O(logn)），退化阈值 6 避免频繁转换

（3）扩容机制

// 扩容触发条件：size > threshold（容量*负载因子）
final Node<K,V>[] resize() {
    int newCap = oldCap << 1; // 容量翻倍
    // … 重新分配元素到新数组
}

优化点：扩容后新位置=原位置或原位置 + 旧容量（利用高位判断）

HashMap 的红黑树优化

从 Java 8 开始，为了优化当多个元素映射到同一个哈希桶（即发生哈希冲突）时的查找性能，当链表长度超过 8 时，链表会转变为红黑树。红黑树是一种自平衡二叉搜索树，能够将最坏情况下的查找复杂度从 O(n) 降低到 O(log n)。

如果树中元素的数量低于 6，红黑树会转换回链表，以减少不必要的树操作开销。

hashCode() 和 equals() 的重要性

HashMap 的键必须实现 hashCode() 和 equals() 方法。hashCode() 用于计算哈希值，以决定键的存储位置，而 equals() 用于比较两个键是否相同。在 put 操作时，如果两个键的 hashCode() 相同，但 equals() 返回 false，则这两个键会被视为不同的键，存储在同一个桶的不同位置。

误用 hashCode() 和 equals() 会导致 HashMap 中的元素无法正常查找或插入。

默认容量与负载因子的选择

默认容量是 16，负载因子为 0.75，这个组合是在性能和空间之间找到的平衡。较高的负载因子（如 1.0）会减少空间浪费，但增加了哈希冲突的概率；较低的负载因子则会增加空间开销，但减少哈希冲突。

如果已知 HashMap 的容量需求，建议提前设定合适的初始容量，以减少扩容带来的性能损耗。

3. 项目实战包装

案例场景：

在电商促销系统的商品库存管理模块，使用 HashMap 缓存实时库存数据：

初始容量优化：根据预估并发量设置 initialCapacity=2048（避免频繁扩容）
键对象设计：重写商品 SKU 对象的 hashCode() 和 equals()，保证哈希均匀
热点数据处理：监控发现某些爆款商品哈希碰撞严重，通过自定义 hash 算法分散热点

4. 底层原理深入

（1）并发问题根因

// 多线程put导致链表成环示例（JDK7头插法问题）
void transfer(Entry[] newTable) {
    Entry<K,V> e = table[bucket];
    while(null != e) {
        Entry<K,V> next = e.next;
        e.next = newTable[bucket]; // 并发修改导致循环链表
        newTable[bucket] = e;
        e = next;
    }
}