企业官网建设流程全解析

• 并发编程
• 高性能计算

concurrent_hash_map<Key, T, HashCompare>是 oneAPI Threading Building Blocks（oneTBB）提供的并发哈希表容器，支持多线程同时对同一张表进行查找、插入、更新与删除，并通过accessor/const_accessor显式区分"写访问"与"只读访问"来控制锁粒度。本文以 concurrent_hash_map.rst 为核心骨架，结合 并发哈希表源码、HashCompare 基础设施 与仓库内置的 count_strings 示例，完整讲解其使用方式、访问器语义与定制哈希/比较策略的实战方案。

一、concurrent_hash_map 是什么

concurrent_hash_map<Key, T, HashCompare>是一张允许并发访问的哈希表，逻辑上是一个从键Key到值T的映射。第三个模板参数HashCompare是特征类型（traits），它定义了"如何对键计算哈希"以及"如何比较两个键是否相等"两个操作，是决定哈希表行为与性能的关键。

从源码定义可见，容器元素类型为std::pair<const Key, T>（见 concurrent_hash_map.h），且默认基于自旋读写锁spin_rw_mutex实现并发控制（见 concurrent_hash_map.h）。它典型适用于"元素被频繁读取、偶尔更新"的共享数据结构场景——例如缓存、词频统计、配置字典、去重集合等。

二、核心概念：HashCompare 特征类型

concurrent_hash_map的键哈希与相等判断完全由HashCompare驱动。它必须提供两个签名：

这两个签名必须放在同一个类中，因为两者之间存在硬性契约：若两个键相等，则它们的哈希值必须相同，否则哈希表将无法正常工作。理论上你可以让所有键都哈希到0来"平凡满足"这一约束，但那会造成灾难性的性能退化；理想情况下，每个键都应尽量哈希到不同的桶，至少要把两个不同键碰撞的概率控制得很低。

文档中的MyHashCompare是一个针对std::string的典型实现：hash采用简单的多项式滚动哈希h = (h*17)^*s，equal直接比较字符串内容：

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; } // True if strings are equal bool equal( const string& x, const string& y ) const { return x==y; } };

关于HashCompare方法的static属性：文档建议，除非你需要让不同实例表现出不同行为，否则这些方法应声明为static。如果确实需要实例相关行为，则应使用接受HashCompare参数的构造函数创建表（详见下文第五节）。

三、完整示例：并行统计字符串出现次数

文档给出的核心示例是：构建一张键为字符串、值为出现次数的concurrent_hash_map，用parallel_for并行统计数组Data中每个字符串出现的次数。完整代码如下（可直接编译运行，配套的可执行示例见 count_strings.cpp）：

#include "oneapi/tbb/concurrent_hash_map.h" #include "oneapi/tbb/blocked_range.h" #include "oneapi/tbb/parallel_for.h" #include <string> using namespace oneapi::tbb; using namespace std; // Structure that defines hashing and comparison operations for user's type. 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; } //! True if strings are equal bool equal( const string& x, const string& y ) const { return x==y; } }; // A concurrent hash table that maps strings to ints. typedef concurrent_hash_map<string,int,MyHashCompare> StringTable; // Function object for counting occurrences of strings. struct Tally { StringTable& table; Tally( StringTable& table_ ) : table(table_) {} void operator()( const blocked_range<string*> range ) const { for( string* p=range.begin(); p!=range.end(); ++p ) { StringTable::accessor a; table.insert( a, *p ); a->second += 1; } } }; const size_t N = 1000000; string Data[N]; void CountOccurrences() { // Construct empty table. StringTable table; // Put occurrences into the table parallel_for( blocked_range<string*>( Data, Data+N, 1000 ), Tally(table) ); // Display the occurrences for( StringTable::iterator i=table.begin(); i!=table.end(); ++i ) printf("%s %d\n",i->first.c_str(),i->second); }

这段代码揭示了三个要点：

1. parallel_for与哈希表配合：blocked_range<string*>(Data, Data+N, 1000)把 100 万个字符串切成大小为 1000 的块分发给各线程，Tally函数对象在每块内独立执行。
2. insert(accessor, key)的原子语义：table.insert(a, *p)要么找到已有键并为其取得访问权，要么新建该键。随后a->second += 1通过访问器安全地完成"读-改-写"复合操作，这是并发哈希表相对普通std::unordered_map的最大优势——查找与更新在锁的保护下作为一个整体完成，不会出现"两个线程同时读到 0、各自加 1 再写回"的竞态。
3. 串行遍历结果：统计完成后begin()/end()迭代器提供只读快照遍历，输出first（键）与second（计数）。

从源码看，insert(accessor&, const Key&)实际调用统一的lookup<true>内部路径并传入写访问标志（见 concurrent_hash_map.h）；find则走lookup<false>的只读路径（见 concurrent_hash_map.h）。两者共享同一查找核心，仅区别在于访问类型与是否允许分配节点。

