完美散列

对集合S的完美散列函数是一个将S的每个元素映射到一系列无冲突的整数的哈希函数。一个完美散列函数的应用与其他哈希函数的应用基本一致,但不需要任何冲突解决方案。在数学术语中,这是一个完全单射函数.

特性及使用

对于特定集合S的完美散列函数能在常数时间中被计算出,其映射值在一个相对小的范围内,能被一个随机化算法发现,该算法的操作次数与S的大小成正比.[1]任何适合在哈希表中使用的完美散列函数需要至少与S的大小成正比的位数。

一个值的位数被限定范围的完美散列函数能应用于高效查找操作中:假定查找键(key)与集合S(或与集合S关联的值)对应,然后将完美散列函数应用于查找键,得到哈希值(一个整数),然后在查找表中取出该整数对应的值。在集合S极少更新且查询频率非常多的情况下,使用完美hash函数是非常有效的。对集合S更新频率的限定是由于对任何集合S的修改,都将导致该完美散列函数退化为非完美散列函数。每次集合S被修改后自动更新hash函数的解决方案被称为dynamic perfect hashing,但这类方法非常复杂,难以实现。一个简单的允许动态更新集合S的完美散列函数的替代品叫cuckoo hashing

最小完美散列函数

最小完美散列函数是一个能将n个键(key)映射到n个连续的整数的完美散列函数。 产生的值通常为 [0..n−1] 或 [1..n]。正式表述如下:设jk是有限集合K的两个元素。F是一个最小完美散列函数iff F(j)=F(k)只在j=k的情况下成立(单射);并且存在整数a,使得F的范围为a..a+|K|−1。已经在数学上证明,通用的完美hash函数至少需要每个键(key)1.44 比特(bit)[2] 。而当前已知的最小完美hash散列函数每个键需要2.6 比特[3]

对一个最小完美散列函数F,若键以a1, a2, ..., an次序给出,对任意键aj and ak, j<k,意味着F(aj)<F(ak).[4] Order-preserving minimal perfect hash functions require necessarily Ω(n log n) bits to be represented.[5],我们称该最小完美散列函数F是保序的。

若对一个最小完美散列函数F,其应用变换后得到的值保持了键(key)的字典序,我们称该最小完美散列函数F为单调的。在此情况下,函数产生的值就是输入的键在所有可能的有序键序列中的位置。若被hash的键被存储于有序数组中,已实现一种策略,对每个键存储少量附加位(bits),以取得更快计算hash值的优势。[6]


请参阅

  • Dynamic perfect hashing
  • Pearson hashing
  • Succinct data structure
  • Universal hashing

索引

  1. ^ Fredman, M. L.; Komlós, J. N.; Szemerédi, E. Storing a Sparse Table with 0(1) Worst Case Access Time. Journal of the ACM. 1984, 31 (3): 538. doi:10.1145/828.1884. 
  2. ^ Belazzougui, D.; Botelho, F. C.; Dietzfelbinger, M. Hash, Displace, and Compress. Algorithms - ESA 2009 (PDF). LNCS 5757. 2009: 682 [2016-02-13]. ISBN 978-3-642-04127-3. doi:10.1007/978-3-642-04128-0_61. (原始内容存档 (PDF)于2011-07-24). 
  3. ^ Baeza-Yates, Ricardo; Poblete, Patricio V., Searching, Atallah, Mikhail J.; Blanton, Marina (编), Algorithms and Theory of Computation Handbook: General Concepts and Techniques 2nd, CRC Press, 2010, ISBN 9781584888239 . See in particular p. 2-10
  4. ^ Jenkins, Bob, order-preserving minimal perfect hashing, Black, Paul E. (编), Dictionary of Algorithms and Data Structures, U.S. National Institute of Standards and Technology, 14 April 2009 [2013-03-05], (原始内容存档于2009-01-30) 
  5. ^ Fox, E. A.; Chen, Q. F.; Daoud, A. M.; Heath, L. S. Order preserving minimal perfect hash functions and information retrieval. Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval - SIGIR '90. 1990: 279. ISBN 0897914082. doi:10.1145/96749.98233. 
  6. ^ Belazzougui, Djamal; Boldi, Paolo; Pagh, Rasmus; Vigna, Sebastiano, Theory and practice of monotone minimal perfect hashing, Journal of Experimental Algorithmics, November 2008, 16, Art. no. 3.2, 26pp, doi:10.1145/1963190.2025378 .

延伸内容

外部链接