作为一名开发者，我们每天都在使用各种各样的数据结构。你是否想过，当需要在海量数据中瞬间（O(1) 时间复杂度）找到某个元素时，Java 的 HashMap 是如何做到的？虽然 Java 提供了完善的集合框架，但亲自拆解并实现一个哈希表，是理解底层原理的最佳途径。在这篇文章中，我们将暂时放下现成的工具，一起动手，使用链地址法在 Java 中构建属于我们自己的哈希表。这不仅是一次代码练习，更是一次对计算机科学经典思想的深入探索。
为什么我们需要自定义哈希表？
在深入研究代码之前，让我们先退一步，思考一下为什么我们会选择哈希表。在算法的世界里，不同的数据结构都有其独特的“杀手级应用”：
- 二叉搜索树 (BST)：当我们需要快速搜索（O(log n)）且保持数据有序时，它是首选。
- 堆/优先队列：当我们需要在常数时间内获取最大或最小元素时，它们不可或缺。
- 哈希表：当我们需要在常数时间内完成获取、添加和删除操作时，它是王者。
虽然 Java 的标准库中已经有了 HashMap 和 Hashtable，但在面试或高性能场景下，理解其内部工作机制——特别是如何处理哈希冲突——是区分初级和高级开发者的关键。
> 注意：在本文中，我们将交替使用“哈希映射”和“哈希表”这两个术语。虽然 Java 中 INLINECODEe45ff3ee 是线程安全的（同步的），而 INLINECODE0486276d 不是，但我们这里的重点是实现核心的数据结构逻辑，而非线程安全。
核心概念：哈希与压缩
每个哈希表的核心都是以键值对的形式存储数据。这里有一个有趣的特性：键必须是唯一的，但值可以重复。
让我们看看哈希表是如何存储数据的。在数组中，我们通过整数索引来获取值；而在哈希表中，我们使用对象（键）来获取值。这个魔法分为两个步骤：
- 哈希码：在 Java 中，每个对象都有一个
hashCode()方法，它返回一个整数（可以是随机的，也可以是确定的）。这是 JVM 给我们的“原材料”。 - 压缩器：哈希码通常是一个很大的整数（甚至是负数），而我们的数组（桶）大小是有限的。我们需要把这个巨大的整数映射到一个有效的数组索引范围内（例如 0 到 10）。
最简单的压缩公式：
index = hashCode(key) % size
在这里，取模运算符 (%) 充当了压缩器。它确保了无论哈希码多大，最终生成的索引都在桶的范围内。
无法避免的挑战：哈希冲突
理论上，完美的哈希函数能让每个键都对应唯一的索引。但在现实中，这是一种奢望。哈希冲突迟早会发生：两个不同的键经过哈希计算后，指向了同一个桶。
试想一下，如果你把“KeyA”放在了 1 号桶，现在又要放“KeyB”，计算结果也是 1 号桶。我们该怎么做？直接覆盖？那是灾难性的！
为了解决这个问题，我们将采用链地址法。
#### 什么是链地址法？
想象我们的哈希表内部是一个数组，数组的每个位置（桶）不仅仅存放一个值，而是存放一个链表的头节点。当冲突发生时，我们只需要把新的数据追加到该桶对应的链表中即可。
这种方法虽然简单，但也带来了最坏情况的风险：如果所有键都极其不幸地映射到了同一个桶，哈希表就会退化成一个链表，搜索操作的时间复杂度也会从 O(1) 暴跌到 O(n)。
性能优化的关键：负载因子与扩容
为了防止哈希表退化为链表，我们需要引入一个监控指标：负载因子。
- 负载因子 = 已填充的桶数 / 总桶数
在我们的实现中，我们将阈值设定为 0.7。这意味着，当 70% 的桶都被填满时，我们需要采取行动来降低冲突的概率。这个行动就是扩容。
扩容逻辑：
- 创建一个大小是原来两倍的新数组（例如从 10 变为 20）。
- 将旧数组中的所有元素重新哈希并放入新数组（因为 INLINECODEaa818498 变了，INLINECODE258216c5 也会变）。
- 丢弃旧数组。
这是一个昂贵的操作，但在长远来看，它保证了 O(1) 的查询性能。
实战编码：构建哈希表
准备好了吗？让我们把理论转化为代码。我们将采用泛型，这样我们的哈希表就可以支持任何类型的键和值。
#### 步骤 1：定义哈希节点
首先，我们需要一个类来表示链表中的节点。因为我们需要使用链地址法来解决冲突，所以每个节点必须存储数据本身以及指向下一个节点的指针。
/**
* 哈希节点类，用于存储链表中的每个键值对。
* 这是一个泛型类，K 代表键的类型，V 代表值的类型。
*/
class HashNode {
K key;
V value;
// 指向链表中的下一个节点（用于处理冲突）
HashNode next;
// 构造函数
public HashNode(K key, V value) {
this.key = key;
this.value = value;
this.next = null;
}
}
设计思路：
- 我们将 INLINECODE0be6c4c5 和 INLINECODE19c48f1c 都存储下来，以便在发生冲突时，我们可以遍历链表并对比
key来找到确切的值。
#### 步骤 2：定义哈希表骨架
接下来是我们的主类。我们需要维护一个桶数组，并跟踪当前的大小（元素数量）和桶的数量。
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
/**
* 我们的自定义哈希表实现
* 使用链地址法处理冲突
*/
public class MyMap {
// 桶数组：每个位置是一个链表的头节点
private List<HashNode> bucketArray;
// 当前桶的数量
private int numBuckets;
// 当前哈希表中元素的大小（键值对数量）
private int size;
// 构造函数：初始化哈希表
public MyMap() {
bucketArray = new ArrayList();
numBuckets = 10; // 初始容量为 10
size = 0;
// 初始化桶
for (int i = 0; i < numBuckets; i++) {
bucketArray.add(null);
}
}
// 获取当前哈希表的大小
public int size() {
return size;
}
// 判断哈希表是否为空
public boolean isEmpty() {
return size() == 0;
}
// ... 核心方法将在下面实现 ...
}
设计思路：
- 我们使用 INLINECODE2ebc028f 而不是原生数组 INLINECODE5dcb1d0c，因为它在动态处理链表节点时更加方便。
- 初始
numBuckets设为 10 是一个比较折中的起点，既不会太大浪费内存，也不会太小导致频繁扩容。
#### 步骤 3：实现哈希函数
这是哈希表的大脑。我们需要安全地处理键的哈希码，并将其转换为桶索引。
/**
* 获取键对应的桶索引
* 使用哈希码和取模运算
*/
private int getBucketIndex(K key) {
int hashCode = Objects.hashCode(key);
// 这种运算方式保证了索引一定是正数
// Integer.MAX_VALUE 是一个大的质数近似值，也可以直接用 numBuckets
int index = hashCode % numBuckets;
// key.hashCode() 可能包含负数，我们需要处理这种情况
// 这里再次取模是为了确保索引非负且在范围内
return (index & 0x7FFFFFFF) % numBuckets;
// 注：更简单的写法是 Math.abs(hashCode) % numBuckets，但要注意溢出问题
// 这里为了演示原理，我们使用健壮的位运算处理
}
关键点解析：
- INLINECODEffbcc983 能够优雅地处理 INLINECODE4e5d111e 为 INLINECODEec747e65 的情况，比直接调用 INLINECODE5540eeb9 更安全。
- INLINECODE93f93b55 是一个经典的位运算技巧，用于将符号位（最高位）置为 0，从而将负数转换为正数，防止 INLINECODE58f12a71。
#### 步骤 4：实现删除方法
在添加数据之前，我们先看删除。因为要删除，必须先找到。寻找的过程体现了链地址法的逻辑：先定位桶，再遍历链表。
/**
* 根据键删除值
* @param key 要删除的键
* @return 被删除的值，如果键不存在则返回 null
*/
public V remove(K key) {
// 1. 找到桶的索引
int bucketIndex = getBucketIndex(key);
// 2. 获取该桶对应的链表头节点
HashNode head = bucketArray.get(bucketIndex);
// 3. 遍历链表寻找目标键
HashNode prev = null;
while (head != null) {
// 如果找到了键
if (head.key.equals(key)) {
break;
}
// 否则继续向后移动
prev = head;
head = head.next;
}
// 如果没找到，返回 null
if (head == null) {
return null;
}
// 4. 执行断链操作（从链表中移除节点）
size--; // 减少元素总数量
// 如果要删除的是头节点
if (prev != null) {
prev.next = head.next;
} else {
// 如果 prev 为 null，说明要删的是头节点，直接将头指针移向下一个
bucketArray.set(bucketIndex, head.next);
}
return head.value;
}
代码逻辑：
- 这段代码维护了一个 INLINECODE7321b4c1 指针。在单向链表中删除节点，我们必须知道前一个节点才能修改 INLINECODE5647c2c1 指针。
- 这是一个标准的链表删除操作，时间复杂度取决于链表长度（最坏 O(n)，平均 O(1)）。
#### 步骤 5：实现获取值方法
与删除类似，get 方法也是“定位 -> 遍历 -> 匹配”。
/**
* 获取键对应的值
* @param key 键
* @return 对应的值，如果不存在返回 null
*/
public V get(K key) {
// 1. 找到桶索引
int bucketIndex = getBucketIndex(key);
// 2. 获取链表头
HashNode head = bucketArray.get(bucketIndex);
// 3. 遍历查找
while (head != null) {
if (head.key.equals(key)) {
return head.value;
}
head = head.next;
}
// 未找到
return null;
}
#### 步骤 6：实现添加方法与动态扩容
这是最复杂的部分。我们需要处理更新现有值、插入新值以及最关键的——负载因子检查与扩容。
/**
* 向哈希表添加键值对
* @param key 键
* @param value 值
*/
public void put(K key, V value) {
// 1. 找到桶索引
int bucketIndex = getBucketIndex(key);
// 2. 获取链表头
HashNode head = bucketArray.get(bucketIndex);
// 3. 检查键是否已存在（遍历链表）
while (head != null) {
// 如果键已经存在，我们更新值并返回（不增加 size）
if (head.key.equals(key)) {
head.value = value;
return;
}
head = head.next;
}
// 4. 如果键不存在，插入新节点
// 将新节点插入到链表头部（头插法），效率高
size++;
head = bucketArray.get(bucketIndex);
HashNode newNode = new HashNode(key, value);
newNode.next = head;
bucketArray.set(bucketIndex, newNode);
// 5. 检查负载因子
// 如果当前数量超过了桶数量的 70%，则扩容
if ((1.0 * size) / numBuckets >= 0.7) {
// 执行扩容操作
List<HashNode> temp = bucketArray;
bucketArray = new ArrayList();
numBuckets = 2 * numBuckets; // 容量翻倍
size = 0; // 重置 size，因为下面要重新 add
// 初始化新的桶数组
for (int i = 0; i < numBuckets; i++) {
bucketArray.add(null);
}
// 将旧数据重新哈希并放入新数组
for (HashNode headNode : temp) {
while (headNode != null) {
put(headNode.key, headNode.value);
headNode = headNode.next;
}
}
}
}
实用见解与最佳实践：
- 头插法 vs 尾插法：我们在代码中使用了头插法（
newNode.next = head）。这比遍历到链表末尾进行尾插法要快（O(1)）。虽然在 Java 8+ 的官方 HashMap 中使用了尾插法（为了优化扩容时的链表死循环问题），但在我们这个简单的实现中，头插法是性能与复杂度的良好平衡。
- 为什么是 0.7？：负载因子是时间和空间的权衡。如果设为 1.0，空间利用率高，但冲突多，查询慢。如果设为 0.5，冲突少，但浪费空间。0.7 是统计学上的一个经验值，被证实能较好地平衡这两者。
- 扩容的代价：注意我们的
put方法中的扩容部分。它需要创建一个新数组，并重新计算每一个旧元素的哈希。这是非常耗时的操作（O(n)）。这就是为什么建议在初始化 HashMap 时，如果能预估数据量，最好指定初始容量，以避免中途扩容带来的性能抖动。
常见错误与陷阱
在实现哈希表时，新手（甚至有经验的开发者）常犯以下错误：
- 错误的哈希函数：如果你只使用 INLINECODE8fa60717，当 INLINECODE9119cbf4 为负数时，索引会变成负数，导致程序崩溃。务必使用 INLINECODE0e3342af 或位运算 INLINECODE87a3e0c6 来处理负数。
- 忘记处理 Key 为 null 的情况：INLINECODE0713946c 会返回 0，这是安全的。但如果你直接调用 INLINECODEeb15541d，当 key 为 null 时会抛出
NullPointerException。使用工具类总是更安全。
- 在 equals 和 hashCode 上不一致：两个对象 INLINECODEd35b3863 返回 true，必须保证 INLINECODEf36f4af9 相同。如果不遵循这个契约，我们的哈希表将无法正确找到数据。
- 扩容死循环：虽然在这个简单版本中不容易发生，但在多线程环境下，如果两个线程同时触发扩容，操作链表指针可能会导致数据丢失或死循环。这就是为什么 Java 的 HashMap 在并发环境下是不安全的，应该使用
ConcurrentHashMap。
总结与后续步骤
通过这篇文章，我们不仅仅是写了几百行代码。我们深入理解了以下核心机制：
- 如何通过哈希函数将对象映射到数组索引。
- 如何使用链地址法优雅地解决哈希冲突。
- 负载因子如何作为触发器，平衡哈希表的内存使用与操作效率。
- 动态扩容机制是如何工作的，以及它为何如此昂贵。
这个实现虽然简单，但它包含了工业级哈希表的核心骨架。接下来，作为读者的你可以尝试以下挑战来进一步提升：
- 实现
toString()方法：能够打印出当前哈希表的所有内容，直观地看到哪个桶是空的，哪个桶发生了冲突。 - 支持 INLINECODEec0903a0 和 INLINECODEa553b3e5：这需要更复杂的遍历逻辑。
- 将链表替换为红黑树：就像 Java 8 做的那样。当单个桶的链表长度超过 8 时，将其转换为树结构，将查询性能从 O(n) 提升到 O(log n)。
希望这次探索能让你对 INLINECODE2f44671c 背后的魔法有了更清晰的认识。下次当你写下 INLINECODE64236e4e 时，你会知道这背后发生了一场怎样的精彩运算。