Perfect hash function: Difference between revisions

Revision as of 09:18, 11 March 2022

Revision as of 14:11, 18 April 2022

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 132:

| year = 2009| citeseerx = 10.1.1.568.130

| url = http://cmph.sourceforge.net/papers/esa09.pdf

}}.</ref> TheAlthough bestthis currentlyspace bound has been achieved by theoretical works, in practice, the best known minimal perfect hashing schemes can be represented using lessrequire thanroughly 1.56 bits/key if given enough time.<ref name="RecSplit">{{citation

| last1 = Esposito | first1 = Emmanuel

| last2 = Mueller Graf | first2 = Thomas