A perfect hash function for a set `S`

is a hash function that maps distinct elements in `S`

to a set of integers, with **no collisions**. A minimal perfect hash function is a perfect hash function that maps `n`

keys to `n`

**consecutive** integers, e.g. the numbers from `0`

to `n-1`

.

In contrast with the PerfectHash package, which is a binding to a C-based library, this package is a fully-native Haskell implementation.

It is intended primarily for generating C code for embedded applications (compare to `gperf`

). The output of this tool is a pair of arrays that can be included in generated C code for **allocation-free hash tables**.

Though conceivably this data structure could be used directly in Haskell applications as a read-only hash table, it is not recommened, as lookups are about 10x slower than HashMap.

This implementation was adapted from Steve Hanov's Blog.

# Usage

The library is written generically to hash both strings and raw integers according to the FNV-1a algorithm. Integers are split by octets before hashing.

```
import Data.PerfectHash.Construction (createMinimalPerfectHash)
import qualified Data.Map as Map
tuples = [
(1000, 1)
, (5555, 2)
, (9876, 3)
]
lookup_table = createMinimalPerfectHash $ Map.fromList tuples
```

Generation of C code based on the arrays in `lookup_table`

is left as an exercise to the reader. Algorithm documentation in the `Data.PerfectHash.Hashing`

and `Data.PerfectHash.Lookup`

modules will be helpful.

# Demo

See the `hash-perfectly-strings-demo`

and `hash-perfectly-ints-demo`

, as well as the test suite, for working examples.

```
$ stack build
$ stack exec hash-perfectly-strings-demo
```