随着互联网的发展，自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 . $ |
目前对一维Hash表性能的分析，一般只考虑填充率，这是因为在数据量不大的情况下，Hash函数的冲突率通常要比填充率小2个量级，所以一般情况下有δ≈α, 因而在分析中Hash函数的冲突率往往就被忽略了。
1.4 存取效率目前对Hash表的性能一般通过平均查找长度来衡量，在此方面已有较为成熟的结论，如表 1所示。
| 处理方法 | 查找成功 | 查找失败 |
| 链地址法 | α+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 _{Ⅱ}}). $ |
由于0≤α≤1，βⅠ>βⅡ，因此δ1≥δ2，当且仅当填充率α=1时取等号。即在填充率相同的情况下，除非表被填满(即α=1)，否则一维Hash表的失效率要大于二维Hash表的失效率。
2.3 Hash效率分析这里以Hash表的平均存入时间ta作为性能指标，ta可分为2部分，一部分是计算Hash值的时间th，另一部分是实际访存的时间ts。因此ta可表示为
| $ {t_{\rm{a}}} = {t_{\rm{h}}} + {t_{\rm{s}}}. $ |
对于一维Hash表而言，以链地址法为例，只需要一次Hash计算和最多2次访存就可以完成数据的存入。假设一维Hash表的失效率为δ1，则平均存入时间为
| $ {t_{{\rm{a}}1}} = {t_{\rm{h}}} + {t_{\rm{s}}} + {\delta _1}{t_{\rm{s}}} = {t_{\rm{h}}} + (1 + {\delta _1}){t_{\rm{s}}}. $ |
对于二维Hash表而言，如果也采取链地址法，则完成一次数据的存入需要2次Hash计算和最多2次访存。为了便于分析，假设二维Hash表的2个维度采用计算复杂度相同的Hash函数，计算时间都为th，二维Hash表的失效率为δ2，则平均存入时间为
| $ {t_{a2}} = 2{t_{\rm{h}}} + {t_{\rm{s}}} + {\delta _2}{t_{\rm{s}}} = 2{t_{\rm{h}}} + (1 + {\delta _2}){t_{\rm{s}}}. $ |
根据前面对冲突率的分析，可知δ2比δ1要小2~4个数量级，这里假设δ1=2 000δ2。另一方面，一般的Hash函数计算，多以加减和移位操作为主，Hash值计算时间比访存操作时间要短。由于数据密集型应用处理的数据通常不是很长，通过对平均长度不超过20的随机字符串进行测试的结果，这里给出一个合理的估计值ts=5th，则有
| $ \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} $ |
前面曾经提高到，一般的Hash函数的冲突率的量级介于万分之一到百分之一之间，这里假设
| $ \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. $ |
由此可见：在最差的情况下，二维Hash表的平均存入时间与一维Hash表相当(略差)；而在最好的情况下，二维Hash表的平均存入时间比一维Hash表缩短了了1个数量级。
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}}. $ |
其中：ch是每个字符的ASCII码值，H初始化为0，“≪”是左移位操作。
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表的在不同样本数和扩充率下的平均存入时间表。
| 样本数 | 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 | |
| 样本数 | 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] | 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] | 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] | 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] | 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] | 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] | 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] | Rivest R L. The MD5 message-digest algorithm[J]. Network Working Group IETF, 1992, 473(10): 303–311. |
| [8] | Eastlake Rd D, Jones P. US Secure Hash Algorithm 1(SHA1)[M]. Los Argeles County:RFC Editor, 2001. |
| [9] | 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] | 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] | Larson P A. Dynamic hashing[J]. BIT Numerical Mathematics, 1978, 18(2): 184–201. DOI:10.1007/BF01931695 |
| [12] | 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. |