[Haskell-cafe] Very imperfect hash function

Hans Aberg haberg at math.su.se
Fri Jan 29 07:46:42 EST 2010

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


More information about the Haskell-Cafe mailing list