四、accessor 与 const_accessor：读写访问的控制模型

concurrent_hash_map的元素是std::pair<const Key, T>。当访问容器元素时，你通常只关心两种操作：更新（写）或读取（读）。模板类分别用accessor与const_accessor两个"智能指针"类支持这两种用途：

• accessor（写访问）：只要它仍指向某个元素，其他线程对该键的查找（无论读还是写）都会被阻塞，直到该accessor释放。它提供可写的operator*/operator->，返回value_type&。
• const_accessor（只读访问）：与accessor类似，但代表只读权限，提供const引用/指针。多个const_accessor可以同时指向同一个元素，互不阻塞。

这一模型能显著提升"读多写少"场景的并发度：所有读者可并行共享同一元素，只有写者之间以及写者与读者之间才需要互斥。从实现上看，const_accessor私有继承自节点的scoped_type（即spin_rw_mutex::scoped_lock），把"数据访问、加锁、垃圾回收"三者合并在一个对象里（见 concurrent_hash_map.h）；accessor则公有继承const_accessor，仅将operator*/operator->提升为非 const 版本（见 concurrent_hash_map.h）。因此默认构造的concurrent_hash_map在每个桶（bucket）上以自旋读写锁spin_rw_mutex作为并发原语。

find与insert方法都接受accessor或const_accessor作为第一个参数，传入哪种访问器就决定了请求的是更新还是只读访问：

• find(const_accessor&, key)/find(accessor&, key)：查找键。返回true表示找到并已持有对应权限的锁，false表示键不存在（此时访问器为空，可调用empty()判断）。
• insert(const_accessor&, key)/insert(accessor&, key)：若键不存在则插入；返回true表示新插入。
• count(key)：返回 0 或 1，不持有任何锁（见 concurrent_hash_map.h）。

关键实践准则：缩短访问器生命周期。因为持有访问权会阻塞其他线程对同一键的访问，所以应尽量让accessor/const_accessor的生命周期最短——在最内层代码块中声明它，用完即弃。

五、提前释放访问：release() 方法

除依赖作用域结束时的析构来释放锁之外，还可以调用release()方法提前释放访问权。下面是对词频统计循环体的改写，将访问器a提到循环外复用，并在每次迭代末尾显式release()，避免为每次迭代重复构造/析构访问器：

StringTable::accessor a; for( string* p=range.begin(); p!=range.end(); ++p ) { table.insert( a, *p ); a->second += 1; a.release(); }

release()的实现会将节点置空并释放底层 scoped lock（见 concurrent_hash_map.h）；析构函数同样会经由 scoped lock 的析构完成释放（见 concurrent_hash_map.h）。值得说明的是：insert在取得访问权前会先对传入的访问器执行result.release()（见 concurrent_hash_map.h），因此复用同一访问器对象是安全且推荐的写法。

release()与析构两种方式的取舍：循环体内每次insert前都会release上一轮的访问，因此"循环外声明 + 循环内 release"既减少了构造开销，又保证了访问粒度最小。这是文档明确推荐的性能实践。

六、erase 的并发语义

erase(key)同样可以并发执行，但它隐式请求写访问：在真正删除键之前，会等待该键上所有其他尚存的访问（无论读还是写）全部结束，以确保删除操作的原子性与安全性。

从源码看，erase(const Key&)经由internal_erase(key)完成（见 concurrent_hash_map.h），返回true表示该次调用确实删除了元素。此外还提供基于访问器的重载erase(const_accessor&)/erase(accessor&)（见 concurrent_hash_map.h），可直接删除当前访问器指向的元素。这一点与find/insert的"返回即持锁"模型保持一致：删除动作本身也是受锁保护的临界区。

七、More on HashCompare：为自定义类型定制哈希与比较

文档的下游章节 More_on_HashCompare.rst 系统阐述了让HashCompare适配自有类型的几种途径：

7.1 两条定制路线

• 显式指定HashCompare参数：即像第二节的MyHashCompare那样，自己编写一个同时提供hash与equal的类，作为第三个模板参数传入。
• 让HashCompare默认取tbb_hash_compare<Key>，然后二选一：
  • 为tbb_hash_compare<Key>定义特化版本；
  • 提供自由函数tbb_hasher。

例如，若键类型为Foo且已定义operator==，只需提供tbb_hasher即可：

