创新计划

What We'd Like to Say

• Theory is modern art
• Attitude decides everthing

Perfect Hashing Function Principles and Practice

1.前言

在很多应用中，都要用到一种动态集合结构，它仅支持INSERT，SEARCH和DELETE字典操作。例如，计算机程序设计语言的编译程序需要维护一个符号表，其中元素的关键字值为任意字符串，与语言中的标示符对应。实现字典的一种有效数据结构为散列表(hash table)。 在最坏情况下，在散列表中，查找一个元素的时间与在链表中查找一个元素的时间相同，在最坏情况下都是Θ(n)，但在实践中，散列技术的效率是很高的。在一些合理的假设下，在散列表中查找一个元素的期望时间为O(1)。散列表是对普通数组概念的推广。[CLRS] 由于其具有其他很多数据结构都不具有的优点，散列的应用甚为广泛，从信息安全（例如文件校验，数字签名，签权协议）到搜索引擎(eMule)再到现在人们广泛应用的各种高速下载软件，都能看到其身影。可以说，如果没有它，Google都是不可能实现的。 毫无疑问，这种算法的探究具有重要意义。尽管前述各种方式看来在实现上似乎已经毫无问题，但是，我们要指出，完美散列仍然有一些问题没有解决，而这些问题也是在这种算法中最为重要的冲突。

2.正文

2.1 经典方法

当关键字的全域U比较小时，直接寻址是一种简单而有效的技术。

然而，直接寻址技术存在一个明显的问题，如果域很大，受内存的限制，这就有点不实际了。而且分配给表T的大部分空间都要浪费掉。1953年，H.P.Luhn[Luh53]首先提出了散列表这一技术，以及用于解决碰撞的链接(chaining)方法。 我们利用hash function h，根据关键字k计算出槽的位置： h：U→{0，1，…，m-1} 从而降低了空间开销。

这样做又有一个小问题：两个关键字可能映射到同一个槽上，我们称这种情形为发生了碰撞(collision)。我们需要采取有效的方法来避免碰撞。

2.1.1

链接法(chaining)是一种最简单的碰撞解决技术。在chaining中，把散列到同一槽中的所有元素都放在一个链表中，如图所示。槽j中有一个指针，它指向所有到j的元素构成的链表的头；如果不存在这样的元素，则j中为NIL。

2.1.2

在差不多同一时间，G.M.Amdahl首先提出了开放寻址法的思想。 在开放寻址法(open addressing)中，所有的元素都存放在散列表里。亦即，每个表项或包含动态集合的一个元素，或包含NIL。当查找一个元素时，要检查所有的表项，直到找到所需的元素，或者最终发现该元素不在表中。不像chaining，没有链表，没有元素存放在散列表外。Open addressing 的好处在于它根本不用指针，而是计算出要存取的各个槽。 有三种技术常用来计算open addressing中的探查序列：线性探查(linear probing)，二次探查(quadratic probing)，以及双重散列(double hashing)。 线性探查：给定一个普通的散列函数h’：U→{0，1，…，m-1}，linear probing采用的散列函数为：h ( k ， i )=( h’(k)+ i )mod m， i=0，1，…m-1。线性探查方法比较容易实现，但它存在一个问题，称为一次群集(primary clustering)。随着时间的推移，连续被占用的槽不断增加，平均查找时间也随着不断增加 二次探查：quadratic probing采用如下形式的的散列函数： h( k ， i ) = ( h’(k)+c1i+c2i2)mod m 初始的探查位置为T[h’(k)]，后续的探查位置要在此基础上加上一个偏移量，该偏移量以二次的方式依赖于探查号i。这种探查方法的效果要比线性探查好很多。 双重散列：double hashing是用于开放寻址法的最好方法之一，因为它所产生的排列具有随机选择的排列的许多特性。它采用如下的散列函数： h( k ， i )=( h1(k)+ih2(k))mod m 与线性探查或二次探查不同的是，这里的探查序列以两种方式依赖于关键字k，因为初始探查位置、偏移量都可能发生变化。如图所示，给出了一个用双重散列法进行插入的例子。此处，散列表的大小为13，h1(k) = k mod 13，h2(k) = 1+(k mod 11)。因为14≡1(mod 13)，且14≡3(mod 11)，故在探查了槽1和槽5，并发现它们已被占用后，关键字14被插入到空槽9中。

