【数据结构】当两个不同的 Key 撞在了一起：HashMap 的“事故”现场与急救指南
目录
一、任务目标：
1. 理解哈希冲突与解决策略（拉链寻址、开放寻址等）。
2. 实现简单HashMap。
3. 掌握哈希函数设计。
4.基于 MAP，实现一个简单的 hashMap
二、正文
在日常开发中，HashMap 是我们最常用的集合类之一。它能够在近似 O(1) 的时间复杂度内完成键值对的存储和查找，这背后离不开哈希表的精巧设计。本文将带你从零开始，一步步理解哈希冲突的产生原因、常见解决策略，并动手实现一个最简单的 HashMap。即使你 Java 基础薄弱，也能轻松跟上。
1. 为什么需要 HashMap？
假设我们要存储一批学生信息，希望通过学号快速找到对应的学生。如果用数组，学号就是索引，查找非常快，但学号可能不连续（比如 10001、20005），会造成大量空间浪费。如果用链表，空间利用率高，但查找需要遍历，速度慢。
有没有一种结构，既能像数组一样快速定位，又能像链表一样灵活利用空间？答案是哈希表（Hash Table），Java 中的 HashMap 就是哈希表的一种实现。
2. 哈希表基础概念
哈希表的核心思想是：通过一个哈希函数，将键（Key）映射到数组的某个下标，然后将键值对存储在该下标对应的位置。
数组：哈希表底层通常是一个数组，我们称它为 桶数组（bucket array）。
哈希函数：
f(key) -> index，将任意大小的 key 转换为一个固定范围内的整数（通常是数组长度范围内的索引）。节点：数组中每个位置可以存放一个或多个键值对。最简单的形式是存放一个键值对，但更常见的是存放一个链表或红黑树的头节点。
当我们调用 map.put("apple", 5) 时，大致流程是：
-
计算
"apple"的哈希值。 -
将哈希值通过某种方式（如取模）转换为数组下标，比如
index = 3。 -
将键值对
("apple", 5)存入数组下标为 3 的位置。
查找时同样计算下标，直接取出即可。理想情况下，每个下标只存一个元素，时间复杂度 O(1)。
3. 什么是哈希冲突？
现实很骨感：不同的 key 经过哈希函数计算后，可能得到相同的下标。比如 "apple" 和 "banana" 都映射到了下标 3。这种情况称为 哈希冲突（Hash Collision）。
冲突是无法完全避免的，因为数组长度有限，而 key 的可能性无限。所以我们必须有办法解决冲突。
4. 解决哈希冲突的常见策略
4.1 拉链法（Chaining）
思想：数组的每个元素不再是一个单独的键值对，而是一个链表的头节点。冲突发生时，将新的键值对直接挂在链表末尾。
-
优点：实现简单，删除方便，数组空间利用率高。
-
缺点：最坏情况下所有元素都冲突，链表过长，查找退化为 O(n)。JDK 1.8 的 HashMap 在链表长度超过 8 时会转换为红黑树，优化查找性能。
4.2 开放寻址法（Open Addressing）
思想：当发生冲突时，按某种规则在数组中寻找下一个空闲位置存放元素。常见探测方法有：
-
线性探测：依次检查
index+1、index+2... 直到找到空位。 -
二次探测：探测位置为
index + 1^2、index + 2^2... 避免数据聚集。 -
双重哈希：使用第二个哈希函数计算步长。
Java 中的 ThreadLocalMap 就使用了线性探测的开放寻址法。
-
优点：完全利用数组空间，无需额外指针，缓存友好。
-
缺点：删除元素麻烦（需要特殊标记），随着负载因子升高，性能急剧下降。
负载因子 = 已存储元素个数 / 数组长度。当负载因子超过阈值（如 0.75）时，通常需要扩容（rehash）来减少冲突。
5. 哈希函数设计
一个好的哈希函数应该：
-
计算快速：不能太复杂，否则影响性能。
-
均匀分布：尽量让 key 散列到各个下标，减少冲突。
在 Java 中，每个对象都有一个 hashCode() 方法，它返回一个 int 整数。但直接使用 hashCode() 作为下标会超出数组范围，所以通常需要取模：index = hashCode % array.length。但取模运算较慢，且如果 hashCode 分布不均匀，可能导致某些下标频繁冲突。
JDK 的 HashMap 对 hashCode() 做了二次处理（扰动函数），让高位也参与运算，然后再取模：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}这样混合了高位和低位，使得分布更均匀。取模时利用位运算（(n - 1) & hash）代替取模，前提是数组长度必须是 2 的幂次。
6. 手写一个最简单的 HashMap
现在，我们用拉链法实现一个简化的 HashMap，包含最基本的 put、get、remove 方法。为了突出核心思想，我们不考虑扩容、红黑树、泛型边界等复杂内容。
6.1 定义节点类 Entry
每个键值对就是一个节点，同时作为链表节点：
class Entry<K, V> {
K key;
V value;
Entry<K, V> next; // 指向下一个节点，用于拉链
public Entry(K key, V value, Entry<K, V> next) {
this.key = key;
this.value = value;
this.next = next;
}
}6.2 定义 HashMap 类
我们需要一个数组来存储链表头节点，还需要记录当前元素个数和默认容量：
public class MyHashMap<K, V> {
private static final int DEFAULT_CAPACITY = 16; // 默认数组长度
private Entry<K, V>[] table; // 桶数组
private int size; // 当前存储的键值对数量
@SuppressWarnings("unchecked")
public MyHashMap() {
table = (Entry<K, V>[]) new Entry[DEFAULT_CAPACITY];
size = 0;
}
}6.3 哈希函数与下标计算
我们采用简单取模，同时利用 key 的 hashCode()：
private int hash(K key) {
if (key == null) return 0; // 允许 null 键
// 简单起见，直接取 hashCode 然后取绝对值，再取模
return Math.abs(key.hashCode()) % table.length;
}6.4 put 方法
步骤：
-
计算下标。
-
遍历该下标对应的链表，如果找到相同 key（用
equals判断），则更新 value 并返回旧值。 -
如果没找到，将新节点插入链表头部（或尾部，这里用头部方便）。
public V put(K key, V value) {
int index = hash(key);
Entry<K, V> current = table[index];
// 遍历链表，查找是否已存在相同 key
while (current != null) {
if (keyEquals(current.key, key)) {
V oldValue = current.value;
current.value = value;
return oldValue; // 返回旧值
}
current = current.next;
}
// 没找到，插入新节点（头插法）
Entry<K, V> newEntry = new Entry<>(key, value, table[index]);
table[index] = newEntry;
size++;
return null;
}
// 比较两个 key 是否相等，考虑 null
private boolean keyEquals(K k1, K k2) {
if (k1 == k2) return true;
if (k1 == null || k2 == null) return false;
return k1.equals(k2);
}6.5 get 方法
步骤：
-
计算下标。
-
遍历链表，找到 key 相等的节点，返回其 value。
-
如果没找到，返回 null。
汇聚全球AI编程工具，助力开发者即刻编程。
更多推荐
3
0- 0
已为社区贡献4条内容
所有评论(0)