{"history":[],"article":{"id":"7977b88c-46cf-4e26-a9b8-a393d88d918e","title":"Perfect hash function","slug":"perfect-hash-function","content":":::summary\n:::\n\n# \nIn [computer science](https://bliptext.com/articles/computer-science), a **perfect [hash function](https://bliptext.com/articles/hash-function)** h for a set S is a [hash function](https://bliptext.com/articles/hash-function) that maps distinct elements in S to a set of m integers, with no [collisions](https://bliptext.com/articles/hash-collision).\nIn mathematical terms, it is an [injective function](https://bliptext.com/articles/injective-function).\nPerfect hash functions may be used to implement a [lookup table](https://bliptext.com/articles/lookup-table) with constant worst-case access time.\nA perfect [hash function](https://bliptext.com/articles/hash-function) can, as any [hash function](https://bliptext.com/articles/hash-function), be used to implement [hash tables](https://bliptext.com/articles/hash-table), with the advantage that no [collision resolution](https://bliptext.com/articles/hash-table) has to be implemented.\nIn addition, if the keys are not in the data and if it is known that queried keys will be valid, then the keys do not need to be stored in the lookup table, saving space.\nDisadvantages of perfect hash functions are that S needs to be known for the construction of the perfect hash function.\nNon-dynamic perfect hash functions need to be re-constructed if S changes.\nFor frequently changing S [dynamic perfect hash functions](https://bliptext.com/articles/dynamic-perfect-hashing) may be used at the cost of additional space.\nThe space requirement to store the perfect hash function is in\nO(n)\nwhere\nn\nis the number of keys in the structure.\nThe important performance parameters for perfect hash functions are the evaluation time, which should be constant, the construction time, and the representation size.\n# [A perfect hash function for the four names shown | upload.wikimedia.org/wikipedia/commons/7/71/Hash///table///4///1///1///0///0///0///0///LL.svg]\n# [A minimal perfect hash function for the four names shown | upload.wikimedia.org/wikipedia/commons/2/2e/Hash///table///4///1///0///0///0///0///0///LL.svg]\n\n# Application\nA perfect hash function with values in a limited range can be used for efficient lookup operations, by placing keys from S (or other associated values) in a [lookup table](https://bliptext.com/articles/lookup-table) indexed by the output of the function.\nOne can then test whether a key is present in S, or look up a value associated with that key, by looking for it at its cell of the table.\nEach such lookup takes [constant time](https://bliptext.com/articles/constant-time) in the [worst case](https://bliptext.com/articles/worst-case-complexity).\nWith perfect hashing, the associated data can be read or written with a single access to the table.\n\n# Performance of perfect hash functions\nThe important performance parameters for perfect hashing are the representation size, the evaluation time, the construction time, and additionally the range requirement \\frac{m}{n} (average number of buckets per key in the hash table).\nThe evaluation time can be as fast as\nO(1)\n, which is optimal.\nThe construction time needs to be at least\nO(n)\n, because each element in S needs to be considered, and S contains n elements.\nThis lower bound can be achieved in practice.\nThe lower bound for the representation size depends on m and n. Let\nand h a perfect hash function.\nA good approximation for the lower bound is Bits per element.\nFor minimal perfect hashing,\nε = 0\n, the lower bound is\nlog e ≈ 1.44\nbits per element.\n\n# Construction\nA perfect hash function for a specific set S that can be evaluated in constant time, and with values in a small range, can be found by a [randomized algorithm](https://bliptext.com/articles/randomized-algorithm) in a number of operations that is proportional to the size of S. The original construction of uses a two-level scheme to map a set S of n elements to a range of\nO(n)\nindices, and then map each index to a range of hash values.\nThe first level of their construction chooses a large prime p (larger than the size of the [universe](https://bliptext.com/articles/universe-mathematics) from which S is drawn), and a parameter k, and maps each element x of S to the index\nIf k is chosen randomly, this step is likely to have collisions, but the number of elements ni that are simultaneously mapped to the same index i is likely to be small.\nThe second level of their construction assigns disjoint ranges of\nO(ni2)\nintegers to each index i. It uses a second set of linear modular functions, one for each index i, to map each member x of S into the range associated with\ng(x)\n.\nAs show, there exists a choice of the parameter k such that the sum of the lengths of the ranges for the n different values of\ng(x)\nis\nO(n)\n. Additionally, for each value of\ng(x)\n, there exists a linear modular function that maps the corresponding subset of S into the range associated with that value.\nBoth k, and the second-level functions for each value of\ng(x)\n, can be found in [polynomial time](https://bliptext.com/articles/polynomial-time) by choosing values randomly until finding one that works.\nThe hash function itself requires storage space\nO(n)\nto store k, p, and all of the second-level linear modular functions.\nComputing the hash value of a given key x may be performed in constant time by computing\ng(x)\n, looking up the second-level function associated with\ng(x)\n, and applying this function to x. A modified version of this two-level scheme with a larger number of values at the top level can be used to construct a perfect hash function that maps S into a smaller range of length\nn + o(n)\n.\nA more recent method for constructing a perfect hash function is described by as \"hash, displace, and compress\".\nHere a first-level hash function g is also used to map elements onto a range of r integers.\nAn element\nx ∈ S\nis stored in the Bucket Bg(x).\nThen, in descending order of size, each bucket's elements are hashed by a hash function of a sequence of independent fully random hash functions\n(Φ1, Φ2, Φ3, ...)\n, starting with\nΦ1\n. 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.\nIf not, the next hash function in the sequence is tested.\nTo evaluate the perfect hash function\nh(x)\none only has to save the mapping σ of the bucket index\ng(x)\nonto the correct hash function in the sequence, resulting in\n.\nFinally, to reduce the representation size, the (\nσ(i))0 ≤ i < r\nare compressed into a form that still allows the evaluation in\nO(1)\n.\nThis approach needs linear time in n for construction, and constant evaluation time.\nThe representation size is in\nO(n)\n, and depends on the achieved range.\nFor example, with\nachieved 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.\nThe space lower bound in this scenario is 0.88 bits/key.\n\n## Pseudocode\n**algorithm** hash, d**is**place, and compress **is**\n(1) Split S into buckets\nBi := g−1({i})∩S,0 ≤ i < r\n(2) Sort buckets Bi in falling order according to size |Bi|\n(3) Initialize array T[0...m-1] with 0's (4) **for all** i ∈[r], in the order from (2), **do**\n(5) **for** l ← 1,2,...\n(6) **repeat** forming Ki ← {{{math|Φ}}{{sub|l}}(x)|x ∈ Bi}\n(6) **until** |Ki|=|Bi| **and** Ki∩{j|T[j]=1}= ∅\n(7) ****let**** σ(i):= the successful l (8) **for all** j ∈ Ki ****let**** T[j]:= 1\n(9) Transform (σi)0≤i

History