2.1.3

任何一个特定的散列函数都可能出现某种最坏情况形态：所有的关键字全部散列到同一个槽中。唯一有效的改进方法是随机地选择散列函数，使之独立于要存储的关键字。这种方法称作全域散列(universal hashing)。 全域散列的基本思想是在执行开始时，就从一族仔细设计的函数中，随机地选择一个作为散列函数。就像在quick sort中，随机化保证了没有哪一种输入会始终导致最坏情况形态。同时，随机化使得即使是对于同一个输入，算法在每一次执行时的形态也都不一样。这样就可以确保对于任何输入，算法都具有较好的平均情况性态。

2.1.4

算法导论中介绍的版本，假设了一个理想的散列函数（hash function），是一个完全随机的函数.这个假设叫Simple Uniform Hash Assumption (SUHA或者UHA)，认为经其散列后完全没有碰撞。 对这些经典方法的分析都建立在对hash function理想的假设前提下。SUHA为分析提供了方便，经典的结果例如TAOCP，算法导论等，都是基于这个假设。 这是一个过于理想的假设，实际中可以实现的散列函数是k-wise independent的，而k往往是一个常数。例如常用的linear congruential function (ax+b)mod n，它只是pair- wise independent，即2-wise。这已经成为了现实研究的一个瓶颈。

2.2 现代方法

2.2.1

如果某一种散列技术在进行查找时，其最坏情况内存访问次数为O(1)的话，则称其为完美散列(perfect hashing)。设计完全散列的基本想法是比较简单的。我们利用一种两级的散列方案，每一级采用全域散列，可以实现静态的部分功能。

perfect hashing是一个数据结构，它解决的问题是查找一个集合中元素的存在性.这也是计算机科学最经典的问题之一，Knuth的《计算机程序设计的艺术》第三卷《sorting and searching》的searching就是关于这个问题。这个问题的经典解法，二分查找和查找树等[Knu71]，时间复杂度都是O(log n)。 而 perfect hashing在线性的O(n)空间复杂度上达到了常数级的时间复杂度。这是历史上第一次达到这样的解.在此之前人们甚至不太相信我们可以同时在时间和空间上达到最优。无论对于多么庞大的数据集，要查找一个数据对象，只需要读三次即可，这是非常惊人的。可以说如果没有发现这个解，Google都是不可能实现的。 基于SUHA，数学上可以证明，O(1)时间复杂度下至少需要O(n2)的空间复杂度，这显然不能令人满意。

人类的愿望有两点： 1. O(1)时间O(n)空间(时、空复杂度同时最优) 2. 将理想的hash function假设转变为现实的假设。

2.2.2

第一点，人们一直以为不可能实现，人们以为二分查找的O(log n)复杂度对于线性空间已经最优了。直到Yao1981[Yao81]和Tarjan&Yao1979[TY79]提出了O(1)时间和O(n)空间的可能，但它们二者都对hash function的定义域提出了不符合现实的假设，前者需要假设hash function的定义域极大，后者却假设太小。这两个方法都不是现实中可以使用的方法，但却为实现perfect hashing的梦想开启了一扇门，使人们意识到这是可能的。 1984年，基于Yao的工作，由三位数学家Fredman ，Komlos和Szemeredi提出的FKS perfect hashing[FKS84]，可以使每次查询只需要常数级的时间，而且数据结构的空间复杂度仍然只有线性的O(n)。 FKS算法的思路是把hash table分散到两级： In the first level, n items are hashed to n buckets by a 2-universal hash function h. Let Bi be the set of items hashed to the it h bucket. In the second level, construct a | Bi | 2-size perfect hashing for each bucket Bi. The data structure can be stored in a table. The first few entries are reserved to store the primary hash function h. To help the searching algorithm locate a bucket, we use the next n entries of the table as the "pointers" to the bucket: each entry stores the address of the first entry of the space to store a bucket. In the rest of table, the n buckets are stored in order, each using a | Bi | 2 space as required by perfect hashing.

