[Haskell-cafe] Very imperfect hash function

John Lato jwlato at gmail.com
Fri Jan 29 06:52:08 EST 2010

> From: Hans Aberg <haberg at math.su.se>
> 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.

The minimal perfect hash function looks like the real algorithmic
solution, but I would just use Data.IntMap for this.


More information about the Haskell-Cafe mailing list