企业官网建设流程全解析

mold 项目中的 TBB HashCompare 深度指南：为 concurrent_hash_map 定制哈希与相等性比较

【免费下载链接】moldmold: A Modern Linker 🦠项目地址: https://gitcode.com/GitHub_Trending/mo/mold

导读

concurrent_hash_map是 oneTBB（Intel oneAPI Threading Building Blocks）提供的并发哈希表容器，它允许线程安全地并发读写std::pair<const Key, T>形式的键值对。而HashCompare正是决定这张哈希表如何对键进行哈希、如何判定键是否相等的关键类型参数。本文将基于 oneTBB 用户指南中的 "More on HashCompare" 章节，完整讲解如何为自定义键类型编写HashCompare，包括显式指定、特化默认模板tbb_hash_compare<Key>、利用tbb_hasher自由函数、实例相关（带状态）的哈希比较器，以及这些机制在 mold 链接器源码中的真实应用，帮助你写出正确、高效、可并发的自定义哈希表。

一、什么是 HashCompare：并发哈希表正确性的基石

concurrent_hash_map<Key, T, HashCompare>是一个允许并发访问的哈希表，从 Key 映射到类型 T。HashCompare这个 traits 类型负责回答两个问题：

1. 如何为 Key 计算哈希码—— 即hash方法；
2. 如何判定两个 Key 相等—— 即equal方法。

这两个签名必须打包在同一个类中，这并非随意设计，而是由哈希表的数学不变量决定的：如果两个键相等，那么它们的哈希值必须相同。否则，两个逻辑上相同的键会被分配到不同的桶（bucket）中，哈希表将无法正确工作——find可能找不到一个实际存在的键，insert也可能产生重复条目。

从 oneTBB 的规范文档 hash_compare.rst 中可以找到这条硬性约束的原文：如果H::equal(k1, k2)返回true，则必须保证H::hash(k1) == H::hash(k2)。同时该文档还要求hash的返回类型为std::size_t，equal的返回类型应可隐式转换为bool，并且H需要满足可拷贝构造、可析构等基本约束。

满足这一不变量最简单（但最糟糕）的方式是让所有键都哈希到0——这完全合法，但会带来巨大的效率损失：所有条目都被塞进同一个桶，哈希表退化成链表。理想情况下，每个不同的键应尽可能哈希到不同的值，至少要让不同键碰撞到同一哈希值的概率保持在较低水平，这也是哈希函数设计的核心追求。

从源码看 HashCompare 的接口定义

oneTBB 在头文件 _hash_compare.h 中给出了默认实现tbb_hash_compare的接口骨架：

template <typename Key> class tbb_hash_compare { public: std::size_t hash( const Key& a ) const { return my_hash_func(a); } bool equal( const Key& a, const Key& b ) const { return my_key_equal(a, b); } private: std::hash<Key> my_hash_func; std::equal_to<Key> my_key_equal; };

可以看到，默认的tbb_hash_compare<Key>内部直接封装了标准库的std::hash<Key>和std::equal_to<Key>。这意味着：

• 如果Key是std::hash已经支持的内置类型或标准库类型（如int、std::string），那么什么都不用做，concurrent_hash_map开箱即用；
• 如果Key是自定义类型，你就需要自行定义std::hash<Key>的特化，或者走本文接下来介绍的几条路径。

此外，hash_compare.rst 明确将tbb_hash_compare<Key>声明为满足 HashCompare 命名需求的类模板，其hash方法返回键k的哈希码，equal方法等价于k1 == k2。

二、为自定义类型接入 HashCompare 的两条路径

oneTBB 为你的自定义键类型提供了两种主流接入方式：

1. 显式指定HashCompare参数：在声明concurrent_hash_map时，把自定义的哈希比较器类型作为第三个模板参数传进去；
2. 让HashCompare默认取tbb_hash_compare<Key>，然后做下面两件事之一：
   • 特化模板tbb_hash_compare<Key>；
   • 为Key提供tbb_hasher自由函数（仅适用于传统tbb::命名空间接口，下文详解）。

