哈希表：冲突策略、设计实现与一致性哈希
哈希表是面试中出现频率最高的数据结构之一。从 Two Sum 到 LRU Cache，从 Python dict 到 Redis Hash，哈希表的原理和应用贯穿整个技术栈。
一、核心原理
哈希表通过哈希函数将键映射到数组索引，实现平均 O(1) 的查找、插入、删除。
键(key) → 哈希函数(hash) → 索引(index) → 数组[索引] = 值(value)
理想情况 vs 冲突
- 理想：每个键映射到唯一索引，所有操作 O(1)
- 现实：不同键映射到同一索引 → 哈希冲突（Collision）
二、冲突解决策略
1. 拉链法（Separate Chaining）
每个桶（bucket）维护一个链表（或红黑树），冲突元素链入同一桶。
class HashTable:
def __init__(self, capacity=16):
self.capacity = capacity
self.size = 0
self.buckets = [[] for _ in range(capacity)]
def _hash(self, key):
return hash(key) % self.capacity
def put(self, key, value):
idx = self._hash(key)
bucket = self.buckets[idx]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
self.size += 1
if self.size > self.capacity * 0.75:
self._resize()
def get(self, key):
idx = self._hash(key)
for k, v in self.buckets[idx]:
if k == key:
return v
raise KeyError(key)
def _resize(self):
old_buckets = self.buckets
self.capacity *= 2
self.size = 0
self.buckets = [[] for _ in range(self.capacity)]
for bucket in old_buckets:
for k, v in bucket:
self.put(k, v)
优点：简单易实现，删除方便
缺点：缓存不友好（链表节点离散）
2. 开放寻址法（Open Addressing）
冲突时按探测序列寻找下一个空位。Python dict 使用此方法。
线性探测：h(k, i) = (hash(k) + i) % m
二次探测：h(k, i) = (hash(k) + c1·i + c2·i²) % m
双重哈希：h(k, i) = (hash1(k) + i·hash2(k)) % m
class OpenAddressingHashTable:
def __init__(self, capacity=16):
self.capacity = capacity
self.size = 0
self.table = [None] * capacity
self.DELETED = object() # 标记已删除
def _hash(self, key, i):
return (hash(key) + i) % self.capacity
def put(self, key, value):
for i in range(self.capacity):
idx = self._hash(key, i)
if self.table[idx] in (None, self.DELETED):
self.table[idx] = (key, value)
self.size += 1
return
elif self.table[idx][0] == key:
self.table[idx] = (key, value)
return
raise RuntimeError("Hash table full")
def get(self, key):
for i in range(self.capacity):
idx = self._hash(key, i)
if self.table[idx] is None:
raise KeyError(key)
if self.table[idx] is not self.DELETED and self.table[idx][0] == key:
return self.table[idx][1]
raise KeyError(key)
优点：缓存友好，无指针开销
缺点：删除复杂（需要标记），装载因子受限（< 0.75）
三、复杂度分析
| 操作 | 平均 | 最坏 |
|---|---|---|
| 查找 | O(1) | O(n) — 所有键冲突 |
| 插入 | O(1) | O(n) |
| 删除 | O(1) | O(n) |
均摊 O(1) 的前提是：哈希函数分布均匀、装载因子合理、动态扩容。
四、经典面试题：LRU 缓存
LeetCode 146，要求实现 O(1) 的 get 和 put。
class ListNode:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {}
self.head = ListNode()
self.tail = ListNode()
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_to_head(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self._remove(node)
self._add_to_head(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.cache:
node = self.cache[key]
node.val = value
self._remove(node)
self._add_to_head(node)
else:
if len(self.cache) >= self.capacity:
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]
node = ListNode(key, value)
self.cache[key] = node
self._add_to_head(node)
设计要点：
- 哈希表：O(1) 定位节点
- 双向链表：O(1) 移动节点到头部 / 删除尾部
五、一致性哈希（Consistent Hashing）
分布式系统中，普通哈希在节点增减时会导致大量数据迁移。
问题
普通哈希：server = hash(key) % N。N 变化时，几乎所有数据的映射都改变。
解决方案
将节点和数据都映射到同一个哈希环上，数据归属于顺时针第一个节点。
0
3 1
2
Node A (hash=1), Node B (hash=6), Node C (hash=9)
Data x (hash=5) → 顺时针第一个节点 = Node B (6)
虚拟节点：每个物理节点对应多个虚拟节点，解决数据倾斜问题。
优点：
- 增删节点只影响相邻区间，迁移量从 O(N) 降到 O(K/N)
- 天然支持负载均衡（配合虚拟节点）
应用：Redis Cluster、Nginx 负载均衡、分布式缓存（Memcached）。
六、面试高频问题
Q: Python dict 为什么是有序的？
Python 3.7+ dict 使用开放寻址法 + 紧凑数组存储。索引数组记录插入顺序，遍历时不依赖哈希值顺序。
Q: 装载因子（Load Factor）为什么通常设为 0.75？
权衡时间和空间：太高则冲突增多（性能下降），太低则空间浪费。0.75 是经验值，Java HashMap 也是此值。
Q: 如何设计一个线程安全的哈希表？
- 粗粒度锁：全局锁，简单但并发度低
- 分段锁（ConcurrentHashMap）：锁分段，提高并发
- 无锁：CAS 操作，如 Java 的 ConcurrentHashMap（JDK8+）
相关文章：
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。