[Haskell-cafe] Very imperfect hash function

[John Lato]

> 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.

Cheers,
John