基于hopscotch哈希的快速哈希映射与哈希集合的C++实现
该项目提供了一个高效的C++哈希映射和哈希集合实现,采用hopscotch哈希算法。与标准库中的std::unordered_map和std::unordered_set相比,它在查找、插入和删除操作上具有更快的性能,同时保持了良好的内存局部性和缓存友好性。
背景速读
- **hopscotch-map** 是一个 C++ 开源库,由开发者 Tessil 维护,提供基于**跳房子哈希(hopscotch hashing)** 算法的高性能哈希表(hash map)和哈希集合(hash set)实现。
- **跳房子哈希**是一种 2008 年提出的哈希表冲突解决算法,结合了开放寻址(open addressing)和布谷鸟哈希(cuckoo hashing)的优点,特点是每个桶有一个"邻域"(neighbourhood),冲突元素只需在邻域内移动,从而获得极佳的缓存局部性和插入/查找速度。
- 这个库对标的是 C++ 标准库中的 `std::unordered_map` / `std::unordered_set`,在密集负载下往往延迟更低、吞吐更高。Tessil 还维护了同系列的 `tsl::sparse_map`(节省内存)和 `tsl::ordered_map`(保持插入顺序)等库,合称 **Tessil 哈希库**,在 C++ 性能敏感项目中广为使用。
- 如果读者遇到讨论"高并发键值存储""实时系统""游戏引擎"或"高频交易"等场景下的 C++ 数据结构选择,hopscotch-map 常被列为比标准库更快的选项之一。