perfect-hash-generator
Version 0.2.0.4 revision 0 uploaded by kostmo.
Package meta
- Synopsis
- Perfect minimal hashing implementation in native Haskell
- Description
A perfect hash function for a set
Sis a hash function that maps distinct elements inSto a set of integers, with no collisions. A minimal perfect hash function is a perfect hash function that mapsnkeys tonconsecutive integers, e.g. the numbers from0ton-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.
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) tuples = [ (1000, 1) , (5555, 2) , (9876, 3) ] lookup_table = createMinimalPerfectHash tuplesGeneration of C code based on the arrays in
lookup_tableis 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-demoandhash-perfectly-ints-demo, as well as the test suite, for working examples.$ stack build $ stack exec hash-perfectly-strings-demo- Author
- Karl Ostmo <kostmo@gmail.com>
- Bug reports
- https://github.com/kostmo/perfect-hash-generator/issues
- Category
- Data Structures, Embedded
- Copyright
- n/a
- Homepage
- https://github.com/kostmo/perfect-hash-generator#readme
- Maintainer
- Karl Ostmo <kostmo@gmail.com>
- Package URL
- n/a
- Stability
- n/a