Perfect hash function

A perfect hash function is a hash function which different elements of a finite and fixed set of keys on different elements of an image set mapping ( no collisions, injectivity ). From the injectivity follows an important advantage: on an element of a hash table can be accessed in the worst-case constant time.

The perfect hash function is called minimal perfect hash function, if, that is. This means that the image set of the function h equally powerful is the archetype amount. In practice, this reduces the memory requirements of the arrays which stores for each of the elements.

In contrast to non - perfect hashing (which is amortized access time required) provides the perfect hashing to access the elements in constant time in the worst case. This is achieved by setting the values ​​of s in a code of 0 to | T | - 1 are stored indexed array at the position h (s). In contrast to normal hashing each bucket ( bucket ) contains due to the injectivity of h ie exactly one element. Instead of you can to the elements then in constant time, so radically accelerated access. For this you pay with computing time by the hash function h to construct as well as space for storage of h

In practice, we investigated hash functions h with the following properties:

  • Construction of H in O (n) time, i.e. with increasing number of keys | S | h increases, the time to construct linear.
  • Evaluation of H, O (1 ), i.e. after construction of h can map a key in constant time on an index.
  • The hash function h requires as little memory.
  • The hash function h should be minimal perfect.

Common perfect hash functions currently work in time for the construction of h and require about 0.3 times as much memory as the key set S.

( Minimum ) perfect hash functions are then applied, in practice, if:

  • There is a fixed key set S of pairwise different keys, which are each associated with values ​​( in ever-changing sets of keys would be an ongoing redesign of h too time-consuming )
  • Is enough time available to construct the hash function h
  • On the values ​​of access is required in constant time
  • In constant time is to be asked whether a key exists in the hash
  • Additional memory for h exists

A method for constructing a perfect hash functions is hashed and displace.

  • Hash
Bucket (disambiguation)
642061
de