并发编程高性能计算【免费下载链接】oneTBBoneAPI Threading Building Blocks (oneTBB)项目地址https://gitcode.com/gh_mirrors/on/oneTBB点击查看免费下载concurrent_hash_mapKey, T, HashCompare是 oneAPI Threading Building BlocksoneTBB提供的并发哈希表容器支持多线程同时对同一张表进行查找、插入、更新与删除并通过accessor/const_accessor显式区分写访问与只读访问来控制锁粒度。本文以 concurrent_hash_map.rst 为核心骨架结合 并发哈希表源码、HashCompare 基础设施 与仓库内置的 count_strings 示例完整讲解其使用方式、访问器语义与定制哈希/比较策略的实战方案。一、concurrent_hash_map 是什么concurrent_hash_mapKey, T, HashCompare是一张允许并发访问的哈希表逻辑上是一个从键Key到值T的映射。第三个模板参数HashCompare是特征类型traits它定义了如何对键计算哈希以及如何比较两个键是否相等两个操作是决定哈希表行为与性能的关键。从源码定义可见容器元素类型为std::pairconst Key, T见 concurrent_hash_map.h且默认基于自旋读写锁spin_rw_mutex实现并发控制见 concurrent_hash_map.h。它典型适用于元素被频繁读取、偶尔更新的共享数据结构场景——例如缓存、词频统计、配置字典、去重集合等。二、核心概念HashCompare 特征类型concurrent_hash_map的键哈希与相等判断完全由HashCompare驱动。它必须提供两个签名成员签名职责hashsize_t hash(const Key) const把键映射为一个size_t哈希码equalbool equal(const Key, const Key) const判断两个键是否相等这两个签名必须放在同一个类中因为两者之间存在硬性契约若两个键相等则它们的哈希值必须相同否则哈希表将无法正常工作。理论上你可以让所有键都哈希到0来平凡满足这一约束但那会造成灾难性的性能退化理想情况下每个键都应尽量哈希到不同的桶至少要把两个不同键碰撞的概率控制得很低。文档中的MyHashCompare是一个针对std::string的典型实现hash采用简单的多项式滚动哈希h (h*17)^*sequal直接比较字符串内容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 xy; } };关于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 users 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 xy; } }; // A concurrent hash table that maps strings to ints. typedef concurrent_hash_mapstring,int,MyHashCompare StringTable; // Function object for counting occurrences of strings. struct Tally { StringTable table; Tally( StringTable table_ ) : table(table_) {} void operator()( const blocked_rangestring* range ) const { for( string* prange.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_rangestring*( Data, DataN, 1000 ), Tally(table) ); // Display the occurrences for( StringTable::iterator itable.begin(); i!table.end(); i ) printf(%s %d\n,i-first.c_str(),i-second); }这段代码揭示了三个要点parallel_for与哈希表配合blocked_rangestring*(Data, DataN, 1000)把 100 万个字符串切成大小为 1000 的块分发给各线程Tally函数对象在每块内独立执行。insert(accessor, key)的原子语义table.insert(a, *p)要么找到已有键并为其取得访问权要么新建该键。随后a-second 1通过访问器安全地完成读-改-写复合操作这是并发哈希表相对普通std::unordered_map的最大优势——查找与更新在锁的保护下作为一个整体完成不会出现两个线程同时读到 0、各自加 1 再写回的竞态。串行遍历结果统计完成后begin()/end()迭代器提供只读快照遍历输出first键与second计数。从源码看insert(accessor, const Key)实际调用统一的lookuptrue内部路径并传入写访问标志见 concurrent_hash_map.hfind则走lookupfalse的只读路径见 concurrent_hash_map.h。两者共享同一查找核心仅区别在于访问类型与是否允许分配节点。四、accessor 与 const_accessor读写访问的控制模型concurrent_hash_map的元素是std::pairconst 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.haccessor则公有继承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* prange.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_compareKey然后二选一为tbb_hash_compareKey定义特化版本提供自由函数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_compareKey实际上包装了标准库的std::hashKey与std::equal_toKey见 _hash_compare.h。因此只要std::hashKey可实例化且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_compareKey或自定义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 xy; } VariantHashCompare(bool ignore_case_) : ignore_case(ignore_case_) {} }; typedef concurrent_hash_mapstring,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_allocatorchar自定义字符串分配器MyString让字符串内存也走 oneTBB 的可扩展分配器用tick_count计时分别运行串行版max_allowed_parallelism1与并行版自动选择线程数以对比加速效果内置随机的仿造单词数据生成器并支持--count_collisions统计哈希碰撞情况。构建与运行方式见 README.mdcmake path_to_example cmake --build .命令行参数count_strings [n-of-threadsvalue] [n-of-stringsvalue] [verbose] [silent] [count_collisions] [-h]-h打印命令行选项帮助n-of-threads使用的线程数可为low[:high]区间形式或auto平台默认值n-of-strings待统计的字符串个数默认 1,000,000verbose输出诊断信息每个唯一字符串及其计数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 项目中安全、高效地使用这张并发哈希表。赞分享并发编程高性能计算【免费下载链接】oneTBBoneAPI Threading Building Blocks (oneTBB)项目地址https://gitcode.com/gh_mirrors/on/oneTBB点击查看免费下载相关推荐并发哈希表优化oneTBB concurrent_hash_map应用指南并发哈希表优化oneTBB concurrent_hash_map应用指南 引言高性能并发数据结构的必要性 在多核处理器主导的时代传统的线程安全哈希表如并发编程高性能计算如何让大麦自动抢票脚本跑起来实战教程如何让大麦自动抢票脚本跑起来实战教程 抢票日 8 点你按下立即购买屏幕先是一顿转圈再弹出已售罄刷新页面连票价区都没了。靠手抢热门演出基本是这网页爬虫工作流自动化终极指南如何让AI智能管家帮你自动下载网页文件终极指南如何让AI智能管家帮你自动下载网页文件 还在为每天重复的文件下载任务而烦恼吗Browser Use开源项目让你的AI助手像专业人士一样自动完成所有人工智能AI Agent浏览器控制GUI 自动化MCP 服务上一篇适配器模式在 gh_mirrors/api1/api 中的应用Laravel/Lumen 路由适配实现下一篇CANN/PID FOPDT批量闭环滚动评分算子创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考