该库是C++实现的快速哈希映射和哈希集合，采用开放寻址和hopscotch哈希解决冲突。它比std::unorderedmap性能更好，与google::densehash_map类似但内存更少、功能更多，提供多种类以适应不同哈希函数需求。

好的，这是根据您的要求，对原文主要内容进行的中文重述：

标题： GitHub - Tessil/hopscotch-map：一个使用hopscotch哈希实现的快速C++哈希映射和哈希集合库

核心内容：

hopscotch-map 是一个C++库，它通过开放寻址法和hopscotch哈希来解决冲突，实现了快速的哈希映射和哈希集合。该数据结构对缓存友好，在大多数情况下性能优于 std::unordered_map，并且与 google::dense_hash_map 性能相近，但内存占用更少，功能更丰富。

主要类：

库提供了两类主要类：

1. tsl::hopscotch_map 和 tsl::hopscotch_set：默认选择，性能更优，采用2的幂次方增长策略。
2. tsl::hopscotch_pg_map 和 tsl::hopscotch_pg_set：采用素数增长策略，能更好地应对较差的哈希函数。如果哈希值的低位可能出现重复模式（例如，使用身份哈希函数存储指针），建议使用此版本。

此外，还有对应的“安全”版本：tsl::bhopscotch_map、tsl::bhopscotch_set 及其 pg 版本。这些版本要求键必须是“可小于比较的”（LessThanComparable），但提供了更好的渐近上界，能抵御哈希表拒绝服务（DoS）攻击。不过，如果没有特定需求，默认选择 tsl::hopscotch_map 和 tsl::hopscotch_set 通常就足够了。

主要特性：

• 仅头文件库：只需将 include 目录添加到包含路径即可使用。
• 高性能：基准测试显示其性能优异。
• 支持移动语义：支持仅移动和不可默认构造的键/值。
• 异构查找：允许使用与键类型不同的类型进行 find 操作。
• 无需预留哨兵值。
• 可存储哈希值：通过 StoreHash 模板参数，可在插入时存储哈希值，以加速重哈希和查找。
• 预计算哈希：如果查找前已知哈希值，可将其作为参数传入以加速查找。
• 抗DoS攻击：tsl::bhopscotch_map 和 tsl::bhopscotch_set 提供 O(log n) 的最坏情况查找和删除性能。
• 支持禁用异常：可通过编译选项或定义 TSL_NO_EXCEPTIONS 来禁用异常。
• API 与 std::unordered_map 和 std::unordered_set 高度相似。

与 std::unordered_map 的主要区别：

• 迭代器失效：除 erase 外，任何修改哈希表的操作都会使所有迭代器失效。
• 引用和指针失效：插入操作会使指向键或值的引用和指针失效，与迭代器失效规则相同。
• 迭代器返回值：operator*() 和 operator->() 返回 const std::pair<Key, T> 的引用和指针，而非 std::pair<const Key, T>。要修改值，需调用迭代器的 value() 方法。
• 移动语义要求：仅移动类型必须具有不抛异常的移动构造函数。
• 不支持桶相关方法：如 bucket_size、bucket 等。

增长策略：

库通过 GrowthPolicy 模板参数支持多种增长策略：

• tsl::hh::power_of_two_growth_policy：默认策略，将桶数组大小保持为2的幂次方，使用位运算代替取模，速度快，但可能因哈希函数不佳导致大量冲突。
• tsl::hh::prime_growth_policy：默认用于 pg 版本，将桶数组大小保持为素数，即使哈希函数不佳也能使哈希分布更均匀，速度较慢但更安全。
• tsl::hh::mod_growth_policy：通过可自定义的增长因子来增长映射，直接使用取模运算，速度最慢但最灵活。

如果遇到性能问题，可以检查 overflow_size() 是否非零，以判断是否存在大量哈希冲突。可以尝试更换哈希函数或使用 tsl::hh::prime_growth_policy。

安装与使用：

• 将 include 目录添加到包含路径即可。
• 如果使用CMake，可以通过 add_subdirectory 或 find_package 来使用。
• 代码兼容C++17标准。
• 运行测试需要Boost Test库和CMake。

示例：

代码示例展示了如何创建、插入、遍历和查找 tsl::hopscotch_map 和 tsl::hopscotch_set，包括使用 value() 方法修改值、使用预计算哈希加速查找，以及通过 StoreHash 参数存储哈希值。

异构查找示例：

通过定义 KeyEqual::is_transparent 类型，可以启用异构查找，允许使用其他类型（如整数）来查找以自定义对象为键的映射。

DoS攻击示例：

通过一个总是返回相同哈希值的“坏”哈希函数模拟DoS攻击，展示了 tsl::bhopscotch_map 相比 tsl::hopscotch_map 在插入大量元素时的性能优势（从110毫秒降至2毫秒），体现了其抗攻击能力。

许可：

该库采用MIT许可证。

根据评论内容，总结如下：

主要观点与论据：

1. 性能对比与现状：多位评论者指出，当前更优的哈希表实现（如boost::unorderedflatset、absl、folly）性能远超标准库。nly 强调“缓存行性能难以被击败（SIMD优化线性扫描）”，并推荐“boost::unorderedflatset paired with rapidhash”。jll29 则指出“google::densehashmap 在基准测试中运行时最低”。

2. 与类似算法的比较：teo_zero 认为 hopscotch 与 robin hood 哈希“性能曲线非常接近”，并倾向于“更知名的 robin hood”。mgaunard 询问与“boost unordered flat map”的对比，并指出基准测试“最后更新于2019年”。

3. 实现原理与局限性：einpoklum 引用维基百科解释 hopscotch 原理，并指出实际应用中“可以放弃部分元素的哈希处理，将其单独处理”，而标准实现“必须成功插入所有值，导致更多冲突和扩容”。

4. 个人经验：stevefan1999 分享10年前在CSGO作弊软件中使用 hopscotch 哈希的经历，最终发现“性能不会因架构而提升”，并提到后来学习了“Cuckoo Hashing 和 Robinhood hash 的组合”。

平衡性总结：评论呈现了 hopscotch 哈希的优缺点——性能接近同类算法但非最优，实际应用需考虑工作负载特性，且已有更现代的实现（如boost、absl）在缓存性能上更具优势。