My favourite small hash table
5 months ago
- #data-structures
- #hash-table
- #optimization
- 文章讨论了一种特定的哈希表设计，采用罗宾汉开放寻址法结合线性探测和二次幂表大小。
- 键为32位整数，值同样为32位整数，使得键值对可以存储为64位整数。
- 哈希表结构包含槽位（64位整数数组）、掩码（表大小减一）以及非空槽位计数。
- 查找过程涉及检查键的自然位置，若发生冲突则线性探测，并通过评分函数决定终止条件。
- 插入操作会检查现有键，必要时通过重新插入键处理冲突，并在75%负载因子时触发表扩容。
- 键删除通过左移槽位直到遇到空槽或评分为零的槽位实现，避免了墓碑标记的需求。
- 迭代过程直接遍历数组并过滤空槽位。
- 该设计可通过可逆哈希函数扩展至非随机分布键，或通过分离存储支持更大的键值对。
- 文章指出其局限性，例如不适用于无锁并发场景或需要特定硬件指令的情况。