摘要
传统的Hash表通过对目标数据进行Hash计算,可以实现数据的快速存取与检索。为了保持较好的存储性能,需要使整个Hash表保持疏松的状态,从而牺牲掉10%~25%的空间。这对于海量数据存储而言,是一种巨大的空间浪费。该文提出一种多维Hash表结构,通过增加Hash表在逻辑上的维度,大大降低了Hash表的冲突率,实现了在较高的填充率下获得较满意的性能。实验结果表明:在千万的数据量级上,二维Hash表的冲突率比传统Hash表的减小2~4个数量级,总体性能则提升了1个数量级。该文还在原有填充率的基础上,提出失效率的概念,进一步完善和统一了Hash表性能评价指标。
Traditional Hash table can quickly locate the target by calculating the Hash value of the target data to enable fast data access and retrieval. Good storage performance requires that the Hash table maintains a loose state by sacrificing 10%--25% of the space. This is a tremendous waste of space in massive data storage systems. This paper presents a multi-dimensional Hash table structure that by increasing the logical dimension of the Hash table to significantly reduce the collision rate in the Hash table for satisfactory performance with a high filling rate. Tests show that with ten million entries, the collision rate of a two dimensional Hash table is 2--4 orders of magnitude lower than a traditional Hash table and the overall performance is improved by 1 order of magnitude. In addition, a failure rate concept is proposed to improve Hash table performance evaluations.
作者
吴泉源
彭灿
郑毅
卜俊丽
WU Quanyuan PENG Can ZHENG Yi BU Jun(School of Computer, National University of Defense Technology, Changsha 410073, China)
出处
《清华大学学报(自然科学版)》
EI
CAS
CSCD
北大核心
2017年第6期586-590,共5页
Journal of Tsinghua University(Science and Technology)
关键词
多维
HASH表
海量数据存储
失效率
multi dimension
Hash table
massive data storage
failure rate