Tessil/hopscotch-map

来源：https://github.com/Tessil/hopscotch-map CI：https://github.com/Tessil/hopscotch-map/actions/workflows/ci.yml

一个使用跳跃哈希的快速哈希映射和哈希集合的C++实现

hopscotch-map 库是一个使用开放寻址和跳跃哈希（hopscotch hashing）解决冲突的快速哈希映射和哈希集合的 C++ 实现。它是一种缓存友好的数据结构，在大多数情况下性能优于 std::unordered_map，与 google::dense_hash_map 性能相近，同时使用更少的内存并提供更多功能。

该库提供以下主要类：tsl::hopscotch_map、tsl::hopscotch_set、tsl::hopscotch_pg_map 和 tsl::hopscotch_pg_set。前两个速度更快，并使用 2 的幂次增长策略；后两个使用素数增长策略，能够更好地处理较差的哈希函数。如果哈希值的低位可能出现重复模式（例如，使用恒等哈希函数存储指针），请使用素数版本。详见 增长策略。

除了这些类外，该库还提供了 tsl::bhopscotch_map、tsl::bhopscotch_set、tsl::bhopscotch_pg_map 和 tsl::bhopscotch_pg_set。这些类对键有额外要求：必须满足 LessThanComparable，但它们提供了更好的渐近上界，详见示例中的 细节。不过，如果没有特定需求（如哈希 DoS 攻击的风险），大多数情况下 tsl::hopscotch_map 和 tsl::hopscotch_set 就足够了，并且应作为默认选择，因为它们通常性能更好。

