hash-table 标签归档

共 3 篇文章 · 返回首页

Cuckoo Hashing：用两个位置换取最坏情况常数查找

从 Pagh–Rodler 的两表插入与 cuckoo 图出发，用可复现实验核对失败概率、stash、d-ary 与分桶的负载阈值和两种插入搜索的代价，再对照 MemC3、libcuckoo、DPDK、OVS 源码说明并发读写怎样避免假未命中。

用可复现的探测次数模拟核对 Knuth 的线性探测公式，比较链式、线性探测、Robin Hood、双重哈希与 SwissTable 分组探测的探测分布和删除策略，再对照 CPython 3.13、JDK 21、Go 1.23/1.24、Abseil、Redis 7.4 的源码说明各自的取舍。

从 Redis 7.4/8.x 的 dict 源码拆解链式哈希、双表渐进 rehash、rehashidx 步进与 DICT_RESIZE_AVOID 在 fork 期的行为，并对照站内哈希表内部文章说明与教科书一次性扩容的差异。