主题
哈希进阶：开放定址、扩容策略与工程实现
1. 基础哈希表讲完后，为什么还不够
基础章已经回答了两个问题：
- 哈希表为什么平均查找快。
- 拉链法为什么能处理冲突。
但如果想真正理解工程级哈希表，还需要继续往下追：
- 为什么有些实现不用链表，而用开放定址？
- 删除为什么会比插入更微妙？
- 扩容为什么不能简单粗暴地“一次性全搬”？
- 一致性哈希为什么被分布式系统反复使用？
这些问题共同决定了哈希表从“课堂结构”走向“系统部件”的质量。
2. 开放定址：把元素直接放在桶数组里
开放定址法不再让每个桶挂链表，而是要求元素本身就落在桶数组中。冲突时，按照某种探测规则寻找下一个可用槽位。
开放定址的优点：
- 内存布局更紧凑。
- 缓存局部性通常更好。
- 不需要每个桶再持有链式节点对象。
缺点：
- 删除更麻烦。
- 高装载因子下性能下降更明显。
- 探测策略不好时容易形成聚集。
3. 三种常见探测方式
3.1 线性探测
冲突后依次检查：
text
h, h+1, h+2, h+3 ...优点是实现简单、局部性好；缺点是容易形成主聚集（primary clustering）。
3.2 二次探测
text
h+1^2, h+2^2, h+3^2 ...它能缓解主聚集，但实现和表长选择更讲究。
3.3 双重哈希
用第二个哈希函数决定步长。好处是分布往往更均匀，但计算成本更高。
4. 删除为什么会破坏查找链
在线性探测表里，若直接把某个槽位删成“空”，后续查找可能提前停止，误以为某个本应继续探测到的键不存在。
因此，开放定址里的删除通常需要“墓碑标记”（tombstone）：
- 这个位置当前没有元素。
- 但查找不能在这里停，还要继续探测。
go
package openaddr
type state uint8
const (
empty state = iota
occupied
deleted
)
type entry struct {
key int
value int
mark state
}这说明哈希表真正难的地方，常常不是“怎么存进去”，而是“怎么在长期更新后仍保持正确与高效”。
5. Go 实现一个线性探测哈希表
go
package openaddr
import "fmt"
type Map struct {
table []entry
size int
}
func New(capacity int) *Map {
if capacity < 8 {
capacity = 8
}
return &Map{
table: make([]entry, capacity),
}
}
func (m *Map) hash(key int) int {
if key < 0 {
key = -key
}
return key % len(m.table)
}
func (m *Map) Put(key, value int) {
if float64(m.size+1)/float64(len(m.table)) > 0.6 {
m.resize()
}
idx := m.hash(key)
firstDeleted := -1
for {
slot := &m.table[idx]
switch slot.mark {
case empty:
if firstDeleted != -1 {
idx = firstDeleted
slot = &m.table[idx]
}
*slot = entry{key: key, value: value, mark: occupied}
m.size++
return
case deleted:
if firstDeleted == -1 {
firstDeleted = idx
}
case occupied:
if slot.key == key {
slot.value = value
return
}
}
idx = (idx + 1) % len(m.table)
}
}
func (m *Map) Get(key int) (int, error) {
idx := m.hash(key)
for {
slot := m.table[idx]
if slot.mark == empty {
return 0, fmt.Errorf("not found")
}
if slot.mark == occupied && slot.key == key {
return slot.value, nil
}
idx = (idx + 1) % len(m.table)
}
}
func (m *Map) Delete(key int) bool {
idx := m.hash(key)
for {
slot := &m.table[idx]
if slot.mark == empty {
return false
}
if slot.mark == occupied && slot.key == key {
slot.mark = deleted
m.size--
return true
}
idx = (idx + 1) % len(m.table)
}
}
func (m *Map) resize() {
old := m.table
m.table = make([]entry, len(old)*2)
m.size = 0
for _, e := range old {
if e.mark == occupied {
m.Put(e.key, e.value)
}
}
}5.1 这段代码揭示了什么
- 开放定址删除不等于简单清空。
- 装载因子不能太高，否则探测链会变长。
- 扩容后必须重新安置元素，因为取模基数变了。
6. 装载因子不是“参考数字”，而是性能阈值
装载因子：
text
loadFactor = 元素个数 / 桶数它越高，说明表越满。表越满，冲突越多，探测链越长，插入和查找就越慢。
不同实现对阈值容忍不同：
- 链式哈希常见阈值可以更高。
- 开放定址通常更怕过满。
因此，扩容策略本质上是用空间换时间。
7. 一次性扩容与渐进式扩容
最朴素的扩容方式是一次性 rehash：
新建更大的桶数组，把旧元素全部重新插入。
优点：
- 逻辑简单。
- 实现容易。
缺点：
- 单次扩容停顿明显。
- 大表扩容时对延迟敏感场景不友好。
工程上还会出现渐进式扩容：
- 同时维护旧表和新表。
- 每次普通读写时顺带搬一点元素。
- 用更平滑的方式摊掉扩容成本。
这已经不只是算法问题，而是系统延迟控制问题。
8. Robin Hood 哈希的思想
Robin Hood Hashing 的核心直觉是：
探测距离远的元素“更穷”，应该优先占据更好的位置。
它会在插入时比较“谁离理想位置更远”，必要时进行交换，把探测距离尽量拉平。这样做的好处是减少极端长探测链，提高整体稳定性。
你不一定需要立刻手写它，但应当知道：
现代哈希表实现已经不只是“随便找个空槽”这么简单，而是在局部性、均匀性和最坏探测长度之间做细致权衡。
9. Go 的 map 为什么不等于“哈希表已经学完”
Go 的 map 很强，但如果只会调用它，不理解底层，就会错过很多关键判断：
- 为什么遍历顺序不稳定。
- 为什么键类型要可比较。
- 为什么并发读写会出问题。
- 为什么大规模扩容会影响性能曲线。
学习数据结构的目的，不是为了拒绝标准库，而是为了知道标准库背后做了什么选择。
10. 并发环境下为什么哈希表更难
并发下的问题不只是“加锁”：
- 读写是否会竞争同一个桶。
- 扩容时旧表和新表如何切换。
- tombstone 与迁移状态如何保持一致。
- 锁粒度太粗会影响吞吐，太细又会让实现复杂。
这也是为什么高性能并发哈希表常常是系统设计中的难点，而不是普通容器题。
11. 一致性哈希：从单机结构到分布式映射
一致性哈希解决的是：
当节点集合变化时，如何尽量少地移动已有键的归属。
11.1 普通取模的问题
若把键直接映射为：
text
server = hash(key) % N一旦 N 改变，大量键都会落到不同节点上。
11.2 一致性哈希环
一致性哈希把服务器和键都映射到一个环上，键归属于顺时针遇到的第一个服务器节点。
节点增减时，只会影响局部区间。这就是它在缓存系统、分布式存储、负载均衡里的价值。
12. 学完哈希进阶后应该抓住什么
- 冲突解决不是只有拉链法。
- 删除是开放定址里真正容易踩坑的地方。
- 扩容策略影响的不只是复杂度表，还有延迟尖峰。
- 一致性哈希说明“哈希思想”可以从单机容器扩展到分布式系统。
把这些点看清，哈希表就不再只是“平均 O(1)”那一句口号。