size_t tbb_hasher(const Foo& f) { size_t h = ...compute hash code for f... // 为 f 计算哈希码 return h; }

从源码看，默认的tbb_hash_compare<Key>实际上包装了标准库的std::hash<Key>与std::equal_to<Key>（见 _hash_compare.h）。因此，只要std::hash<Key>可实例化且Key支持operator==，默认参数即可直接使用；tbb_hasher特化机制正是用于补足标准库未覆盖的自定义键类型。顺带一提，oneTBB 在启用TBB_DEFINE_STD_HASH_SPECIALIZATIONS时还会为std::pair及std::basic_string提供std::hash特化（见 _hash_compare.h）。

7.2 hash 与 equal 的契约约束

无论以何种方式定义，tbb_hash_compare<Key>或自定义HashCompare都必须提供hash与equal两个签名，二者共存于同一类的原因仍是那条不变式：相等的键必须哈希到相同的值。同时注意equal必须是"真相等"判断，而非"等价"判断——哈希表依赖它与hash的一致性来完成桶内查找。

7.3 实例相关的 HashCompare：大小写不敏感示例

若希望哈希与比较行为随实例变化，应让方法保持非static，并用接受HashCompare参数的构造函数创建表。文档给出的VariantHashCompare用一个内部标志ignore_case决定执行大小写敏感还是不敏感的哈希与比较：

// 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 ) return 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再参与运算，保证大小写不同的字符串得到相同哈希；equal分支使用strcasecmp做忽略大小写的比较，需要#include <cstring>与<cctype>。从源码看，接受HashCompare参数的构造函数会将其存入my_hash_compare成员（见 concurrent_hash_map.h），默认构造函数则以hash_compare_type()值初始化（见 concurrent_hash_map.h）。

八、源码级实现原理：分段表与桶级锁

从源码结构看，concurrent_hash_map的底层（hash_map_base，见 concurrent_hash_map.h）采用了分段增长的哈希表设计：

• 前embedded_block = 1段（即 2 个桶）内嵌在对象自身，随对象一起构造，无额外分配；
• 后续按需以 2 的幂扩大段：first_block = 8段以内一次性分配，更远的分段单独分配（见 concurrent_hash_map.h）；
• 每个bucket内部有一个自旋读写锁mutex与一个原子的node_list头指针（见 concurrent_hash_map.h）。

这意味着并发粒度是"桶"级别：不同桶上的访问完全互不干扰，同一桶内的读读可并发、读写与写写互斥。这也是为什么"读多写少"场景下concurrent_hash_map能比整表加锁的容器获得好得多的扩展性。此外，桶节点还有用于标记重哈希（rehash）状态的哨兵指针（rehash_req_flag、empty_rehashed_flag，见 concurrent_hash_map.h），说明重哈希过程同样是并发安全的增量操作，而非一次性全表拷贝。

注意：以上均为对当前仓库源码结构的观察结论。concurrent_hash_map的行为与语义以 头文件 中的公开接口及 conformance 测试 为准。

九、仓库配套示例：count_strings 的构建与运行

仓库在 examples/concurrent_hash_map/count_strings 提供了可运行的完整示例（源码见 count_strings.cpp），其核心逻辑与文档示例一致，但做了工程化增强：

• 使用oneapi::tbb::tbb_allocator<char>自定义字符串分配器（MyString），让字符串内存也走 oneTBB 的可扩展分配器；
• 用tick_count计时，分别运行串行版（max_allowed_parallelism=1）与并行版（自动选择线程数）以对比加速效果；
• 内置随机的"仿造单词"数据生成器，并支持--count_collisions统计哈希碰撞情况。

构建与运行方式（见 README.md）：

cmake <path_to_example> cmake --build .

命令行参数：

count_strings [n-of-threads=value] [n-of-strings=value] [verbose] [silent] [count_collisions] [-h]

• -h：打印命令行选项帮助；
• n-of-threads：使用的线程数，可为low[:high]区间形式或auto（平台默认值）；
• n-of-strings：待统计的字符串个数（默认 1,000,000）；
• verbose：输出诊断信息（每个唯一字符串及其计数）；
• silent：仅输出耗时，不打印其他内容。

这也是理解本文第三、四节内容的最佳"现场验证"素材：你可以用verbose观察a->second += 1的累计结果，用不同线程数对比并发统计的正确性（总计数应恒等于n-of-strings）与吞吐差异。

十、进一步阅读

• 容器总览：Containers.rst 与 Summary_of_Containers.rst
• 并发哈希表 API 参考：concurrent_hash_map 参考文档（位于 reference/source 目录）
• 头文件：concurrent_hash_map.h、_hash_compare.h
• 测试：conformance_concurrent_hash_map.cpp、test_concurrent_hash_map.cpp

核心要点回顾：concurrent_hash_map通过HashCompare解耦"哈希 + 相等"策略；通过accessor/const_accessor把"查找-持有锁-更新/读取-释放"固化为一个原子流程；以桶级自旋读写锁换取读多写少场景的高并发。掌握访问器的生命周期管理（作用域最短化 +release()）与自定义哈希策略的两种定制路线，即可在自己的多线程 C++ 项目中安全、高效地使用这张并发哈希表。

• 并发编程
• 高性能计算