Revision as of 07:43, 12 April 2020 edit OAbot (talk \| contribs) Bots 643,717 edits m Open access bot: doi added to citation with #oabot. ← Previous edit		Revision as of 21:00, 25 April 2020 edit undo JayBeeEll (talk \| contribs) Extended confirmed users, New page reviewers, Temporary account IP viewers 29,607 edits replace Range (mathematics) (a redirect to a disambig page) with plain english word -- not being used in a technical sense here Next edit →
Line 7: ==Application== A perfect hash function with values in a limited [[range ~~(mathematics)\|range]]~~ can be used for efficient lookup operations, by placing keys from {{mvar\|S}} (or other associated values) in a [[lookup table]] indexed by the output of the function. One can then test whether a key is present in {{mvar\|S}}, or look up a value associated with that key, by looking for it at its cell of the table. Each such lookup takes [[constant time]] in the [[Worst-case complexity\|worst case]].<ref name="inventor"/> ==Construction== Line 67: ===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'' − 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\|F}} is a minimal perfect hash function if and only if {{math\|1=''F''(''j'') = ''F''(''k'')}} implies {{math\|1=''j'' = ''k''}} ([[injectivity]]) and there exists an integer {{mvar\|a}} such that the range of {{mvar\|F}} is {{math\|1=''a''..''a'' + {{!}}''S''{{!}} − 1}}. It has been proven that a general purpose minimal perfect hash scheme requires at least 1.44 bits/key.<ref name="CHD">{{citation \| last1 = Belazzougui \| first1 = Djamal \| last2 = Botelho \| first2 = Fabiano C.

Perfect hash function: Difference between revisions