Re: [Haskell-cafe] Very imperfect hash function

On 28 Jan 2010, at 20:07, Steve Schafer wrote:

The data are currently in a large lookup table. To save space, I'd like to convert that into a sort of hash function:

hash :: key -> value

My question is this: Is there any kind of generic approach that can make use of the knowledge about the internal redundancy of the keys to come up with an efficient function?

There are minimal perfect hash functions; there are some libraries mentioned here, though they are not in Haskell code: http://en.wikipedia.org/wiki/Perfect_hash_function This is suitable when you do a lot of lookups with few key updates. An alternative might be Data.Map, where lookups have time complexity O(log n), n = size of map. Hans