Editing Perfect hash function (section)

==Space lower bounds==
The use of {{math|''O''(''n'')}} words of information to store the function of {{harvtxt|Fredman|Komlós|Szemerédi|1984}} is near-optimal: any perfect hash function that can be calculated in constant time
requires at least a number of bits that is proportional to the size of {{mvar|S}}.<ref>{{citation
 | last1 = Fredman | first1 = Michael L. | author1-link = Michael Fredman
 | last2 = Komlós | first2 = János | author2-link = János Komlós (mathematician)
 | doi = 10.1137/0605009
 | issue = 1
 | journal = [[SIAM Journal on Algebraic and Discrete Methods]]
 | mr = 731857
 | pages = 61–68
 | title = On the size of separating systems and families of perfect hash functions
 | volume = 5
 | year = 1984}}.</ref>

For minimal perfect hash functions the information theoretic space lower bound is
:<math>\log_2e\approx1.44</math>
bits/key.<ref name="CHD" />

For perfect hash functions, it is first assumed that the range of {{mvar|h}} is bounded by {{mvar|n}} as {{math|''m'' {{=}} (1+&epsilon;) ''n''}}. With the formula given by {{harvtxt|Belazzougui|Botelho|Dietzfelbinger|2009}} and for a [[Universe (mathematics)|universe]] <math>U\supseteq S</math> whose size {{math|{{!}}''U''{{!}} {{=}} ''u''}} tends towards infinity, the space lower bounds is
:<math>\log_2e-\varepsilon \log\frac{1+\varepsilon}{\varepsilon}</math>
bits/key, minus {{math|log(''n'')}} bits overall.<ref name="CHD" />