简介

最近在寻找新的工作机会, 面试了一家做海外 AI 的公司, 面试官一上来就抛出了这个问题:

HashMap 是如何实现的?

听到这个问题, 我真的很想怼他一句: 你们是在使用 HashMap 的时候遇到什么问题了吗? 你说说问题, 我或许能帮你们解决一下.

但是本着相互尊重的原则, 我还是硬着头皮回答了一下, 因为很久没有看这些底层实现细节了, 所以今天还是整理一下.

Hash 的历史

这个人你一定要记住他, 他就是你每次面试都会被问到 HashMap 的灵魂人物, 哈希表的祖师爷: 汉斯·彼得·卢恩（Hans Peter Luhn）, 他在 IBM 内部备忘录中首次描述了散列和链接的概念，这被认为是现代哈希表思想的一个重要起源。

从「卢恩算法」到「存储桶」思想

在 20 世纪中叶，随着社会的信息化进程加快，各种身份识别号码开始在公共与私人生活中扮演重要角色，比如 信用卡号、社会保障号、电话号码 等。这些号码既难以记忆，也容易在手动操作中出错，更有被伪造的风险。

卢恩算法的诞生：为了防错校验

为了解决这个问题，IBM 的科学家 汉斯·彼得·卢恩（Hans Peter Luhn） 开发了一种轻量级的 校验和算法，旨在快速验证一组数字是否有效，这套算法现在被称为 Luhn Algorithm（卢恩算法），或者 模 10 算法（mod 10）。

以一个 10 位数字为例，这套算法的基本步骤是：

1. 每两位数字加倍
2. 如果加倍的结果 ≥ 10，则将结果的十位和个位数字相加（例如，16 → 1 + 6 = 7）
3. 将所有处理后的数字相加
4. 乘以 9
5. 取结果的最后一位数字

这个个位数字就是所谓的“校验码”。在原始设定中，如果校验码是 0，则说明号码有效。后来，该校验码被直接附加到号码末尾，用于后续验证。

哈希思想的启蒙：将信息分组进「桶」

更有趣的是，卢恩在 1953 年写的一份 IBM 内部备忘录 中提出了一个前所未有的想法：

“将信息放入编号的存储桶（bucket）中，以加快搜索速度。”

当时，查找电话号码或身份证号通常需要在整个数据库中逐条扫描，这在大数据面前效率极低。卢恩认为：

既然每组号码都有其特征，为什么不先计算一个“定位码”，把它放入对应的桶中？

桶的计算方式：原始的哈希函数原型

他以一个电话号码 314-159-2652 为例，说明如何生成桶号：

1. 将号码划分为若干两位数对：31、41、59、26、52
2. 对每一对求和：4（3+1）、5（4+1）、14（5+9）、8（2+6）、7（5+2）
3. 如果结果为两位数（如 14），仅取最后一位：变为 45487
4. 将这个结果作为桶号：45487

于是，号码 314-159-2652 和对应的姓名、地址等信息一起被存入 编号为 45487 的桶中。之后查找时，只需通过相同方式重新计算一次桶号，就可以快速定位相关信息。

即便一个桶中存在多个条目，也远比在所有数据中线性查找高效得多。

从「校验算法」 到「哈希算法」

卢恩的这项工作，不仅催生了现代校验机制，也成为了日后被称为 哈希算法（Hash Algorithm） 的基础雏形：

• 将任意输入映射为有限输出空间
• 以桶分组方式组织和快速访问数据
• 应对大量数据的高效存储与检索

这个“将数据送入桶”的理念，正是今天我们熟知的 哈希表（Hash Table） 的思想起点，直到今天仍广泛应用于数据库、编译器、缓存系统、密码学等领域。

KWIC 索引与 「存储桶」机制

在 1960 年代，面对不断增长的政府文献资料量，美国 Brandeis 大学图书馆尝试通过数据处理技术提高检索效率。他们开发了一种基于 KWIC（Key Word In Context）的计算机索引系统，用于整理和访问美国与联合国出版物。

