ACM通信
研究突出了
技术角度:构建更好的哈希函数
哈希无处不在。首先，哈希表是最广泛使用的原始数据结构之一，有许多变体(开放地址、链式、线性探测、多项选择、布谷鸟，等等)。哈希也经常用于抽样;哈希所有项目，只保留那些具有特定哈希值的项目作为示例。哈希在流数据和非流数据草图的各种算法和数据结构中扮演着重要的角色，比如Bloom过滤器和近似计数结构。
在哈希的早期历史中，理论和实践之间存在着明显的分歧。哈希和哈希算法的数学分析过去是(现在仍然是)基于完全随机性。对于每个输入，你都假设是这样x，哈希值h（x)均匀分布在它可以取的所有可能值上，并且每个值h（x)独立于所有其他散列值h（y)yx．这种完美的哈希函数使数学分析变得更加简单，因为每一个新的哈希值看起来都是完全随机的。
当然，没有人会真正使用完美的哈希函数;在任何合理的计算模型下，它们都需要指数级的空间来存储。相反，在实践中，人们使用各种方法来获得伪随机哈希函数。Knuth提供了这种类型的各种哈希方法的早期指南，例如乘以一个常数和移位以获得更高阶的位。2有些人求助于加密哈希函数，尽管对于许多哈希目的来说，这种函数实际上可能不是适当随机的，而且在使用它们的系统中，速度可能会慢到成为瓶颈。
现实世界中有很多哈希函数都没有可证明的保证。也许这种哈希函数最大的危险是，它们可能在大量测试中工作得很好，产生一种错误的安全感，但在面对不是随机的真实数据时，它们可能会失败得很惨。它们的行为通常看起来就像假设完全随机的分析所预测的那样，直到事实并非如此。不幸的结构化数据集可能会破坏这种散列函数，进而破坏依赖它们的系统。
理论计算机科学试图开发出能够同时提供这两个世界最好的框架:实用的哈希函数以及可证明的保证。关键的见解是，完美的随机性虽然更容易分析，但通常不是保证理想结果的必要条件。通过在分析中多加注意，我们通常可以从我们的哈希函数中确定我们真正需要什么，并根据这些需求调整我们对哈希函数的选择。这项工作似乎始于卡特和韦格曼的开创性工作，1他认为，对于性能良好的哈希表，哈希值并不都需要完全独立。相反，假设我们从范围为[的哈希函数族中随机选择一个哈希函数。0, B)，以便对任意两个元素x而且y，它们得到相同哈希值的概率只有1/B．这足以表明标准链式哈希表的性能很好。更一般的情况是，在其他一些设置中，分析可能只要求我们从哈希函数家族中随机选择一个哈希函数，以便任何集合k哈希值是独立的，对于一个小的值k。幸运的是，有这样的家庭k-独立的哈希函数，只需要少量的空间和计算时间，每个成比例k，它们适用于许多应用。不幸的是，我们关心的许多其他应用程序似乎需要对数独立性(或更多)，对于这类应用程序，散列函数的计算时间可能会变得令人望而却步。尽管如此，这些基本思想已经阐明，我们确实可以在许多情况下获得具有可证明保证的实际哈希函数，只要我们清楚地了解我们到底需要从哈希函数中得到什么。
在接下来的文章中，Mikkel Thorup描述了另一种简单但惊人有效和强大的哈希函数变体，它是基于使用随机哈希值的小表。这种方法被称为表格哈希。表格哈希实际上可以追溯到20世纪60年代末，当时Zobrist使用它来创建电脑游戏中棋盘位置的标识符。3.几十年来，它的力量一直被忽视，直到索鲁普(和他的同事)重新启用了这种方法。他展示了表格哈希如何提供实践中经常需要的一般集中保证类型，以及某些关键算法和数据结构的特定保证，包括布谷鸟哈希、线性探测和基于桶的抽样。在某些情况下，这些结果来自于简单的表格哈希，但对于某些问题，他还展示了某些改进如何提供更强的保证，而不需要付出太多的空间和运行时间代价。他介绍的其中一种“扭转”甚至被称为扭曲表格哈希。
简而言之，Thorup的工作表明，表列哈希在更多情况下提供了巨大的潜力，我们可以鱼龙俱下:也就是说，我们可以安全地知道我们的哈希提供了理论上的可靠保证，同时还拥有一个实际的哈希函数的效率，而不会成为系统瓶颈。
参考文献
1.Carter, J.L.和Wegman, M.N.哈希函数的通用类。J.计算机与系统科学， 2(1979)， 143154。
数字图书馆是由计算机协会出版的。版权所有©2017 ACM股份有限公司
没有发现记录