链式哈希表与开放寻址哈希表的缓存性能对比

让我一步步拆解这些问题，帮你彻底搞懂哈希表和缓存之间的关联：

1. 链式哈希表缓存性能差的成因是什么？ #

核心问题出在内存局部性上。链式哈希表处理冲突时，会把冲突的键值对存在独立的链表节点里，这些节点是在堆内存中分散分配的——也就是说，每个链表节点的内存地址是不连续的。

而CPU缓存的工作逻辑是按缓存行（通常64字节）加载数据，会一次性把连续的内存块加载到缓存里。当你遍历链式哈希表的冲突链表时，每次访问下一个节点都得跳转到一个新的、不连续的内存地址，这大概率会触发缓存未命中（cache miss），CPU不得不从速度慢得多的主存里加载数据，反复下来就拖慢了整体性能。

2. 缓存在此场景中发挥作用的位置是哪里？ #

这里说的是CPU的高速缓存（L1/L2/L3缓存），它是CPU和主存之间的“高速中转站”。

主存的访问速度比CPU运算速度慢几个数量级，CPU会把近期可能频繁访问的主存数据提前加载到缓存里。当哈希表需要访问某个键值对时，首先会在缓存里找，如果找到就直接用（缓存命中），速度极快；找不到才去主存取（缓存未命中），这会产生明显的延迟。哈希表的性能很大程度上就取决于缓存命中率的高低。

3. 为何开放寻址哈希表缓存性能更优？ #

开放寻址哈希表的所有数据都存在一个连续的数组里，哪怕遇到哈希冲突，也是在数组的相邻或邻近位置（比如线性探测、二次探测）寻找空闲槽位。

这种连续的内存布局完美契合CPU缓存的工作机制：当你访问数组中的某个元素时，CPU会自动把该元素所在的整个缓存行（包含周边连续的数组元素）加载到缓存里。后续访问冲突的元素时，这些元素很大概率已经在缓存里了，缓存命中率大幅提升，自然性能更优。

另外，开放寻址不需要额外的链表节点指针开销，内存利用率更高，缓存能容纳更多有效数据，进一步强化了缓存优势。

4. 选择哈希表实现方式时还需考虑哪些因素？ #

除了缓存性能，还有这些关键因素要权衡：

• 哈希冲突与聚集问题：如果键的分布容易导致大量冲突，开放寻址可能出现“聚集”（连续多个槽位被占用），导致探测路径变长；链式哈希表的冲突只会影响单个链表，性能下降更平缓。
• 内存开销：链式哈希表每个节点需要额外的指针空间，内存开销更大；开放寻址用数组存储，空间更紧凑，但需要预留一定的空槽（负载因子通常不超过0.7-0.8），否则冲突会急剧增加。
• 并发安全实现难度：链式哈希表可以对单个链表加锁，实现细粒度的并发控制；开放寻址因为是连续数组，锁的粒度通常更大，无锁实现也更复杂。
• 删除操作复杂度：开放寻址不能直接删除元素（会破坏探测链），需要标记为“已删除”的占位符；链式哈希表可以直接删除链表节点，逻辑更简单。
• 负载因子容忍度：链式哈希表的负载因子可以很高（甚至超过1），因为链表可以无限延伸；开放寻址的负载因子一旦过高，性能会暴跌，需要频繁扩容。

内容的提问来源于stack exchange，提问作者Trajan