, 彭灿 , 郑毅 , 卜俊丽 国防科技大学 计算机学院, 长沙 410073
收稿日期：2016-06-28
作者简介：吴泉源(1942-), 男, 教授。E-mail:wuquanyuan@126.com
摘要：传统的Hash表通过对目标数据进行Hash计算，可以实现数据的快速存取与检索。为了保持较好的存储性能，需要使整个Hash表保持疏松的状态，从而牺牲掉10%~25%的空间。这对于海量数据存储而言，是一种巨大的空间浪费。该文提出一种多维Hash表结构，通过增加Hash表在逻辑上的维度，大大降低了Hash表的冲突率，实现了在较高的填充率下获得较满意的性能。实验结果表明：在千万的数据量级上，二维Hash表的冲突率比传统Hash表的减小2~4个数量级，总体性能则提升了1个数量级。该文还在原有填充率的基础上，提出失效率的概念，进一步完善和统一了Hash表性能评价指标。
关键词：多维Hash表海量数据存储失效率
Multi-dimensional Hash table structure for massive data applications
WU Quanyuan
, PENG Can, ZHENG Yi, BU JunliSchool of Computer, National University of Defense Technology, Changsha 410073, China
Abstract: 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.
Key words: multi-dimensionHash tablemassive data storagefailure rate
随着互联网的发展，自2012年以来，全球的数据量以每年58%的速度增长。国际数据公司(IDC)的《数字宇宙报告》显示，预计到2020年全球数据总量将超过44 ZB(相当于4.4万亿GB)[1]。飞速增长的数据对快速存取与检索技术提出了巨大的挑战。为了应对这一挑战，出现了以Amazon的Dynamo[2]、Google的Bigtable[3]和Facebook的Cassandra[4]为代表的非关系型数据库产品。它们的共同特点是采用分布式结构和支持广泛的数据类型(文本、图像、音频、视频等)，适用于数据格式松散不一、数据总量庞大的大中型应用，比如社交网络、购物网站等的后台数据存取与检索。而对于一些数据格式相对统一、操作相对简单、数据量较大但占用的存储空间不大的小型应用，比如数字地图数据、卫星定位和导航数据等的存取与查询等，虽然也可以用上述方案解决，但一方面需要事先搭建专门的数据库环境, 对于小型应用来说成本太高；另一方面与单机环境比较而言，分布式的存取效率也不高。
Hash表作为一种通用的数据结构，非常适用于上述的小型应用问题的数据存取与检索。传统的Hash表是一维线性结构，采用一个Hash函数将目标内容(文本、图像等)转化为一个序列，然后将该序列与一维线性表中的位置对应起来。优点是结构简单，定位和检索通常只需要通过一次Hash计算；缺点是其存取性能与失效率(由Hash函数的冲突率和表的填充率决定)密切相关。一般来说，在Hash函数确定的情况下，表的填充率越低，失效率就越低，其存取性能就越好。这就使得Hash表在实际应用中，往往需要在性能和存储空间上作出权衡，大大限制了其在海量数据方面的应用。
为了克服一维Hash表的不足，本文提出一种多维Hash表结构，够在较高的填充率下获得与一维Hash表相当甚至更好的性能，达到了性能和存储空间的完美统一。
1 指标描述多维Hash表将目标内容转化为一个多维的序列组，根据该序列组来确定其存储位置。以二维Hash表为例，二维Hash表采用2个不同的Hash函数，用得到的2个Hash值作为确定其存储位置的行和列的依据。图 1为一维Hash表和二维Hash表的示意图。
 |