问题背景

• 政府出版物数量庞大、结构分散，传统卡片目录系统难以及时更新；
• 用户难以通过主题或标题快速定位所需文献；
• 现有分类系统（如国会编号、馆藏号）对读者并不友好。

KWIC 项目核心机制

解决方案是构建一个以“关键词”为中心的计算机检索系统：

1. 出版物先按顺序编号（accession number）
2. 使用 IBM 卡片记录出版物元数据（如机构、标题、分类号等），字段位置固定（例如第14-79列存放标题字段）
3. 标题字段中的所有关键词被提取出来作为索引项，并记录其上下文（作者机构、出版年等）
4. 关键词作为索引入口，编号作为定位符，指向对应文献条目

类似哈希表的分组思想

• 虽未使用现代“哈希函数”，但该系统的“关键词映射到文献编号”的方法，已体现出初步的“键 → 桶”的思想；
• 每个关键词就像现代哈希表中的“key”，它指向的所有出版物编号，就像是哈希表中的“桶（bucket）”中的项；
• 数据组织结构本质上是：

1

keyword → [accession_number1, accession_number2, ...]

这与现代 HashMap 在思想上非常接近：通过可计算的关键码，将复杂数据分组管理，从而加速查询。

技术细节亮点

• 使用 IBM 1620 计算机 处理 KWIC 卡片；
• 所有词（除了例外字典中的、单字母、数字）都会生成关键词卡；
• 实现了快速索引、视觉清晰、可离线打印、易于维护；
• 成本低廉：每 100 条记录约花费 2.80 美元（1960 年代价格）；
• 缺点：关键词不等于真实主题；更新困难；依赖外部计算中心；排序不支持多字段复杂比较。

从 KWIC 到 HashMap 的理念进化

Brandeis 图书馆的 KWIC 项目虽然是信息检索系统，但其“关键词驱动 + 映射到资源”的核心思想，就是哈希表的雏形应用：

• 关键词提取 → 哈希函数作用
• 映射到文献编号 → 桶内存放多个条目
• 查找关键词 → 类似从哈希表中通过 key 定位 bucket

这类系统启发了之后数据库、搜索引擎乃至编程语言中哈希表结构的广泛发展。它标志着“对非结构化信息进行结构化索引与检索”的第一次成功实践之一。

参考

1. Hans Peter Luhn and the Birth of the Hashing Algorithm

Hash 冲突

卢恩算法通过 一种固定的算法 将 key 映射到桶的思路点亮了哈希表的科技树, 但是这里有一个不得不面对的问题: 「Hash 冲突」, 这里的 Hash 即代表前面的 固定算法, 常见的 Hash 算法有 MD5, SHA-X 系列等, 或者你可以使用取模来作为一个最简单的 hash 算法, 但是聪明的你会发现这个最简 hash 算法不能完全满足 Hash 函数的几个关键特性:

1. 确定性：相同输入始终产生相同哈希值
2. 不可逆性：无法通过哈希值反推原始输入（单向性）
3. 抗碰撞性：极难找到两个不同输入产生相同哈希值
4. 雪崩效应：输入微小变化会导致哈希值显著变化
5. 高效性：计算速度快，适合大规模数据处理

所以 Hash 算法是什么: 它是一种将任意长度的输入（如文本、文件或数据）通过特定计算规则转换为固定长度字符串（哈希值）的数学函数。它用来解决一些核心问题:

1. 数据完整性验证
   通过对比文件哈希值，可快速检测数据是否被篡改。例如，软件下载时提供的SHA-256校验码。区块链技术也依赖哈希值确保交易记录的不可篡改性。
2. 密码安全存储
   用户密码以哈希值形式存储（如bcrypt、Argon2算法），即使数据库泄露，攻击者也无法还原明文密码。
