Perfect hash function: Difference between revisions

Revision as of 14:11, 18 April 2022

Revision as of 23:55, 27 April 2022

Line 52:

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|(&Phi;₁, &Phi;₂, &Phi;₃, ...)}}, starting with {{math|&Phi;₁}}. 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 &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 ≤ 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 67:

(6) '''repeat''' forming K_i{{thin space}}&larr;{{thin space}}{{{math|&Phi;}}_l(x)|x{{thin space}}∈{{thin space}}B_i}

(6) '''until''' |K_i|=|B_i| '''and''' K_i&cap;{j|T[j]=1}={{thin space}}&emptyset;

(7) '''let''' &sigma;σ(i):= the successful l

(8) '''for all''' j{{thin space}}∈{{thin space}}K_i '''let''' T[j]:={{thin space}}1

(9) Transform (&sigma;σ_i)_0&le;i<r into compressed form, retaining {{math|''O''(''1'')}} access.

==Space lower bounds==

Line 116:

===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|lg ''e'' &approx;≈ 1.44}} bits/key.<ref name="CHD">{{citation

| last1 = Belazzougui | first1 = Djamal

| last2 = Botelho | first2 = Fabiano C.

Line 152:

(6) '''repeat''' forming K_i{{thin space}}&larr;{{thin space}}{{{math|&Phi;}}_l(x)|x{{thin space}}∈{{thin space}}B_i}

(6) '''until''' |K_i|=|B_i| '''and''' K_i&cap;{j|<u>T[j]=k</u>}={{thin space}}&emptyset;

(7) '''let''' &sigma;σ(i):= the successful l

(8) '''for all''' j{{thin space}}∈{{thin space}}K_i '''set''' <u>T[j]&larr;T[j]+1</u>