HashMap优化及其在列存储数据库查询中的应用

• 作者: 李征 母红芬 金正皓 霍卫平
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 哈希图 分组 连接 缓存感知 缓存不敏感 列存储数据库 BHMap
• 年，卷（期）: 2016,（9）
• 所属期刊栏目: 数据库技术
• 页码范围: 1250-1261
• 页数: 12页
• 分类号: TP311.132.3
• 字数: 7913字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.1507065

摘要

HashMap在基本字典操作中具有常数级别的平均算法时间复杂度,广泛应用于大数据的检索.Block_HashMap (BHMap)基于C++ HashMap,其优化包括三方面:哈希函数选取,冲突解决和关键字匹配.优化核心在于冲突解决时,以链地址法为基础,提出了一种高效利用高速缓存的存储结构Block_List来存储冲突的数据,并且预先缓存哈希值,节省匹配时间.实验证明,在桶数目充足的情况下,BHMap会多消耗少部分内存,但在桶数目有限,数据重复率比较低的情况下,时间性能上相对C++标准模板库中的Map提升10倍以上,比unordered_map快3.5倍以上,且消耗的内存与unordered map相差不大.在列存储数据库分组和连接查询中,关键字的分桶、解决冲突和匹配操作也都涉及到基于哈希的技术,最终把BHMap应用到列存储数据库的关键查询中.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李征	北京化工大学计算机系	23	151	8.0	11.0
2	母红芬	北京化工大学计算机系	1	14	1.0	1.0
3	霍卫平		1	14	1.0	1.0
4	金正皓		1	14	1.0	1.0