3. 快速数据检索
   哈希表通过哈希函数将键映射到存储位置，实现O(1)时间复杂度的查找。例如Java的HashMap使用链地址法解决冲突。
4. 分布式系统优化
   • 一致性哈希：在节点动态增减时，仅需局部数据迁移，避免全量重分布（如Redis集群）。
   • 负载均衡：通过哈希值分配请求到服务器，实现会话粘滞
5. 数字签名与认证
   哈希生成数据摘要后加密，确保信息完整性和来源可信（如SSL证书）

目前 Hash 算法也面临了一些挑战:

1. 哈希冲突
2. 安全性威胁
   • 碰撞攻击：MD5、SHA-1已被证明存在可构造的碰撞（如王小云教授的研究）。
   • 量子计算风险：量子计算机可能破解传统哈希算法，需抗量子算法（如基于格的哈希）。
   • 哈希洪水攻击：通过构造大量冲突拖慢系统性能。
3. 性能瓶颈
   • 计算开销：复杂哈希算法（如SHA-3）对CPU资源消耗较高。
   • 扩容成本：哈希表扩容需重新计算所有元素哈希值
   • 内存占用：链地址法的指针存储可能造成内存碎片。
4. 应用场景局限性
   • 动态数据分布：传统哈希取模法在节点增减时需全量数据迁移，一致性哈希虽优化但仍需虚拟节点平衡负载。
   • 实时性要求：高并发场景下哈希表锁竞争可能降低性能（需结合CAS或无锁结构）

其中 哈希冲突 是第一个需要被解决的问题, 人们从 2 个方面来解决这个问题:

1. 设计算法减少哈希冲突;
2. 在出现冲突时如何解决;

为什么我们不能彻底解决哈希冲突? 因为根据 鸽巢原理, 无限输入映射到有限输出必然导致冲突, 所以我们只能尽量减少冲突, 并在出现冲突时使用其他方式重新映射.

减小 Hash 冲突

减少 Hash 冲突不是一个方法就能搞定的, 二是一整套设计思维, 比如:

1. 使用优秀的哈希函数来保证确定性和高效性等其他特性;
2. 合理的桶大小来避免过多的数据导致冲突概率上升;
3. 针对具体使用场景的结构调整;
4. 针对具体场景选择高效的冲突解决策略;

面对 Hash 冲突

我们在尽量减小 Hash 冲突的同时, 还是不得不面对 Hash 冲突的发生, 因为这个是无法被避免的, 所以这个时候 链地址法(Separate Chaining) 和 开放地址法(Open Addressing) 就上场了.

链地址法

• 每个桶是链表、平衡树或跳表；
• 优点：结构灵活，可无限扩展；
• 提升点：
  • 使用红黑树替代链表（如 Java 8）
  • 使用跳表提升局部搜索性能（如 Redis）

开放地址法

• 所有 key 都放在数组中；
• 冲突后探测空位插入（线性探测、二次探测、双重哈希）；
• 提升点：
  • 避免过高的负载因子（一般不超过 0.7）
  • 二次探测比线性更抗聚集
  • 使用删除标记而不是实际清除

工程实现上的优化方式

Robin Hood Hashing (罗宾汉哈希)

• 开放地址法的变体：将“探测序列长的人”抢位置；
• 优点：缩短最长探测距离，性能更平衡；
• 被用于 Rust 的 HashMap 和 Facebook F14 Map。

Cuckoo Hashing (布谷鸟哈希)

• 使用多个哈希函数，如果冲突就“踢出原来的元素”，重新安置；
• 冲突概率低，但插入成本高，适合静态数据或安全关键场景；
• 应用于一些高性能缓存与网络路由中。

Hopscotch Hashing (跳房子哈希)

• 改良版的开放地址法，结合 bitmask 快速索引邻近元素；
• 支持高负载因子、高性能查找；
• 用于多核 CPU 上高速哈希表（Lock-Free/Concurrent scenarios）。

