Content deleted Content added
m Open access bot: url-access updated in citation with #oabot. |
m HTTP to HTTPS for SourceForge |
||
Line 119:
| last3 = Dietzfelbinger | first3 = Martin
| contribution = Hash, displace, and compress
| contribution-url =
| doi = 10.1007/978-3-642-04128-0_61
| ___location = Berlin
Line 130:
| 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
Line 195:
*[https://www.gnu.org/software/gperf/ gperf] is an [[open source]] 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
*[
*[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#
| |||