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

摘要：

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

关键词：哈希图、分组、连接、缓存感知、缓存不敏感、列存储数据库、BHMap

所属期刊栏目：10

分类号：TP311.132.3(计算技术、计算机技术)

资助基金：The National Natural Science Foundation of China under Grant Nos.61170082,61472025;the New Century Excellent Talents Foundation from MOE of China under Grant No.NCET-12-0757;the Scientific Research Foundation for the Returned Overseas Chinese Scholars,State Education Ministry of China under Grant No.LXJJ201303

在线出版日期：2016-11-04（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：1250-1261