Content deleted Content added
m convert special characters (via WP:JWB) |
JMarianczuk (talk | contribs) added concrete numbers for the CHD representation size |
||
Line 53:
Then, in descending order of size, each bucket's elements are hashed by a hash function of a sequence of independent fully random hash functions {{math|(Φ<sub>1</sub>, Φ<sub>2</sub>, Φ<sub>3</sub>, ...)}}, starting with {{math|Φ<sub>1</sub>}}. If the hash function does not produce any collisions for the bucket, and the resulting values are not yet occupied by other elements from other buckets, the function is chosen for that bucket. If not, the next hash function in the sequence is tested.<ref name="CHD" />
To evaluate the perfect hash function {{math|''h''(''x'')}} one only has to save the mapping σ of the bucket index {{math|''g''(''x'')}} onto the correct hash function in the sequence, resulting in {{math|h(x) {{=}} Φ<sub>σ(g(x))</sub>}}.<ref name="CHD" />
Finally, to reduce the representation size, the (σ(i))<sub>0≤i<r</sub> are compressed into a form that still allows the evaluation in {{math|''O''(''1'')}}.<ref name="CHD" />
This approach needs linear time in {{mvar|n}} for construction, and constant evaluation time
===Pseudocode===
Line 88:
For minimal perfect hash functions the information theoretic space lower bound is
:<math>\log_2e\approx1.44</math>
For perfect hash functions, it is first assumed that the range of {{mvar|h}} is bounded by {{mvar|n}} as {{math|''m'' {{=}} (1+ε) ''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>
==Extensions==
| |||