| 图 1 一维Hash表与二维Hash表示意图 |
| 图选项 |
1.1 填充率填充率也称装载因子，是Hash表最基本和最重要的一个指标。若总长度为m的Hash表中填入了n(n≤m)条记录，则填充率为n/m。填充率越低Hash表越松散，反之则Hash表越紧凑。
1.2 Hash函数冲突率设h(x)为Hash函数，如果有2个或多个关键字使用同一个散列函数计算得到的Hash值相同，即key1≠key2但h(key1)=h(key2)，即为发生冲突[5]。冲突的存在是Hash表性能瓶颈的根本原因，而且随着冲突的增加，Hash表的性能也急剧下降。为了衡量冲突的程度，这里引入冲突率的概念。若Hash函数h(x)对于m个互异的关键字计算之后，得到了n(n≤m)个互异的Hash值，则定义该Hash函数的冲突率为(m-n)/m，并以此作为衡量Hash函数冲突的指标。
1.3 Hash表失效率在将某个内容存入Hash表时，如果与该内容的Hash值相对应的存储单元已经被占用，则为发生了一次失效。导致失效的原因有2方面：一方面是由于Hash函数的冲突，将不同的内容计算得到了同一个Hash值；另一方面则是由于Hash表的实际容量有限，而将原本不同的Hash值映射到了同一个存储单元(如将Hash值对表长取余而造成的)。Hash表失效将导致其重新探索新的存储位置，从而降低整体的存取效率。根据导致失效的2方面，可知Hash表失效率与Hash函数的冲突率以及Hash表的填充率有关。具体来说，如果当前Hash表的填充率为α，其Hash函数的冲突率为β，则Hash表的失效率δ可表示为
| $\delta = a + (1-\alpha )\beta = (1-\beta )\alpha + \beta .$ |
1.4 存取效率目前对Hash表的性能一般通过平均查找长度来衡量，在此方面已有较为成熟的结论，如表 1所示。
表 1 Hash表的平均查找长度
| 处理方法 | 查找成功 | 查找失败 |
| 链地址法 | α+e-α | |
| 线性探测法 | ||
| 二次探测法 |
表选项
根据节1.3的分析，表 1中的α实际上就是忽略了Hash函数冲突率之后的失效率δ。然而对于多维Hash表，一般用于输入量级较大的情况，而此时Hash函数的冲突率会急剧上升，以至于达到和填充率相同的量级，在这种情况下，Hash函数的冲突率对性能的影响不再能够被忽略。由于表 1中对平均表长的分析仅考虑了填充率，因此其结论仅适用于一维Hash表。如果将表 1中的填充率α用失效率δ代替，则替换后的公式既适用于一维Hash表，也适用于多维Hash表。
由于进行替换以后，一维Hash表和多维Hash表的平均查找长度的公式在形式上得到了统一，没有直观的差别。因此在本文中采用一个可以直接观测到的量——Hash表的平均存取时间，来衡量Hash表的性能。Hash表的平均存取时间分为平均存入时间和平均取出时间。平均存入时间是指给定一个关键字，将该关键字存入Hash表所花费的平均时间；而平均取出时间是指给定一个关键字，从Hash表中找出该关键字或者确定该关键字不在表中所需的平均时间。由于存入和取出是2个相似的逆过程，因此在本文中仅使用平均存入时间作为衡量Hash表性能优劣的指标。
2 指标分析2.1 Hash函数冲突率分析假设一维Hash表的Hash函数为h1(x)，设其冲突率为β1。为了便于比较，将二维Hash表的第一维的Hash函数也选为h1(x)。另选取h2(x)作为其第二个维度的Hash函数，设其冲突率为β2。由此可以得出，二维Hash表总的Hash函数冲突率βⅡ理论上为βⅡ=β1β2θ。其中θ为一个介于[1, β2-1]之间的系数，由2个Hash函数之间的相似度来决定，在这里不做具体的分析。由于一般的Hash函数随着输入的数量级不同，其冲突率的量级介于万分之一到百分之一之间，因此二维Hash表的Hash函数冲突率理论上要比一维Hash表小2~4个量级。
2.2 Hash表失效率分析Hash表的失效率是Hash表填充率和Hash函数冲突率的函数，由于在Hash表的填充过程中，填充率从0逐渐变大，失效率会随之不断变化。因此，本文比较多维和一维Hash表在相同填充率下的失效率。具体分析如下：
设当前一维Hash表和二维Hash表的填充率均为α，一维Hash表和二维Hash表的Hash函数冲突率分别为βⅠ和βⅡ，则它们的失效率分别为
| $\begin{array}{l}{\delta _1} = \alpha + \left( {1-\alpha } \right){\beta _Ⅰ}, \\{\delta _1} = \alpha + \left( {1-\alpha } \right){\beta _{Ⅱ}}.\end{array}$ |
| ${\delta _1}-{\delta _2} = \left( {1-\alpha } \right)({\beta _Ⅰ}-{\beta _{Ⅱ}}).$ |
2.3 Hash效率分析这里以Hash表的平均存入时间ta作为性能指标，ta可分为2部分，一部分是计算Hash值的时间th，另一部分是实际访存的时间ts。因此ta可表示为
| ${t_{\rm{a}}} = {t_{\rm{h}}} + {t_{\rm{s}}}.$ |
| ${t_{{\rm{a}}1}} = {t_{\rm{h}}} + {t_{\rm{s}}} + {\delta _1}{t_{\rm{s}}} = {t_{\rm{h}}} + (1 + {\delta _1}){t_{\rm{s}}}.$ |
| ${t_{a2}} = 2{t_{\rm{h}}} + {t_{\rm{s}}} + {\delta _2}{t_{\rm{s}}} = 2{t_{\rm{h}}} + (1 + {\delta _2}){t_{\rm{s}}}.$ |
| $\begin{array}{l}{t_{{\rm{a}}1}} = {t_{\rm{h}}} + (1 + {\delta _1}){t_{\rm{s}}} = {\rm{ }}{t_{\rm{h}}} + (1 + 2\;000{\delta _2})5{t_{\rm{h}}} = \\\;\;\;\;\;\;\;\;\;\;\;(6 + 10\;000{\delta _2}){t_{\rm{h}}}, \\{t_{{\rm{a}}2}} = 2{t_{\rm{h}}} + (1 + {\delta _2}){t_{\rm{s}}} = {\rm{ }}2{t_{\rm{h}}} + (1 + {\delta _2})5{t_{\rm{h}}} = \\\;\;\;\;\;\;\;\;\;\;\;\;\;(7 + 5{\delta _2}){t_{\rm{h}}}.\end{array}$ |
| $\frac{1}{{10\;000}} \le {\delta _2} \le \frac{1}{{100}}, $ |
| $0.99 \le \frac{{{t_{{\rm{a}}1}}}}{{{t_{{\rm{a}}2}}}} \le 15.$ |
3 二维Hash表的实现本文在Java语言环境下实现了一种具体的二维Hash表，并以此与Java内置的Hash表进行比较。
3.1 数据存储结构在本文的实现中，采用二维数组作为数据存储的基本结构，因为二维数组大小固定，存取速度快，而且比ArrayList等容器类更加简单，没有额外的性能损耗，最适合作为二维Hash表的存储结构。
3.2 Hash函数选择为了便于与Java内置的Hash表对比，在具体的实现中，第一个维度的Hash函数选择了与Java Hash表相同的内置HashCode函数。文[5-6]对包括MD5[7]、SHA1[8]和CRC32[9]在内的25种Hash函数进行了评估，最终选择了SDBM[10-11]作为第二个维度的Hash函数。SDBM[10-11]是一种标准的Hash函数，即使在很大的文本中，也能获得较低的冲突率，对于很多不同的数据集都拥有不错的总体分布[12]。
在SDBM中Hash值H的计算方法如下：
| $H = (H \ll 6) + (H \ll 6)-H + {\rm{ch}}.$ |
3.3 扩容策略在本文的实现中，也提供了与Java Hash表类似的扩容能力，支持Hash表的动态增长，以便用于数据大小未知的应用场合。这里采取的扩容策略是：当目前的Hash表的填充率达到给定值(本文将这个给定值称为扩充率，即填充率达到该值就扩容，默认为75%)时，将Hash表的单维长度扩大为之前的1.5倍，相当于总容量扩大为之前的2.25倍。
4 实验对比实验选取从100万到1亿条随机的8位定长字符串作为输入数据，分别比较在扩充率为0.25、0.5、0.75、0.9和1.0时Java Hash表和本文实现的二维Hash表的各项指标。
4.1 实验环境采用的实验环境如下：处理器为Intel Xeon E5-2403 (4核1.8 G 64bit)；内存为32 GB；硬盘为2 TB；操作系统为NeoKylin Linux Server 3.2。
4.2 Hash函数冲突率对比图 2所示为实验数据集在Java的Hash表和二维Hash表下的Hash函数冲突率对比。可以看到，二维Hash表的Hash函数冲突率比Java的Hash表要低得多。当输入数据的量级达到1亿条时，Java的Hash表所使用的Hash算法冲突率已经达到2.294%，而二维Hash表仅为0.001 2%，约为前者的1/2 000，与理论分析得出的小2~4个量级的结论一致。
 |