路径 A：为 Key 提供 tbb_hasher 自由函数

如果你的键类型是Foo，且已经为Foo定义了operator==，那么你只需要提供一个tbb_hasher自由函数即可，例如：

size_t tbb_hasher(const Foo& f) { size_t h = ...compute hash code for f...; return h; };

文档指出这是接入 HashCompare 的便捷方式：只要operator==已定义、tbb_hasher(const Foo&)已提供，tbb_hash_compare<Foo>的equal会退化为调用operator==，hash则调用你的tbb_hasher。需要说明的是，该机制属于传统tbb::命名空间接口的约定；在使用oneapi::tbb::命名空间的新接口时，更通用、可移植的做法是显式提供hash/equal方法或特化tbb_hash_compare，后文会给出完整示例。

路径 B：显式提供 hash + equal 方法

无论采用哪条路径，最终HashCompare都必须提供两个签名：

std::size_t hash(const Key& k) const; // 将 Key 映射为 size_t bool equal(const Key& k1, const Key& k2) const; // 判定两个键是否相等

一个最小可用的自定义比较器如下（来自用户指南中concurrent_hash_map一节的MyHashCompare示例，concurrent_hash_map.rst）：

struct MyHashCompare { size_t hash( const string& x ) const { size_t h = 0; for( const char* s = x.c_str(); *s; ++s ) h = (h*17)^*s; // 简单的字符串多项式哈希 return h; } bool equal( const string& x, const string& y ) const { return x==y; } }; typedef concurrent_hash_map<string,int,MyHashCompare> StringTable;

三、实例相关（带状态）的 HashCompare：大小写不敏感的字符串表

HashCompare的方法默认应为static，因为你通常不需要它们在不同实例间行为不同。但如果你确实需要实例相关（instance-dependent）的行为——例如同一个比较器类型既支持大小写敏感、又支持大小写不敏感的模式——那么就必须使用接受HashCompare参数作为构造参数的构造函数来构建concurrent_hash_map。

下面是一个完整的实例相关示例（取自 "More on HashCompare" 章节原文）：

// Structure that defines hashing and comparison operations class VariantHashCompare { // If true, then case of letters is ignored. bool ignore_case; public: size_t hash(const string& x) const { size_t h = 0; for(const char* s = x.c_str(); *s; s++) h = (h*16777179)^*(ignore_case?tolower(*s):*s); return h; } // True if strings are equal bool equal(const string& x, const string& y) const { if( ignore_case ) strcasecmp(x.c_str(), y.c_str())==0; else return x==y; } VariantHashCompare(bool ignore_case_) : ignore_case(ignore_case_) {} }; typedef concurrent_hash_map<string,int, VariantHashCompare> VariantStringTable; VariantStringTable CaseSensitiveTable(VariantHashCompare(false)); VariantStringTable CaseInsensitiveTable(VariantHashCompare(true));

这段代码的精妙之处在于：哈希函数与相等性比较必须保持"同频"。

• 在hash中，如果ignore_case为真，每个字符都会先经过tolower归一化后再参与多项式哈希h = (h*16777179)^c；
• 在equal中，同样在ignore_case为真时使用strcasecmp（大小写不敏感比较）。

由于哈希和比较走了同一套大小写归一化逻辑，所以对于任意两个仅大小写不同的键（如"Foo"与"foo"），它们的哈希值相等，equal也判定它们相等，从而满足"相等键必须同哈希"的不变量。反过来，如果hash归一化而equal不归一化，或者反之，就会破坏该不变量，导致哈希表行为错误。

从源码结构看，VariantHashCompare之所以能用同一个类型构造出行为不同的两张表，正是因为concurrent_hash_map支持将HashCompare实例作为构造参数传入，构造时拷贝该实例，之后每次哈希、比较都调用该实例的非静态成员函数——这也是"方法应尽量为 static，除非需要实例相关行为"这一建议的由来。

使用注意：实例相关比较器必须是可拷贝的

从 hash_compare.rst 的命名需求可知，HashCompare类型必须支持拷贝构造。上述示例中VariantHashCompare只有bool ignore_case一个标量成员，天然满足可拷贝要求；如果你的比较器持有资源（如动态分配的内存、锁等），需要确保其拷贝语义正确，或在设计中避免持有这类资源。

四、实战对照：mold 链接器中的真实应用

本仓库（mold，一个高性能现代链接器）正是 oneTBB 并发容器的重度用户。在 mold.h 中可以看到#include <tbb/concurrent_hash_map.h>，在 mapfile.cc 中同样包含了该头文件。

在 mold.h 中，mold 定义了一个用于收集未定义符号错误信息的并发哈希表：

tbb::concurrent_hash_map<Symbol<E> *, std::vector<std::string>> undef_errors;

在 mapfile.cc 中，mold 使用它记录输入段到符号的映射关系：

tbb::concurrent_hash_map<InputSection<E> *, std::vector<Symbol<E> *>>;

这两处都没有显式指定第三个模板参数HashCompare，而是让concurrent_hash_map默认使用tbb_hash_compare<Key>：

• 键类型是Symbol<E>*或InputSection<E>*这样的指针，std::hash对任意指针类型都有现成的特化（按指针值散列），std::equal_to对指针执行地址相等比较；
• 因此默认的tbb_hash_compare完全够用，mold 无需为这些键编写任何自定义哈希逻辑。

这是一个非常有代表性的工程实践：能用默认std::hash覆盖的键类型，就不要手写HashCompare。只有当键是自定义结构体、或者需要特殊的相等语义（如大小写不敏感、内容相等而非地址相等）时，才需要显式定制。

五、与并发语义配合：accessor 与锁粒度

理解HashCompare还需要顺带理解concurrent_hash_map的并发访问模型，因为自定义比较器是在这个模型中被调用的。根据用户指南 concurrent_hash_map.rst：

• concurrent_hash_map存储的元素类型是std::pair<const Key, T>；
• accessor表示写（更新）访问，只要它指向某个元素，其他线程对该键的查找就会被阻塞，直到该accessor释放；
• const_accessor表示只读访问，多个const_accessor可以同时指向同一元素，这对"读多写少"的场景能显著提升并发度；
• find/insert方法通过接收accessor还是const_accessor来决定请求的是更新还是只读访问；
• 访问会阻塞其他线程，因此应尽量缩短 accessor 的生命周期——在尽可能内层的块中声明它，或在块结束前调用release()主动释放；
• erase(key)隐式请求写访问，会等待该键上所有现存访问结束。

例如统计字符串出现次数的经典写法（来自count_strings示例，count_strings.cpp）：

StringTable::accessor a; table.insert(a, *p); a->second += 1;

insert返回时a已指向新插入或已存在的元素，通过a->second即可安全地原子化累加计数。需要强调的是，hash与equal方法在并发环境下可能被多个线程同时调用，因此比较器内部不应修改共享的可变状态（除非有同步机制保护），这也是官方建议方法默认声明为static的深层原因。

六、写一个正确且高效的 HashCompare 的要点清单

综合上述分析，为concurrent_hash_map编写自定义HashCompare时应遵循以下要点：

按此清单实现，你就能为任意自定义键类型接入concurrent_hash_map，既保证并发哈希表的正确性，又不牺牲查找性能。

延伸阅读

• oneTBB 并发哈希表入门：concurrent_hash_map.rst
• 本文主题原始出处：More_on_HashCompare.rst
• HashCompare 命名需求规范：hash_compare.rst
• 默认比较器tbb_hash_compare类模板文档：tbb_hash_compare_cls.rst
• 默认实现源码：_hash_compare.h
• 完整可运行的统计示例：count_strings.cpp
• mold 链接器中的实际使用：mold.h、mapfile.cc

【免费下载链接】moldmold: A Modern Linker 🦠项目地址: https://gitcode.com/GitHub_Trending/mo/mold