[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
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
More information about the Haskell-Cafe
mailing list