| 图 2 Java Hash表与二维Hash表Hash函数冲突率对比 |
| 图选项 |
4.3 性能对比这里采用ta作为性能指标来比较Java Hash表和二维Hash表的性能。表 2和3分别为Java Hash表和二维Hash表的在不同样本数和扩充率下的平均存入时间表。
表 2 Java Hash表平均存入时间
| 样本数 | ta/μs | |||||
| 扩充率= | 0.25 | 0.50 | 0.75 | 0.90 | 1.0 | |
| 100万 | 0.170 | 0.152 | 0.171 | 0.300 | 0.271 | |
| 300万 | 0.184 | 0.172 | 0.206 | 0.219 | 0.183 | |
| 500万 | 0.187 | 0.186 | 0.209 | 0.232 | 0.188 | |
| 800万 | 0.196 | 0.191 | 0.220 | 0.241 | 0.200 | |
| 1 000万 | 0.192 | 0.247 | 0.225 | 0.242 | 0.191 | |
| 3 000万 | 0.200 | 0.197 | 0.274 | 0.255 | 0.300 | |
| 5 000万 | 0.297 | 0.301 | 0.392 | 0.445 | 1.008 | |
| 8 000万 | 0.347 | 1.066 | 1.011 | 0.966 | 0.861 | |
| 10 000万 | 0.725 | 0.803 | 1.468 | 0.994 | 0.592 | |
表选项
表 3 二维Hash表平均存入时间
| 样本数 | ta/μs | |||||
| 扩充率= | 0.25 | 0.50 | 0.75 | 0.90 | 1.0 | |
| 100万 | 0.227 | 0.158 | 0.165 | 0.178 | 0.208 | |
| 300万 | 0.295 | 0.215 | 0.253 | 0.270 | 0.109 | |
| 500万 | 0.373 | 0.221 | 0.263 | 0.274 | 0.112 | |
| 800万 | 0.300 | 0.233 | 0.266 | 0.327 | 0.115 | |
| 1 000万 | 0.296 | 0.232 | 0.266 | 0.282 | 0.118 | |
| 3 000万 | 0.316 | 0.233 | 0.241 | 0.247 | 0.126 | |
| 5 000万 | 0.131 | 0.273 | 0.158 | 0.156 | 0.131 | |
| 8 000万 | 0.757 | 0.258 | 0.668 | 0.733 | 0.133 | |
| 10 000万 | 0.280 | 0.486 | 0.377 | 0.414 | 0.527 | |
表选项
从横向比较来看，Java的Hash表的平均存入时间随着输入数量级的提高而增长的速率明显快于二维Hash表。以扩充率为0.75为例，当数据量级达到1亿条时，Java的Hash表的平均存入时间比起100万条时增长了8.58倍，而二维Hash表的平均存入时间仅增长了2.28倍。
从纵向比较中，可以得出2个方面的结论：
1) 当数据量较小时，两者性能相当；当数据量较大时，二维Hash表的性能明显优于Java的Hash表。图 3为扩充率为0.75时, Java的Hash表与二维Hash表的平均存入时间对比。可以看到，当数据量小于1 000万时，两者性能相当；当数据量大于3 000万时，二维Hash表的性能要远远优于Java的Hash表，这也与在节2.3中分析的结论相符。
 |
