Cuckoo hashing improves SIMD hash tables
7 months ago
- #hash-tables
- #cuckoo-hashing
- #performance
- 布谷鸟哈希是一种哈希表设计方案，它使用两个哈希函数，在查找时仅搜索固定数量的位置。
- 布谷鸟哈希可与SIMD加速探测结合使用，在许多场景下性能优于标准实现方案。
- 对于缓存内表，布谷鸟哈希通过避免分支预测错误和减少指令数而胜出。
- 对于缓存外表，布谷鸟哈希凭借更短的探测长度占据优势，在高负载因子时尤为明显。
- 布谷鸟哈希支持任意表大小、高效的表大小调整，且不需要墓碑标记条目。
- 由于具有有界探测长度特性，布谷鸟哈希表是传输字典数据的理想线格式。
- 根据使用场景不同，最优的哈希表布局各异，当负载因子超过50%时，布谷鸟哈希通常是最佳选择。