26年过去了，这个漂亮的理论结果对计算机理论研究产生了深远的影响。在实际应用中，Linux下的CMPH library实现了基于FKS思想的一系列数据结构。然而CMPH library只针对静态的情况，即数据集不会改变。FSK算法只是静态的，而实际应用中往往需要更新(update)。 1994年，数据集中的元素被动态的添加（insert）和删除（delete）在理论上已经得到常数级的解[DKM+94]。然而这个结果在现实中仍然缺乏很好的实现，目前还没有任何标准库实现了这一功能。其原因是它所利用的散列函数 （hash function）的计算需要很多的乘法运算，这在理论模型中是被忽略的，但在苛刻的现实条件中，cpu做乘法被认为是及其低效的。 这个结果还有个缺陷，不是最坏时间复杂度O(1)而是amortized time complexity，平摊时间复杂度是O(1)。原因在于FKS的hash function的分配并不平均。

2.2.3

第二点，由理想的simple uniform hash assumption转为Carter-Wegman[CW79]的universal classes of hash functions。universal classes of hash functions可以被视为一条链接理论和现实的辅助线。从理论的角度而言，它是更弱的随机性假设。从现实的角度，它是可以有效实现的随机性保证。因此，从universal hashing的假设出发，可以严格的证明(而不是基于理想的假设)hash table的效率。Carter-Wegman原始的universal hash function的构造是基于多项式，效率不够好（因为需要乘法和模运算）。[DHKP97]提出了新的universal hash function的构造，非常高效，因此在实践中大量使用。这个函数甚至可以被表示成为仅仅一行的c代码： h(x) = a * x >> ( 32 – k ); 它的不足在于随机性能不够好(只保证pair-wise independence)，因此在FKS中使用仍然无法做到平均分配。因此动态更新的时间复杂度无法从amortized O(1) time改进为worst-case O(1) time。对此，[DMadH90]中的hash function可以做到FKS的worst-case O(1) time所需的足够的随机性。然而，[DMadH90]中的hash function无论空间的使用(O(sqrt(n)))还是计算的效率都远远落后与[DHKP97]提出的那个已在在现实中大量应用hash function。因此现实中人们宁愿忍受糟糕的worst-case time complexity，也仍旧使用随机性不够好却可以高效计算的[DHKP97]的hash function。 我们需要解决这一对矛盾。寻找既有良好随机性,足够另FKS拥有worst-case O(1) time，又可以高效率计算的hash function。

2.2.4

最新发展情况。出现了cuckoo hashing，其基本思想是使用两个hash function而不是只用一个，这样对于每个关键词有两个可能的位置。当插入一个新关键词的时候，采用贪心法，如果该位置已经被占，则像杜鹃一样把它踢出巢，被踢出的元素寻找下一个可选位置，这个定义是递归的。对于cuckoo hashing，Pagh 2001[Pag01]提出了静态版本。Pagh， Rodler 2004[PR04]提出了动态版本。两个目前都基于uniform hash assumption的理想假设。理论上，使用uniform hashing function是open problem, 实践中，目前根本没有实现cuckoo hashing的标准库。 因此我们可以实验cuckoo hashing在实际hash function上的性能，以及实现一个可以用的cuckoo hashing 库。

3.小结

3.1

关于现有的perfect hashing库如CMPH、gperf、Sux4J。 上面已经提过了，在实际应用中，Linux下的CMPH library实现了基于FKS思想的一系列数据结构。然而CMPH library只针对静态的情况，即数据集不会改变。同样的，gperf和Sux4j也类似。

3.2

我们要做的就是在有限的独立性假设下，支持完美散列。这是非常有现实意义的一件事。[DKM+94]这个结果没有很好的实现，主要原因是对于散列函数的假设过于理想，这是一个比较基本的难点。 1.同时，我们需要解决随机性和运算效率之间的矛盾，得到一个令人较为满意的散列函数。 2.此外，测试cuckoo hashing的性能，并实现一个可以用的cuckoo hashing库。 3.实现一个动态perfect hashing的Linux open source library。 4.尝试对成果数学性质的证明。

