Content deleted Content added
m Open access bot: doi updated in citation with #oabot. |
m HTTP to HTTPS for SourceForge |
||
| (10 intermediate revisions by 10 users not shown) | |||
Line 6:
Perfect hash functions may be used to implement a [[lookup table]] with constant worst-case access time. A perfect hash function can, as any [[hash function]], be used to implement [[hash table]]s, with the advantage that no [[Hash table#Collision resolution|collision resolution]] has to be implemented. In addition, if the keys are not in the data and if it is known that queried keys will be valid, then the keys do not need to be stored in the lookup table, saving space.
Disadvantages of perfect hash functions are that {{mvar|S}} needs to be known for the construction of the perfect hash function. Non-dynamic perfect hash functions need to be re-constructed if {{mvar|S}} changes. For frequently changing {{mvar|S}} [[dynamic perfect hashing|dynamic perfect hash functions]] may be used at the cost of additional space.<ref name="DynamicPerfectHashing" /> The space requirement to store the perfect hash function is in {{math|''O''(''n'')}} where {{math|''n''}} is the number of keys in the structure.
The important performance parameters for perfect hash functions are the evaluation time, which should be constant, the construction time, and the representation size.
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+ε) ''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|ε {{=}} 0}}, the lower bound is {{math|log e ≈ 1.44}} bits per element.<ref name="CHD"/>
Line 95:
==Extensions==
===Dynamic perfect hashing===
{{main article|Dynamic perfect hashing}}
Line 117 ⟶ 114:
===Minimal perfect hash function===
A minimal perfect hash function is a perfect hash function that maps {{mvar|n}} keys to {{mvar|n}} consecutive integers – usually the numbers from {{math|0}} to {{math|''n'' − 1}} or from {{math|1}} to {{mvar|n}}. A more formal way of expressing this is: Let {{mvar|j}} and {{mvar|k}} be elements of some finite set {{mvar|S}}. Then {{mvar|h}} is a minimal perfect hash function if and only if {{math|1=''h''(''j'') = ''h''(''k'')}} implies {{math|1=''j'' = ''k''}} ([[injectivity]]) and there exists an integer {{mvar|a}} such that the range of {{mvar|h}} is {{math|1=''a''..''a'' + {{!}}''S''{{!}} − 1}}. It has been proven that a general purpose minimal perfect hash scheme requires at least
| last1 = Belazzougui | first1 = Djamal
| last2 = Botelho | first2 = Fabiano C.
| last3 = Dietzfelbinger | first3 = Martin
| contribution = Hash, displace, and compress
| contribution-url =
| 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
| volume = 5757
| isbn = 978-3-642-04127-3
| year = 2009| citeseerx = 10.1.1.568.130
| url =
}}.</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 |last1=Hagerup |first1=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>
===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 [[
*[http://burtleburtle.net/bob/hash/perfect.html Minimal Perfect Hashing (bob algorithm)] by Bob Jenkins
*[
*[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#
| |||