Perfect hash function: Difference between revisions

Revision as of 01:55, 12 November 2023

Revision as of 10:24, 6 December 2023

Line 129:

| 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 = http://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 }}</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