趣谈哈希表优化：从规避 Hash 冲突到利⽤ Hash 冲突

趣谈哈希表优化：从规避 Hash 冲突到利⽤ Hash 冲突

摘要

本文从哈希表传统设计与解决思路入手，深入浅出地引出新的设计思路：从尽量规避哈希冲突，转向了利⽤合适的哈希冲突概率来优化计算和存储效率。新的哈希表设计表明 SIMD 指令的并⾏化处理能⼒的有效应⽤能⼤幅度提升哈希表对哈希冲突的容忍能⼒，进⽽提升查询的速度，并且能帮助哈希表进⾏极致的存储空间压缩。