[Haskell-cafe] Very imperfect hash function

Hans Aberg haberg at math.su.se
Thu Jan 28 14:41:20 EST 2010

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:

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.


More information about the Haskell-Cafe mailing list