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

• 作者: 康超凡 张坤龙 李鹏飞
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 并发数据结构 哈希表 无等待 可线性化 可扩展
• 年，卷（期）: 2015,（11）
• 所属期刊栏目: 先进计算与数据处理
• 页码范围: 52-58
• 页数: 7页
• 分类号: TP311.1
• 字数: 6065字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2015.11.010

摘要

针对现有无等待哈希表算法未充分利用哈希表的固有并行性,造成线程之间存在高冲突和高冗余的问题,提出一种快速无等待哈希表算法.利用可冻结集合思想简化哈希表操作,采用CAS原子指令保证插入、删除与查找操作均为无等待.根据哈希表结构改进帮助机制,使得哈希桶的实现为无等待,只有在扩展哈希表时哈希桶之间才提供帮助.实验结果表明,该算法能降低线程操作间的冲突,提高帮助操作的并行度,当查找率为0、键值范围为0～ 256且线程数为8时,其吞吐率是现有无等待哈希表算法的2.5倍.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李鹏飞	天津大学计算机科学与技术学院	12	49	4.0	7.0
2	张坤龙	天津大学计算机科学与技术学院	8	24	3.0	4.0
3	康超凡	天津大学计算机科学与技术学院	3	7	2.0	2.0