CODEWITHSUNDEEP
data-structureshaskellhashtable
John F. Miller
John F. Miller

Reputation: 27227

A Haskell hash implementation that does not live in the IO monad

I am looking for a data structure that works a bit like Data.HashTable but that is not encumbered by the IO monad. At the moment, I am using [(key,val)]. I would like a structure that is O(log n) where n is the number of key value pairs.

The structure gets built infrequently compared to how often it must be read, and when it is built, I have all the key value pairs available at the same time. The keys are Strings if that makes a difference.

It would also be nice to know at what size it is worth moving away from [(key,val)].

Upvotes: 6

Views: 1466

Answers (2)

augustss
augustss

Reputation: 23014

If you have all the key-value pairs up front you might want to consider a perfect hash function.

Benchmarking will tell you when to switch from a simple list.

Upvotes: 3

Don Stewart
Don Stewart

Reputation: 137987

You might consider:

or alternatively,

The former is the standard container for storing and looking up elements by keys in Haskell. The latter is a new library specifically optimized for hashing keys.

Johan Tibell's recent talk, Faster persistent data structures through hashing gives an overview, while Milan Straka's recent Haskell Symposium paper specifically outlines the Data.Map structure and the hashmap package.

Upvotes: 12

Related Questions