跳房子映射库是一个使用开放寻址和跳房子哈希来解决冲突的快速哈希映射和哈希集合的C++实现。它是一个缓存友好的数据结构，在大多数情况下比std::unordered_map提供更好的性能，并且与google::dense_hash_map非常相似，同时占用更少的内存并提供更多的功能。该库提供了以下主要类：tsl::hopscotch_map，tsl::hopscotch_set，tsl::hopscotch_pg_map和tsl::hopscotch_pg_set。前两者更快，并采用二次幂增长策略，后两者则采用素数增长策略，因此能够更好地应对较差的哈希函数。如果你的哈希在低位可能出现重复模式（例如，你在存储使用身份哈希函数的指针），请使用素数版本。有关详细信息，请参见增长策略。除了这些类，库还提供了tsl::bhopscotch_map，tsl::bhopscotch_set，tsl::bhopscotch_pg_map和tsl::bhopscotch_pg_set。这些类对键有额外要求，它必须是可比较的小于关系（LessThanComparable），但它们提供更好的渐近上界，具体细节请参见示例。然而，如果你没有特定需求（哈希拒绝服务攻击的风险），tsl::hopscotch_map和tsl::hopscotch_set在大多数情况下应该是足够的，并且应该作为你的默认选择，因为它们通常表现更好。跳房子哈希和一些实现细节的概述可以在这里找到。tsl::hopscotch_map与其他哈希映射的基准测试可以在这里找到。该页面还提供了一些建议，告诉你应该尝试哪种哈希表结构（如果你对tsl命名空间中的多个哈希表实现感到困惑，这非常有用）。关键特性：仅头文件库，只需将包含目录添加到您的包含路径即无需其他操作即可开始。如果您使用CMake，您还可以使用CMakeLists.txt中导出的tsl::hopscotch_map目标。快速哈希表，基准测试中可见一些数字。支持仅移动和不可默认构造的键/值。支持异构查找，允许使用与键不同的类型调用find（例如，如果你有一个使用std::unique_ptr<foo>作为键的映射，你可以使用foo*或std::uintptr_t作为键参数进行查找，而不需要构造一个std::unique_ptr<foo>，请参见示例）。无需从键中保留任何哨兵值。能够在插入时存储哈希值，以便在哈希或键相等函数计算开销较大的情况下加快重新哈希和查找（请参见StoreHash模板参数）。如果在查找之前已知哈希值，则可以将其作为参数传递以加速查找（请参见API中的precalculated_hash参数）。tsl::bhopscotch_map和tsl::bhopscotch_set在查找和删除时提供O(log n)的最坏情况，使这些类对哈希表拒绝服务（DoS）攻击具有抵抗力（详情请见示例）。该库可以在禁用异常的情况下使用（通过在Clang和GCC上使用-fno-exceptions选项，在MSVC上没有/EH选项，或简单地定义TSL_NO_EXCEPTIONS）。在禁用异常时，std::terminate用于替代throw指令。API与std::unordered_map和std::unordered_set非常相似。与std::unordered_map相比的区别：tsl::hopscotch_map试图具有与std::unordered_map类似的接口，但存在一些差异。插入时的迭代器失效行为不同。一般来说，除erase外，所有修改哈希表的操作都会使所有迭代器失效（有关详细信息，请参见API）。在插入时，地图中对键或值的引用和指针以与这些键值的迭代器相同的方式失效。对于迭代器，operator*()和operator->()返回对const std::pair<Key, T>的引用和指针，而不是std::pair<const Key, T>，使得值T不可修改。要修改值，必须调用迭代器的value()方法以获取可变引用。例如：tsl::hopscotch_map<int, int> map = {{1, 1}, {2, 1}, {3, 1}}; for (auto it = map.begin(); it != map.end(); ++it) { // it->second = 2; // 不合法 it.value() = 2; // 合法 } 仅移动类型必须具有不抛出异常的移动构造函数（由于开放寻址，在重新哈希时，如果移动构造函数可能抛出，则无法保持强异常保证）。不支持某些与桶相关的方法（如bucket_size，bucket等）。这些差异也适用于std::unordered_set与tsl::hopscotch_set之间。线程安全性和异常保证与std::unordered_map/set相同（即可能有多个读取器，无写入者）。增长策略：该库通过GrowthPolicy模板参数支持多种增长策略。库提供了三种策略，但如果需要，可以轻松实现自己的策略。tsl::hh::power_of_two_growth_policy：tsl::(b)hopscotch_map/set使用的默认策略。该策略保持