Data.PerfectHash.Lookup

Note that what is referred to as a "nonce" in this library may be better known as "salt".

Documentation

data LookupTable a

Inputs for the lookup function.

There are two arrays used in successive stages of the lookup. In this implementation, both arrays are the same length.

Constructors

LookupTable

Fields

• nonces :: Vector Int

  This is the intermediate lookup table.

  In the lookup process, the key's hash is computed first with a nonce of zero to obtain an index into this array.

  If the value at this index is negative, it is (after negating and subtracting one) a direct index into the values array. Otherwise, the value shall be used as a nonce in a second application of the hashing function to compute the index into the values array.

  See the documentation of lookup for details.

• values :: Vector a

  An array of values of arbitrary type.

  The objective of the perfect hash is to efficiently retrieve an index into this array, given the key associated with the value at that index.

lookup

Arguments

:: (ToHashableChunks a, Unbox b)

=> LookupTable b

-> a

key

-> b

value

For embedded applications, this function would usually be re-implemented in C code.

Algorithm description

The lookup procedure is three steps:

1. Compute the hash (with a nonce of zero) of the "key", modulo the length of the values array.

2. Use the resulting value as an index into the nonces array. The value found there represents either a direct index into the values array or a nonce for a second round of hashing.

   • If negative, it is the former. Negate it (to obtain a positive value) and subtract one to obtain the actual index.
   • Otherwise, re-compute the hash of the key, using this value instead of zero as the nonce. Again, compute the modulus with respect to the length of the values array.
3. Use the result of (2) as the index into the values array.