参考

1. 一篇让你学会哈希表(散列)

HashMap 的前世今生

HashMap 的起源：JDK 1.2

首先要知道，HashMap 并不是从 JDK 1.0 就有的，它是 JDK 1.2（1998 年）随 Collections Framework 一起引入的。

初代设计亮点

• 基于哈希表的数据结构
• 允许 null 键和值
• 线程不安全（需要自行同步）
• 用拉链法解决哈希冲突（链表）
• 默认容量：16，负载因子：0.75

1
2

Map<String, String> map = new HashMap<>();
map.put(null, "value"); // 合法

稳定期：JDK 1.4 - JDK 7（2002 - 2011）

这期间 HashMap 基本保持稳定，没有重构性的变化，主要是 bug 修复和优化：

🛠️ 典型特性

• 哈希函数优化（减少碰撞）
• Entry[] table 的懒初始化（只有第一次 put 才创建）
• 引入了 transient 字段，改进了序列化行为

重构与性能革命：JDK 8（2014）

JDK 8 是 HashMap 演进的分水岭，带来了两大变革：

链表 ➡️ 红黑树（Treeification）

• 如果某个桶内的链表长度超过 TREEIFY_THRESHOLD（默认8），且容量大于64，则转为红黑树，提升查找效率
• 红黑树适用于高冲突场景，避免退化成 O(n) 查询

1
2

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;

哈希算法进一步增强

• 对 key 的 hash 结果再混淆一次（hash(key.hashCode())），提高桶分布均匀性，减少碰撞

渐进优化：JDK 9 - JDK 14（2017 - 2020）

虽然 HashMap 本身的核心结构没有大的变化，但它间接受益于：

内部优化

• JDK 10：局部变量类型推断（var），提升代码可读性
• JDK 12+：HashMap 在 toString()、forEach() 等方面性能微调
• JDK 14：更智能的 GC 配合（ZGC, Shenandoah）对大 Map 更友好

并发友好 & 内存改进：JDK 15 - JDK 17（2020 - 2021）

虽说并发场景还是建议用 ConcurrentHashMap，但 HashMap 的实现更关注内存布局的优化：

• 更高效的对象头管理
• 更好的逃逸分析支持（配合 JIT 提升短生命周期 Map 性能）
• JDK 17 成为长期支持版本（LTS），对 HashMap 稳定性要求更高

虚拟线程时代：JDK 18 - JDK 21（2022 - 2024）

这阶段 Java 最大的主题是 Project Loom（虚拟线程），虽然它不直接改动 HashMap，但从另一个维度强调：

正确使用 HashMap 的边界更清晰

• 虚拟线程更强调“每个请求一个线程”，开发者更可能误用非线程安全集合，官方推荐文档多次强调避免用 HashMap 做并发容器。

JDK 21 - JDK 24：结构稳定，环境适配

虽然 JDK 21 已经是 LTS，JDK 22 和 JDK 23 是非 LTS，但 JDK 24 在三个方面对 HashMap 起到了优化或补强作用：

运行时性能提升：JIT & GC 协同更成熟

• JEP 439: Generational ZGC（JDK 21）：ZGC 现在有代际回收，更适合长期存活的大型 Map；
• JEP 453: ZGC Uncommit Unused Memory（JDK 23）：ZGC 会自动回收未使用的内存，HashMap 的大容量扩容后不再浪费；
• 逃逸分析 + 垃圾回收更紧密协作：尤其是短生命周期的临时 HashMap，在方法结束时自动优化内联释放，节省 GC 压力。

创建一个 HashMap 临时用于缓存中间计算，JIT 编译器会识别其生命周期极短，直接栈上分配，避免频繁 GC。

虚拟线程 & Structured Concurrency（结构化并发）

