Editing Perfect hash function (section)

===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'' &minus; 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''{{!}} &minus; 1}}. It has been proven that a general purpose minimal perfect hash scheme requires at least <math>\log_2 e \approx 1.44</math> bits/key.<ref name="CHD">{{citation
 | last1 = Belazzougui | first1 = Djamal
 | last2 = Botelho | first2 = Fabiano C.
 | last3 = Dietzfelbinger | first3 = Martin
 | contribution = Hash, displace, and compress
 | contribution-url = http://cmph.sourceforge.net/papers/esa09.pdf
 | doi = 10.1007/978-3-642-04128-0_61
 | location = Berlin
 | mr = 2557794
 | pages = 682–693
 | 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 = 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 |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 }}</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
 | last3 = Vigna | first3 = Sebastiano
 | contribution = RecSplit: Minimal Perfect Hashing via Recursive Splitting
 | doi = 10.1137/1.9781611976007.14
 | pages = 175–185
 | series = [[Proceedings]]
 | title = 2020 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX)
 | year = 2020
 | arxiv = 1910.06416
 | doi-access = free
 }}.</ref>