3.3

可能的实践方案如下:

 第一步：在前人的假设基础上以及理论支持下(包括使用已有的解决碰撞的问题和已有的散列函数)实现静态版本的完美散列，从中体会散列表这种数据结构优点及其存在的不足。
 第二步：在第一步的基础上，实现动态版本的完美散列。主要实现数据的更新，包括对关键字的增加和更改等。
 第三步：自己独立设计散列函数，记录构造过程。然后在用自己的散列函数去实现静态和动态的完美散列。
 第四步：从理论上论证函数的可行性。推导构造同类函数的具体过程。
 第五步：将解决碰撞的函数和实现动态更新功能的完美散列联系起来，得到综合性解决方案，针对前述的问题加以修正完善。
 第六步：做出令人满意的库函数。至少可以做出比目前的标准库更好的。
 第七步：尝试对数学性质的证明。

4.References

• [CLRS] T.H. Cormen， C.E. Leiserson， R.L. Rivest， and C. Stein. Introduction to Algorithms.
• [CW79] J.L. Carter and M.N. Wegman. Universal classes of hash functions. Journal of computer and system sciences， 18(2):143{154，1979.
• [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WH3-45NJK2G-2&_user=6422187&_coverDate=10/31/1997&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_searchStrId=1512562639&_rerunOrigin=scholar.google&_acct=C000056877&_version=1&_urlVersion=0&_userid=6422187&md5=8f79b5111fe7a572f057cce708aa0ff0&searchtype=a[DHKP97]</nowki> M. Dietzfelbinger， T. Hagerup， J. Katajainen， and M. Penttonen. A Reliable Randomized Algorithm for the Closest-Pair Problem. Journal of Algorithms， 25(1):19{51， 1997.] *[http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=21968&tag=1<nowiki>[DKM+94]</wiki> M. Dietzfelbinger， A. Karlin， K. Mehlhorn， F.M. Heide，H. Rohnert， and R.E. Tarjan. Dynamic perfect hashing: Upper and lower bounds. SIAM Journal on Computing， 23(4):738{761， 1994.] *[http://www.springerlink.com/content/5467537110456057/<nowiki>[DMadH90] M. Dietzfelbinger and F. Meyer auf der Heide. A new universal class of hash functions and dynamic hashing in real time. In Proceedings of the 17th International Colloquium on Automata， Languages and Programming (ICALP'90)， volume 443， pages

6{19. Springer， 1990.]

• [FKS84] M.L. Fredman， J. Koml_os， and E. Szemer_edi. Storing a SparseTable with O(1) Worst Case Access Time. Journal of the ACM (JACM)， 31(3):538{544， 1984.
• [GBY91] G.H. Gonnet and R.Baeza-Yates. Handbook of algorithms and data structures: in Pascal and C. Addison-Wesley， 1991.

[Knu71] D.E. Knuth. Optimum binary search trees. Acta Informatica， 1(1):14{25， 1971. [Knu73] D.E. Knuth. The art of computer programming. Vol. 3， Sortingand Searching. Addison-Wesley， 1973. [Luh53] H.P. Luhn. A New Method of Recording and Searching Information. American Documentation， page 14， 1953. [Pag01] R. Pagh. On the cell probe complexity of membership and perfect hashing. In Proceedings of the thirty-third annual ACM symposium on Theory of computing， pages 425{432. ACM New York， NY， USA， 2001. [PR04] R. Pagh and F.F. Rodler. Cuckoo hashing. Journal of algorithms， 51(2):122{144， 2004. [TY79] R.E. Tarjan and A.C.C. Yao. Storing a sparse table. Communications of the ACM， 22(11):606{611， 1979. [Yao81] A.C.C. Yao. Should Tables Be Sorted? Journal of the ACM(JACM)， 28(3):615{628， 1981.