• JEP 444/462 引入虚拟线程（JDK 21、22 稳定）
• JEP 453/460 提出结构化线程模型，使得 HashMap 在传统线程上下文中更清晰地标识线程边界

这意味着：

你不能也不该在多个虚拟线程中共享同一个 HashMap 实例，官方也在强调这一点。

虽然这个“变化”不是在 HashMap 本身，而是在开发者使用姿势上的“规则明晰”。

IdentityHashMap 相关行为补注 & 文档完善

虽然不是 HashMap 本体，但从 JDK 22 开始，对相关 Map 实现的行为描述更加严谨，例如：

• 明确了哪些操作在 null 处理上是对称的
• 在 JavaDoc 中增加了关于 key 分布与 hash 冲突的设计指导建议

问题导向的 HashMap 设计哲学

问题 1：如何实现快速查找？

数组查找是 O(1)，但只能用整数下标；如何支持任意对象作为 key？

解决方案：

• 对 key 做 hashCode() 处理，映射为整数索引；
• 用数组保存数据，hash 决定元素存储在哪个“桶”里。

技术点：

• 哈希表结构：Node<K, V>[] table
• 对象哈希码：key.hashCode() + 二次扰动（JDK 8）
• 桶索引计算：index = (n - 1) & hash，数组长度为 2 的幂，便于用位运算代替取模，提高效率

问题 2：多个 key hash 到同一个桶怎么办？

哈希冲突在所难免，不能让后来的元素覆盖前面的。

解决方案：

• 在桶中用链表（或树）保存多个元素，这叫「链地址法」。

技术点：

• 链表存储冲突元素（拉链法）
• JDK 8 引入红黑树：当链表长度超过阈值（8），转换成红黑树，查询从 O(n) 优化到 O(log n)
• TreeifyThreshold / UntreeifyThreshold 控制树 ↔ 链表的动态切换

问题 3：哈希函数分布不均怎么办？

用户写的 hashCode() 质量参差不齐，容易导致热点桶、性能退化。

解决方案：

• 对原始 hash 再做一次扰动，让低位高位都参与桶定位。

技术点：

• 扰动函数（hash spreading）：(h = key.hashCode()) ^ (h >>> 16)
• 减少 hash 冲突，提升数据均匀分布性

问题 4：HashMap 容量有限，数据多了怎么办？

随着数据增多，冲突变多，链表变长，查询变慢。

解决方案：

• 当数据量超过负载因子 * 当前容量时，触发扩容（resize）

技术点：

• 负载因子（loadFactor，默认 0.75）
• 扩容机制：容量变为原来的两倍，重新计算每个元素的位置（rehash）
• 性能风险：rehash 代价高，尤其是高并发场景（JDK7 resize 曾导致死循环）

问题 5：如何支持 null 键和值？

某些场景可能允许 null，但数组或链表不天然支持。

解决方案：

• 将 null key 专门映射到 table[0]，单独处理逻辑。

技术点：

• if (key == null) 特判逻辑
• null key 只能有一个，但 value 可重复为 null

问题 6：如何避免不必要的初始化开销？

如果只是声明一个 Map，但从未使用，没必要马上分配底层数组。

解决方案：

• 使用 懒加载策略：table 在第一次 put() 时才初始化

技术点：

• if (table == null || table.length == 0) resize();

问题 7：如何支持序列化？

有些场景需要将 Map 保存到磁盘或网络中传输。

解决方案：

• 实现 Serializable 接口，自定义序列化/反序列化逻辑。

技术点：

• transient 修饰内部数组，避免直接暴露内存结构
• writeObject() / readObject() 方法定制读写逻辑

问题 8：如何保证良好的迭代体验？

迭代过程不能因数据变化而崩溃，也要有错误提示。

解决方案：

• 在迭代器中记录结构修改次数，fail-fast 检测并发修改。

技术点：

• modCount 字段配合 ConcurrentModificationException
• 快速失败策略提醒开发者非线程安全访问

