Perfect hash function: Difference between revisions

Revision as of 22:14, 4 October 2021

Revision as of 02:23, 22 October 2021

Line 55:

To evaluate the perfect hash function {{math|''h''(''x'')}} one only has to save the mapping &sigma; of the bucket index {{math|''g''(''x'')}} onto the correct hash function in the sequence, resulting in {{math|h(x) {{=}} &Phi;_{&sigma;(g(x))}}}.<ref name="CHD" />

Finally, to reduce the representation size, the ({{math|&sigma;(i))_{0&le; ≤ i < r}}} 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. The representation size is in {{math|''O''(''n'')}}, and depends on the achieved range. For example, with {{math|''m'' {{=}} 1.23''n''}} {{harvtxt|Belazzougui|Botelho|Dietzfelbinger|2009}} achieved a representation size between 3.03 bits/key and 1.40 bits/key for their given example set of 10 million entries, with lower values needing a higher computation time. The space lower bound in this scenario is 0.88 bits/key.<ref name="CHD" />

Line 61:

===Pseudocode===

'''algorithm''' ''hash, displace, and compress'' '''is'''

(1) Split S into buckets {{math|B_i :={{thin space=}} g^-1({i})&cap;{{thin space}}S,0&le; ≤ i < r}}

(2) Sort buckets B_i in falling order according to size |B_i|

(3) Initialize array T[0...m-1] with 0's