基于低冲突帮助机制的快速无等待哈希表算法  

Fast Wait-free Hash Table Algorithm Based on Low-conflict Help Mechanism

作　　者：李鹏飞[1] 张坤龙[1] 康超凡 

机构地区：[1]天津大学计算机科学与技术学院,天津300072

出　　处：《计算机工程》2015年第11期52-58,共7页Computer Engineering

基　　金：国家自然科学基金资助项目(61303021);水利部公益性行业科研专项基金资助项目(201401033)

摘　　要：针对现有无等待哈希表算法未充分利用哈希表的固有并行性,造成线程之间存在高冲突和高冗余的问题,提出一种快速无等待哈希表算法。利用可冻结集合思想简化哈希表操作,采用CAS原子指令保证插入、删除与查找操作均为无等待。根据哈希表结构改进帮助机制,使得哈希桶的实现为无等待,只有在扩展哈希表时哈希桶之间才提供帮助。实验结果表明,该算法能降低线程操作间的冲突,提高帮助操作的并行度,当查找率为0、键值范围为0~256且线程数为8时,其吞吐率是现有无等待哈希表算法的2.5倍。Existing wait-free hash table algorithms do not take full advantage of the inherent parallelism of hash table, which results in the high redundancy and conflict between threads. In order to solve the problem,this paper proposes a fast wait-free hash table algorithm. It makes use of the freezable set to simplify the operations of hash table. And the Compare and Swap（CAS） primitive is applied to realize the wait-free of insertion,deletion and search operations. It improves the help mechanism based on the structure of hash table to realize the wait-free of hash buckets. In order to avoid the conflics between the operations on different buckets, the help is given only when the hash table extends. Experimental results show that the algorithm can reduce the conflict between thread operation, and improve the parallelism of help operation. When the percentage of lookup is 0, the data range is 0 - 256 and the thread number reaches 8, throughput of the proposed algorithm is 2.5 times than the existing wait-free hash table algorithm.

关 键 词：并发数据结构 哈希表 无等待 可线性化 可扩展 

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论]