Perfect hash function: Difference between revisions

Revision as of 01:55, 12 November 2023

Latest revision as of 02:43, 11 August 2025

(7 intermediate revisions by 7 users not shown)

Line 20:

==Performance of perfect hash functions==

The important performance parameters for perfect hashing are the representation size, the evaluation time, the construction time, and additionally the range requirement <math>\frac{m}{n}</math> (average number of buckets per key in the hash table).<ref name="CHD"/> The evaluation time can be as fast as {{math|''O''(''1'')}}, which is optimal.<ref name="inventor"/><ref name="CHD"/> The construction time needs to be at least {{math|''O''(''n'')}}, because each element in {{mvar|S}} needs to be considered, and {{mvar|S}} contains {{mvar|n}} elements. This lower bound can be achieved in practice.<ref name="CHD"/>

The lower bound for the representation size depends on {{mvar|m}} and {{mvar|n}}. Let {{math|''m'' {{=}} (1+&epsilon;) ''n''}} and {{mvar|h}} a perfect hash function. A good approximation for the lower bound is <math>\log e - \varepsilon \log \frac{1+\varepsilon}{\varepsilon}</math> Bits per element. For minimal perfect hashing, {{math|&epsilon; {{=}} 0}}, the lower bound is {{math|log e ≈ 1.44}} bits per element.<ref name="CHD"/>

Line 95:

==Extensions==

===Memory address identity===

A trivial but pervasive example of perfect hashing is implicit in the (virtual) [[Virtual Memory|memory address space]] of a computer. Since each byte of virtual memory is a distinct, unique, directly addressable storage ___location, the value of the [[Pointer (computer programming)|starting address]] where any object is stored in memory can be considered a ''de facto'' perfect hash of that object into the entire memory address range.<ref>{{cite book|publisher=[[Springer Science+Business Media]]|url=https://books.google.com/books?id=66jBbZYOt-EC&pg=PA254|page=254|author1=Witold Litwin|author2=Tadeusz Morzy|author3=Gottfried Vossen|date=19 August 1998|isbn= 9783540649243|title=Advances in Databases and Information Systems}}</ref>

===Dynamic perfect hashing===

{{main article|Dynamic perfect hashing}}

Line 122 ⟶ 119:

| last3 = Dietzfelbinger | first3 = Martin

| contribution = Hash, displace, and compress

| contribution-url = httphttps://cmph.sourceforge.net/papers/esa09.pdf

| doi = 10.1007/978-3-642-04128-0_61

| ___location = Berlin

Line 129 ⟶ 126:

| publisher = Springer

| series = [[Lecture Notes in Computer Science]]

| title = Algorithms - ESA 2009

| title = Algorithms—ESA 2009: 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009, Proceedings

| volume = 5757

| isbn = 978-3-642-04127-3

| year = 2009| citeseerx = 10.1.1.568.130

| url = httphttps://cmph.sourceforge.net/papers/esa09.pdf

}}.</ref> Assuming that <math>S</math> is a set of size <math>n</math> containing integers in the range <math>[1, 2^{o(n)}]</math>, it is known how to efficiently construct an explicit minimal perfect hash function from <math>S</math> to <math>\{1, 2, \ldots, n\}</math> that uses space <math>n \log_2 e + o(n)</math>bits and that supports constant evaluation time.<ref>{{Citation |lastlast1=Hagerup |firstfirst1=Torben |title=Efficient Minimal Perfect Hashing in Nearly Minimal Space |date=2001 |url=http://dx.doi.org/10.1007/3-540-44693-1_28 |work=STACS 2001 |pages=317–326 |access-date=2023-11-12 |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |isbn=978-3-540-41695-1 |last2=Tholey |first2=Torsten|doi=10.1007/3-540-44693-1_28 |url-access=subscription }}</ref> In practice, there are minimal perfect hashing schemes that use roughly 1.56 bits/key if given enough time.<ref name="RecSplit">{{citation

| last1 = Esposito | first1 = Emmanuel

| last2 = Mueller Graf | first2 = Thomas

Line 145 ⟶ 143:

| arxiv = 1910.06416

| doi-access = free

}}.</ref><ref>[https://github.com/iwiwi/minimal-perfect-hash minimal-perfect-hash (GitHub)]</ref>

}}.</ref>

===k-perfect hashing===

Line 192 ⟶ 190:

* Marshall D. Brain and Alan L. Tharp. "Near-perfect Hashing of Large Word Sets". Software—Practice and Experience, vol. 19(10), 967-078, October 1989. John Wiley & Sons.

* Douglas C. Schmidt, [http://www.dre.vanderbilt.edu/~schmidt/PDF/gperf.pdf GPERF: A Perfect Hash Function Generator], C++ Report, SIGS, Vol. 10, No. 10, November/December, 1998.

* Hans-Peter Lehmann, Thomas Mueller, Rasmus Pagh, Giulio Ermanno Pibiri, Peter Sanders, Sebastiano Vigna, Stefan Walzer, "Modern Minimal Perfect Hashing: A Survey", {{arxiv|2506.06536}}, June 2025. Discusses post-1997 developments in the field.

==External links==

*[https://www.gnu.org/software/gperf/ gperf] is an [[Openopen Sourcesource]] C and C++ perfect hash generator (very fast, but only works for small sets)

*[http://burtleburtle.net/bob/hash/perfect.html Minimal Perfect Hashing (bob algorithm)] by Bob Jenkins

*[httphttps://cmph.sourceforge.net/index.html cmph]: C Minimal Perfect Hashing Library, open source implementations for many (minimal) perfect hashes (works for big sets)

*[http://sux.di.unimi.it/ Sux4J]: open source monotone minimal perfect hashing in Java

*[https://web.archive.org/web/20130729211948/http://www.dupuis.me/node/9 MPHSharp]: perfect hashing methods in C#