本文深入解析哈希表数据结构，以 Java HashMap 为例分析其核心原理与源码实现。涵盖哈希函数设计、冲突解决机制（链表转红黑树）、扩容策略及负载因子选择等关键决策。同时对比开放寻址法等其他方案，提供性能分析与最佳实践建议，帮助开发者理解哈希表背后的设计哲学并优化实际使用。
哈希表（Hash Table）是计算机科学中最重要的数据结构之一，它以近乎 O(1) 的时间复杂度提供了快速的插入、查找和删除操作。从编程语言的内置字典（如 Python 的 dict、Java 的 HashMap）到数据库索引，哈希表无处不在。本文将深入探讨哈希表的工作原理，分析其经典实现的源码，并解释背后的设计决策。
哈希表的核心思想是通过哈希函数将键（key）映射到数组的索引位置，从而实现快速访问。这个过程可以描述为：
index = hash_function(key) % array_size
理想情况下，每个键都会映射到唯一的索引位置，但实际上会发生哈希冲突（collision），即不同的键映射到相同的索引。
一个完整的哈希表实现包含以下核心组件：
让我们通过 Java 8 的 HashMap 源码来理解哈希表的实际实现。
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
// 默认初始容量 - 必须是 2 的幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表转红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转回链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 底层数组
transient Node<K,V>[] table;
// 实际存储的键值对数量
transient int size;
// 扩容阈值 = capacity * loadFactor
int threshold;
// 负载因子
final float loadFactor;
}
HashMap 使用链表法解决冲突，每个数组位置存储一个链表（或红黑树）的头节点：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
// 缓存的哈希值
final K key;
V value;
Node<K,V> next;
// 指向下一个节点
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
}
static final int hash(Object key) {
int h;
// 将高 16 位与低 16 位进行异或运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
设计原因分析：
这个看似简单的操作实际上非常精妙：
h ^ (h >>> 16) 将高 16 位的信息混合到低 16 位中public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 1. 检查 table 是否为空，计算索引位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 2. 检查第一个节点
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 3. 遍历链表或红黑树
if ((e = first.next) != null) {
if (first instanceof TreeNode)
// 红黑树查找
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 链表查找
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
关键点：
(n - 1) & hash 而不是 hash % n 计算索引，这是一个重要的优化public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 1. 如果 table 为空，进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2. 如果目标位置为空，直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 3. 如果 key 已存在于第一个节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 4. 如果是红黑树节点
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 5. 链表插入
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 链表长度达到阈值，转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 6. 如果 key 已存在，更新 value
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
return oldValue;
}
}
++modCount;
// 7. 检查是否需要扩容
if (++size > threshold)
resize();
return null;
}
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 已达到最大容量
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 容量翻倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
// ... 初始化逻辑
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 重新哈希所有元素
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
// 单个节点直接重新定位
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 红黑树拆分
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// 链表拆分
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 巧妙的位运算判断
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
原因：
hash % capacity 等价于 hash & (capacity - 1)，位运算比取模快得多(e.hash & oldCap) == 0就能判断举例说明：
假设 oldCap = 16 (10000)，newCap = 32 (100000) hash = 21 (10101)
oldCap - 1 = 15 (01111) 21 & 15 = 5 // 原位置
21 & oldCap = 21 & 16 = 16 (10000) != 0 所以新位置 = 5 + 16 = 21
这是时间和空间的权衡：
0.75 是根据泊松分布统计得出的经验值，在这个负载因子下：
背景：链表查找是 O(n)，红黑树是 O(log n)
原因：
(h = key.hashCode()) ^ (h >>> 16)
原因：
除了链地址法（Chaining），还有其他解决冲突的方法：
当发生冲突时，在数组中寻找下一个空位置。
线性探测：
def insert(key, value):
index = hash(key) % size
while table[index] is not None:
if table[index].key == key:
table[index].value = value # 更新
return
index = (index + 1) % size # 线性探测
table[index] = Entry(key, value)
优点：
缺点：
探测序列：h(k), h(k)+1², h(k)+2², h(k)+3², ...
缓解了线性探测的聚集问题。
使用第二个哈希函数决定探测步长：
index = (hash1(key) + i * hash2(key)) % size
| 操作 | 平均情况 | 最坏情况 |
|---|---|---|
| 查找 | O(1) | O(n) 或 O(log n)* |
| 插入 | O(1) | O(n) 或 O(log n)* |
| 删除 | O(1) | O(n) 或 O(log n)* |
*使用红黑树优化后最坏情况为 O(log n)
O(n)，其中 n 是存储的键值对数量。
实际空间占用为：n / loadFactor
public class CustomKey {
private String id;
private int type;
@Override
public int hashCode() {
// 使用 Objects.hash 或自行实现
return Objects.hash(id, type);
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
CustomKey other = (CustomKey) obj;
return type == other.type && Objects.equals(id, other.id);
}
}
重要规则：
// 如果知道大概会存储 1000 个元素
int expectedSize = 1000;
int initialCapacity = (int) (expectedSize / 0.75f + 1.0f);
Map<String, String> map = new HashMap<>(initialCapacity);
避免多次扩容带来的性能开销。
HashMap 不是线程安全的，多线程环境下应该使用：
ConcurrentHashMap：分段锁机制，高并发性能好Collections.synchronizedMap()：方法级同步，性能较差Hashtable：已过时，不推荐哈希表是一个精妙的数据结构，它的高效性来自于多个层面的优化：
理解这些设计决策不仅能帮助我们更好地使用哈希表，也能启发我们在设计其他系统时如何平衡时间、空间和实现复杂度。
本文基于 Java 8 的 HashMap 实现进行分析，不同版本可能有所差异。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online