[Haskell-cafe] Very imperfect hash function

[Hans Aberg]

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