[Haskell-cafe] Very imperfect hash function

[Hans Aberg]

On 29 Jan 2010, at 12:52, John Lato wrote:

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

That looks interesting too. Yet another idea: use arrays
   http://haskell.org/haskellwiki/Arrays
Then build a hash table, say just taking mod k n, and have values in  
some lookup map. If n > set of keys, average time complexity is O(1),  
and arrays should be very fast.

   Hans