完美散列

對集合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]。正式表述如下：設j和k是有限集合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，若鍵以a₁, a₂, ..., a_n次序給出，對任意鍵a_j and a_k, j<k，意味着F(a_j)<F(a_k).^[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]

請參閱[編輯]

索引[編輯]

^ 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.
^ 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）.
^ 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
^ 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）
^ 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.
^ 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 .

延伸內容[編輯]

Richard J. Cichelli. Minimal Perfect Hash Functions Made Simple, Communications of the ACM, Vol. 23, Number 1, January 1980.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 11.5: Perfect hashing, pp. 245–249.
Fabiano C. Botelho, Rasmus Pagh and Nivio Ziviani. "Perfect Hashing for Data Management Applications".
Fabiano C. Botelho and Nivio Ziviani. "External perfect hashing for very large key sets"（頁面存檔備份，存於網際網路檔案館）. 16th ACM Conference on Information and Knowledge Management (CIKM07), Lisbon, Portugal, November 2007.
Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, and Sebastiano Vigna. "Monotone minimal perfect hashing: Searching a sorted table with O(1) accesses". In Proceedings of the 20th Annual ACM-SIAM Symposium On Discrete Mathematics (SODA), New York, 2009. ACM Press.
Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, and Sebastiano Vigna. "Theory and practise of monotone minimal perfect hashing". In Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 2009.
Douglas C. Schmidt, GPERF: A Perfect Hash Function Generator, C++ Report, SIGS, Vol. 10, No. 10, November/December, 1998.

外部連結[編輯]

Minimal Perfect Hashing（頁面存檔備份，存於網際網路檔案館） by Bob Jenkins
gperf（頁面存檔備份，存於網際網路檔案館） is an Open Source C and C++ perfect hash generator
cmph（頁面存檔備份，存於網際網路檔案館） is Open Source implementing many perfect hashing methods
Sux4J（頁面存檔備份，存於網際網路檔案館） is Open Source implementing perfect hashing, including monotone minimal perfect hashing in Java
MPHSharp is Open Source implementing many perfect hashing methods in C#

[发现者-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 .

[1]

[2]

[3]

[4]

[5]

[6]