总结

当然可以！下面我为你整理了一套 Java HashMap 的最佳实践指南，每条都有理由说明，不仅知其然，还知其所以然，适合写进博客、文档或团队规范中。

HashMap 最佳实践

初始化时预估容量，避免频繁扩容

1

Map<String, Object> map = new HashMap<>(128);

• HashMap 会在元素数量超过 容量 × 负载因子 时触发 扩容 + rehash，这是一项代价昂贵的操作。
• 提前预估数据量可以避免多次扩容重排，提升插入性能，尤其在大批量 put 场景下（如解析 JSON、大批量缓存构建）。

避免在 key 中使用可变对象

1

Set<User> set = new HashSet<>(); // 👎 如果 User 没有重写 hashCode/equals 或字段可变	

• 若对象作为 key，并在 put 之后修改了其字段，hashCode() 结果会改变，导致查找失败或删除失败。
• hashMap 是基于 hash 和 equals 的一致性设计，key 必须是不可变对象。

最好使用 final 类、不可变字段，或直接用 String / Long 等基础类型作为 key。

负载因子保持默认即可，不建议随意更改

1

new HashMap<>(16, 0.75f); // 👍 推荐使用默认负载因子

• 0.75f 是经验权衡结果，在空间利用和查询效率之间平衡得非常好。
• 过低会浪费空间，过高会增加冲突率，导致链表/树查询变慢。

避免在多线程环境下使用 HashMap

• HashMap 不是线程安全的，并发操作可能导致死循环、数据丢失、结构破坏（尤其是在 JDK7 中 resize 存在死链 bug）。
• 使用以下替代方案更安全：
  • ConcurrentHashMap
  • Collections.synchronizedMap(…)（适合小数据量低并发）

迭代时避免修改结构，或使用 Iterator.remove()

1
2
3
4
5
6
7

Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
while (it.hasNext()) {
    Map.Entry<String, String> entry = it.next();
    if (entry.getKey().equals("xxx")) {
        it.remove(); // ✅ 安全方式
    }
}

• HashMap 的 fail-fast 机制会在结构被并发修改时抛出 ConcurrentModificationException。
• 使用 Iterator.remove() 是修改结构的唯一安全方式。

遍历时优先使用 entrySet() 而非 keySet() + get

1
2
3

for (Map.Entry<String, Object> entry : map.entrySet()) {
    System.out.println(entry.getKey() + "=" + entry.getValue()); // 👍 高效
}

• keySet() 迭代过程中若还要调用 map.get(key)，会重复查找 hash、桶定位。
• entrySet() 一次性拿到 key 和 value，更高效。

谨慎使用 null 作为 key，建议避免

1

map.put(null, "xxx"); // 虽然合法，但不推荐

• HashMap 允许一个 null key，但很多人容易忽略这个特性，导致程序行为不一致。
• 某些 Map 实现（如 Hashtable、ConcurrentHashMap）不支持 null，代码可移植性差。
• 建议业务上用特殊字符串或 Optional.empty() 表达“空键”语义。

在对性能要求极高的场景下，使用 LongHashMap、Object2ObjectOpenHashMap 等高性能实现

• JDK 原生的 HashMap 是通用设计，有装箱开销和泛型擦除开销。
• 第三方库如 fastutil、HPPC 提供了更贴近底层的数据结构：
  • 避免装箱
  • 更高缓存局部性
  • 扩容策略更灵活

在使用 hashCode() 时保持 equals() 一致性

1
2

// 必须满足：
a.equals(b) == true ➡️ a.hashCode() == b.hashCode()

• HashMap 查找时先通过 hashCode 快速定位，再通过 equals 精确匹配
• 若 hashCode 不一致，根本找不到桶，就算 equals 成立也无效
• 推荐使用 IDE 自动生成 equals/hashCode

一致性哈希

https://quant67.com/post/system-design/con-hash/hash.html