有关跳跃哈希的概述和实现细节，请参见此处 (https://tessil.github.io/2016/08/29/hopscotch-hashing.html)。

tsl::hopscotch_map 与其他哈希映射的基准测试可以在此找到 (https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html)。该页面还根据您的用例提供了一些关于应该尝试哪种哈希表结构的建议（如果您对 tsl 命名空间中的多个哈希表实现感到困惑，这将很有用）。

主要特性

• 仅头文件库，只需将 include 目录添加到包含路径即可。如果使用 CMake，还可以使用 CMakeLists.txt 中的 tsl::hopscotch_map 导出目标。
• 快速的哈希表，请参见基准测试 (https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html) 查看具体数据。
• 支持仅移动类型和不可默认构造的键/值。
• 支持异构查找，允许使用不同于 Key 的类型进行 find 操作（例如，如果映射使用 std::unique_ptr 作为键，可以使用 foo* 或 std::uintptr_t 作为 find 的键参数，而无需构造 std::unique_ptr，请参见 示例）。
• 无需为键保留任何哨兵值。
• 可以在插入时存储哈希值，以便在哈希或键相等函数计算昂贵时加快重新哈希和查找速度（请参见 StoreHash (https://tessil.github.io/hopscotch-map/classtsl_1_1hopscotch__map.html#details) 模板参数）。
• 如果在查找前已知哈希值，可以将其作为参数传递以加速查找（请参见 API 中的 precalculated_hash 参数 (https://tessil.github.io/hopscotch-map/classtsl_1_1hopscotch__map.html#a74d83c67c50bc8385bb11f78142eaa86)）。
• tsl::bhopscotch_map 和 tsl::bhopscotch_set 在查找和删除操作中提供最坏情况 O(log n) 的复杂度，使这些类能够抵抗哈希表拒绝服务攻击（参见示例中的 细节）。
• 该库可以在禁用异常的情况下使用（通过 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 (https://tessil.github.io/hopscotch-map/classtsl_1_1hopscotch__map.html#details)）。
• 映射中键或值的引用和指针在插入时以与迭代器相同的方式失效。
• 对于迭代器，operator*() 和 operator->() 返回对 const std::pair 的引用和指针，使得值 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. (https://tessil.github.io/hopscotch-map/classtsl_1_1hh_1_1power__of__two__growth__policy.html)
  tsl::(b)hopscotch_map/set 使用的默认策略。该策略将哈希表的桶数组大小保持为 2 的幂。此约束允许策略避免使用慢速的取模运算来将哈希映射到桶，而是使用 hash & (2^n - 1) 代替 hash % 2^n（参见快速取模 (https://en.wikipedia.org/wiki/Modulo_operation#Performance_issues)）。速度快，但如果哈希函数较差，可能会导致大量冲突，因为与 2 的幂次取模最终只屏蔽了最高有效位。

• tsl::hh::prime_growth_policy. (https://tessil.github.io/hopscotch-map/classtsl_1_1hh_1_1prime__growth__policy.html)
  tsl::(b)hopscotch_pg_map/set 使用的默认策略。该策略将哈希表的桶数组大小保持为素数。当将哈希映射到桶时，使用素数作为模数可以更好地将哈希分布在桶中，即使哈希函数较差。为了允许编译器优化取模运算，该策略使用了一个包含常量素数模数的查找表（详见 API (https://tessil.github.io/hopscotch-map/classtsl_1_1hh_1_1prime__growth__policy.html#details)）。比 tsl::hh::power_of_two_growth_policy 慢，但更安全。

• tsl::hh::mod_growth_policy. (https://tessil.github.io/hopscotch-map/classtsl_1_1hh_1_1mod__growth__policy.html)
  该策略通过可自定义的增长因子来增长映射。然后它直接使用取模运算符将哈希映射到桶。速度较慢但更灵活。

如果遇到性能不佳的情况，请检查 overflow_size()，如果它不为零，则可能存在大量哈希冲突。要么更改哈希函数使其更均匀，要么尝试其他增长策略（主要是 tsl::hh::prime_growth_policy）。不幸的是，有时很难防止冲突（例如，对哈希映射的 DoS 攻击）。如果需要，还可以查看 tsl::bhopscotch_map/set，它们在查找时提供 O(log n) 的最坏情况，而不是 O(n)，参见示例中的 细节。

要实现自己的策略，您需要实现以下接口：

struct custom_policy {
    // 在哈希表构造和重新哈希时调用，min_bucket_count_in_out 是哈希表所需的最小桶数。
    // 策略可以根据需要将其更改为更高的桶数，并且哈希表将使用此值作为桶数。
    // 如果请求 0 个桶，则值必须保持为 0。
    explicit custom_policy(std::size_t& min_bucket_count_in_out);
    
    // 返回哈希值所属的桶 [0, bucket_count())。如果 bucket_count() 为 0，则必须始终返回 0。
    std::size_t bucket_for_hash(std::size_t hash) const noexcept;
    
    // 返回下次增长时应使用的桶数
    std::size_t next_bucket_count() const;
    
    // 策略支持的最大桶数
    std::size_t max_bucket_count() const;
    
    // 重置增长策略，如同以桶数 0 创建策略。clear 之后，调用 bucket_for_hash() 时必须始终返回 0。
    void clear() noexcept;
}

安装

要使用 hopscotch-map，只需将 include 目录添加到您的包含路径中。它是一个仅头文件库。如果您使用 CMake，还可以从 CMakeLists.txt 中使用 tsl::hopscotch_map 导出目标，通过 target_link_libraries 链接。

# 示例：将 hopscotch-map 项目存储在第三方目录中
add_subdirectory(third-party/hopscotch-map)
target_link_libraries(your_target PRIVATE tsl::hopscotch_map)

如果项目已通过 make install 安装，您也可以使用 find_package(tsl-hopscotch-map REQUIRED) 而不是 add_subdirectory。

代码应该适用于任何符合 C++17 标准的编译器。要运行测试，您需要 Boost Test 库和 CMake。

git clone https://github.com/Tessil/hopscotch-map.git
cd hopscotch-map/tests
mkdir build
cd build
cmake ..
cmake --build .
./tsl_hopscotch_map_tests

用法

API 可以在此找到 (https://tessil.github.io/hopscotch-map/)。并非所有方法都已记录，但除非另有说明，它们都复制了 std::unordered_map 和 std::unordered_set 中的行为。

示例

#include <iostream>
#include <string>
#include <chrono>
#include <cstdint>
#include <tsl/hopscotch_map.h>
#include <tsl/hopscotch_set.h>

int main() {
    tsl::hopscotch_map<std::string, int> map = {{"a", 1}, {"b", 2}};
    map["c"] = 3;
    map["d"] = 4;
    map.insert({"e", 5});
    map.erase("b");
    
    for(auto it = map.begin(); it != map.end(); ++it) {
        // it->second += 2; // 无效
        it.value() += 2;
    }
    
    // {d, 6} {a, 3} {e, 7} {c, 5}
    for(const auto& key_value : map) {
        std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
    }
    
    if(map.find("a") != map.end()) {
        std::cout << "Found \"a\"." << std::endl;
    }
    
    const std::size_t precalculated_hash = std::hash<std::string>()("a");
    // 如果已经提前知道哈希值，可以将其作为参数传递给查找以加速。
    if(map.find("a", precalculated_hash) != map.end()) {
        std::cout << "Found \"a\" with hash " << precalculated_hash << "." << std::endl;
    }
    
    /*
     * 计算哈希和比较两个 std::string 可能很慢。
     * 我们可以将每个 std::string 的哈希值存储在哈希映射中，
     * 通过将 StoreHash 设置为 true 来加快插入和查找。
     */
    tsl::hopscotch_map<std::string, int, std::hash<std::string>,
                        std::equal_to<std::string>,
                        std::allocator<std::pair<const std::string, int>>,
                        30, true> map2;
    map2["a"] = 1;
    map2["b"] = 2;
    // {a, 1} {b, 2}
    for(const auto& key_value : map2) {
        std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
    }
    
    tsl::hopscotch_set<int> set;
    set.insert({1, 9, 0});
    set.insert({2, -1, 9});
    // {0} {1} {2} {9} {-1}
    for(const auto& key : set) {
        std::cout << "{" << key << "}" << std::endl;
    }
}

异构查找

异构重载允许在查找和删除操作中使用 Key 以外的其他类型，只要使用的类型可以与 Key 进行哈希和比较。要激活 tsl::hopscotch_map/set 中的异构重载，必须使限定 ID KeyEqual::is_transparent 有效。其工作方式与 std::map::find 相同 (http://en.cppreference.com/w/cpp/container/map/find)。您可以使用 std::equal_to<> (http://en.cppreference.com/w/cpp/utility/functional/equal_to_void) 或定义自己的函数对象。KeyEqual 和 Hash 都需要能够处理不同的类型。

#include <iostream>
#include <string>
#include <tsl/hopscotch_map.h>

struct employee {
    employee(int id, std::string name) : m_id(id), m_name(std::move(name)) { }
    
    // 要么我们在类中包含比较器，然后使用 `std::equal_to<>`...
    friend bool operator==(const employee& empl, int empl_id) {
        return empl.m_id == empl_id;
    }
    friend bool operator==(int empl_id, const employee& empl) {
        return empl_id == empl.m_id;
    }
    friend bool operator==(const employee& empl1, const employee& empl2) {
        return empl1.m_id == empl2.m_id;
    }
    
    int m_id;
    std::string m_name;
};

// ... 或者我们实现一个单独的类来比较雇员。
struct equal_employee {
    using is_transparent = void;
    
    bool operator()(const employee& empl, int empl_id) const {
        return empl.m_id == empl_id;
    }
    bool operator()(int empl_id, const employee& empl) const {
        return empl_id == empl.m_id;
    }
    bool operator()(const employee& empl1, const employee& empl2) const {
        return empl1.m_id == empl2.m_id;
    }
};

struct hash_employee {
    std::size_t operator()(const employee& empl) const {
        return std::hash<int>()(empl.m_id);
    }
    std::size_t operator()(int id) const {
        return std::hash<int>()(id);
    }
};

int main() {
    // 使用 std::equal_to<>，它会自动推导并转发参数
    tsl::hopscotch_map<employee, int, hash_employee, std::equal_to<>> map;
    
    map.insert({employee(1, "John Doe"), 2001});
    map.insert({employee(2, "Jane Doe"), 2002});
    map.insert({employee(3, "John Smith"), 2003});
    
    // John Smith 2003
    auto it = map.find(3);
    if(it != map.end()) {
        std::cout << it->first.m_name << " " << it->second << std::endl;
    }
    
    map.erase(1);
    
    // 使用具有 is_transparent 成员类型的自定义 KeyEqual
    tsl::hopscotch_map<employee, int, hash_employee, equal_employee> map2;
    
    map2.insert({employee(4, "Johnny Doe"), 2004});
    
    // 2004
    std::cout << map2.at(4) << std::endl;
}

拒绝服务攻击

除了 tsl::hopscotch_map 和 tsl::hopscotch_set 之外，该库还提供了两个更“安全”的选项：tsl::bhopscotch_map 和 tsl::bhopscotch_set（它们也有对应的 pg 版本）。这两个附加类在查找和删除操作中具有最坏情况 O(log n) 的渐近复杂度，在插入操作中具有摊销最坏情况 O(log n) 的复杂度（由于可能发生重哈希导致 O(n)，所以是摊销的）。即使哈希函数将所有元素映射到同一个桶，O(log n) 仍然成立。这提供了对哈希表拒绝服务攻击的安全性。

为了实现这一点，“安全”版本使用二叉搜索树来处理溢出元素（详见实现细节 (https://tessil.github.io/2016/08/29/hopscotch-hashing.html)），因此需要元素满足 LessThanComparable。还需要一个额外的 Compare 模板参数。

#include <iostream>
#include <chrono>
#include <tsl/hopscotch_map.h>
#include <tsl/bhopscotch_map.h>

/*
 * 一个总是返回 1 的糟糕哈希函数，用于模拟拒绝服务攻击。
 */
struct dos_attack_simulation_hash {
    std::size_t operator()(int id) const {
        return 1;
    }
};

int main() {
    /*
     * 由于哈希函数不佳，速度慢，插入操作为 O(n)。
     */
    tsl::hopscotch_map<int, int, dos_attack_simulation_hash> map;
    
    auto start = std::chrono::high_resolution_clock::now();
    for(int i=0; i < 10000; i++) {
        map.insert({i, 0});
    }
    auto end = std::chrono::high_resolution_clock::now();
    // 110 ms
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end-start);
    std::cout << duration.count() << " ms" << std::endl;
    
    /*
     * 更快的版本。即使使用糟糕的哈希函数，插入操作平均为 O(log n)
     * （重新哈希时可能为 O(n)）。
     */
    tsl::bhopscotch_map<int, int, dos_attack_simulation_hash> map_secure;
    
    start = std::chrono::high_resolution_clock::now();
    for(int i=0; i < 10000; i++) {
        map_secure.insert({i, 0});
    }
    end = std::chrono::high_resolution_clock::now();
    // 2 ms
    duration = std::chrono::duration_cast<std::chrono::milliseconds>(end-start);
    std::cout << duration.count() << " ms" << std::endl;
}

许可证

该代码使用 MIT 许可证，详见