perfect-hash-generator: Perfect minimal hashing implementation in native Haskell

This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.


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 lookups also perform reasonably well for Haskell applications, it hasn't been benchmarked thorougly with respect to other data structures.

This implementation was adapted from Steve Hanov's Blog.


The library is written generically to hash both strings and raw integers. Integers should be wrapped in the Atom newtype:

import Data.PerfectHash.Construction (createMinimalPerfectHash)

tuples = [
   (Atom 1000, 1)
 , (Atom 5555, 2)
 , (Atom 9876, 3)

lookup_table = createMinimalPerfectHash 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.

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


Only integer keys of at most 32-bits have been demonstrated to work properly. Since the hash function masks to 32 bits, colliding 64-bit integers can hang the lookup table construction.


Change logNone available
Dependenciesbase (>=4.5 && <=4.10), containers, data-ordlist, directory, filepath, hashable, optparse-applicative, perfect-hash-generator, random, unordered-containers, vector [details]
AuthorKarl Ostmo <>
MaintainerKarl Ostmo <>
CategoryData Structures, Embedded
Home page
Bug tracker
Source repositoryhead: git clone
Executableshash-perfectly-strings-demo, hash-perfectly-ints-demo
UploadedMon Nov 6 03:28:25 UTC 2017 by kostmo




Maintainers' corner

For package maintainers and hackage trustees