跳至內容

完美散列

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

對集合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]


請參閱

索引

  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 .

延伸內容

外部連結