| 图 3 扩充率为0.75时Java Hash表与二维Hash表的平均存入时间对比 |
| 图选项 |
2) 当扩充率较低时，两者的性能相当；当扩充率较高时，二维Hash表的性能明显优于Java的Hash表。图 4为扩充率为1.0时，Java的Hash表与二维Hash表的平均存入时间对比。可以看出，在所有数量级下，二维Hash表的性能都要优于Java Hash表。
 |
| 图 4 扩充率为1.0时Java Hash表与二维Hash表的平均存入时间对比 |
| 图选项 |
5 结论通过增加Hash表逻辑上的维度，可以大大降低Hash函数的冲突率，提高Hash表在较高填充率下的存储性能。从理论分析和实验数据中都可以看出，二维Hash表在降低冲突率和大数据量的存取性能方面，都要明显优于以Java的Hashtable为代表的一维Hash表。如果数据量级进一步增加，则可以采用三维乃至更高维度的Hash表，以进一步降低冲突率，达到更优的存取性能。
参考文献
| [1] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Zwolenski M, Weatherill L. The digital universe rich data and the increasing value of the Internet of things[J]. Australian Journal of Telecommunications & the Digital Economy, 2014, 2(3): 471–479. |
| [2] | Journal of Central South University(Science and Technology), 41(2):649-654.-->DeCandia G, Hastorun D, Jampani M, et al. Dynamo:Amazon's highly available key-value store[J]. ACM SIGOPS Operating Systems Review, 2007, 41(6): 205–220. DOI:10.1145/1323293 |
| [3] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Chang F, Dean J, Ghemawat S, et al. Bigtable:A distributed storage system for structured data[J]. ACM Transactions on Computer Systems (TOCS), 2008, 26(2): 4–4. |
| [4] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Lakshman A, Malik P. Cassandra:A decentralized structured storage system[J]. ACM SIGOPS Operating Systems Review, 2010, 44(2): 35–40. DOI:10.1145/1773912 |
| [5] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Henke C, Schmoll C, Zseby T. Empirical evaluation of Hash functions for multipoint measurements[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(3): 39–50. DOI:10.1145/1384609 |
| [6] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Christian H, Carsten S, Tanja Z. Empirical evaluation of Hash functions for packetID generation in sampled multipoint measurements[C]//Passive and Active Network Measurement, International Conference 2009. Seoul, Korea:Proceedings, 2009:197-206. |
| [7] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Rivest R L. The MD5 message-digest algorithm[J]. Network Working Group IETF, 1992, 473(10): 303–311. |
| [8] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Eastlake Rd D, Jones P. US Secure Hash Algorithm 1(SHA1)[M]. Los Argeles County:RFC Editor, 2001. |
| [9] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Peterson W W, Brown D T. Cyclic codes for error detection[J]. Proceedings of the IRE, 1961, 49(1): 228–235. DOI:10.1109/JRPROC.1961.287814 |
| [10] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Enbody R J, Du H C. Dynamic hashing schemes[J]. ACM Computing Surveys (CSUR), 1988, 20(2): 850–113. DOI:10.1145/46157.330532 |
| [11] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Larson P A. Dynamic hashing[J]. BIT Numerical Mathematics, 1978, 18(2): 184–201. DOI:10.1007/BF01931695 |
| [12] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Singh B, Yadav I, Agarwal S, et al. An efficient word searching algorithm through splitting and hashing the offline text[C]//Advances in Recent Technologies in Communication and Computing. Kottayam, India:IEEE Press, 2009:387-389. |
