哈希表内部：开放寻址、链式、Robin Hood 的三国演义
内容提要
哈希表是计算机科学中常用的数据结构，主要有链式哈希和开放寻址两种冲突解决策略。链式哈希简单可靠，但缓存不友好；开放寻址更高效，特别是线性探测和Robin Hood哈希。Robin Hood通过交换位置优化探测长度，减少最坏情况的性能下降。不同策略在负载因子下表现各异，Swiss Table在性能上表现最佳。
关键要点
-
哈希表是计算机科学中使用频率最高的数据结构，主要有链式哈希和开放寻址两种冲突解决策略。
-
链式哈希的优点是实现简单可靠，负载因子可以超过1.0，但缺点是缓存不友好，查找时可能导致缓存未命中。
-
开放寻址将所有元素直接存储在桶数组中，冲突时按探测序列寻找空桶，线性探测是最简单且缓存友好的策略。
-
Robin Hood哈希通过交换位置优化探测长度，减少最坏情况的性能下降，且删除操作更为简便。
-
不同策略在不同负载因子下的平均探测长度表现各异，Robin Hood在最坏情况下性能更可预测。
-
Swiss Table在所有负载因子下表现最佳，利用SIMD指令并行处理多个元素，提升性能。
-
哈希表的扩容策略通常是翻倍容量，Redis采用渐进式rehash以避免大停顿。
-
在真实工作负载中，Swiss Table的查找和插入吞吐量均优于其他哈希表实现。
延伸问答
哈希表的主要冲突解决策略有哪些？
哈希表的主要冲突解决策略有链式哈希和开放寻址。
链式哈希的优缺点是什么？
链式哈希的优点是实现简单可靠，负载因子可以超过1.0；缺点是缓存不友好，查找时可能导致缓存未命中。
什么是Robin Hood哈希，它有什么优势？
Robin Hood哈希是一种开放寻址策略，通过交换位置优化探测长度，减少最坏情况的性能下降，且删除操作更为简便。
开放寻址的线性探测有什么优势和缺点？
线性探测的优势是缓存友好性，探测序列在内存中是连续的；缺点是可能导致聚集，影响性能。
Swiss Table在哈希表中有什么特别之处？
Swiss Table在所有负载因子下表现最佳，利用SIMD指令并行处理多个元素，提升性能。
哈希表的扩容策略通常是什么？
哈希表的扩容策略通常是翻倍容量，Redis采用渐进式rehash以避免大停顿。
