[Haskell-cafe] Very imperfect hash function
haberg at math.su.se
Fri Jan 29 10:26:18 EST 2010
On 29 Jan 2010, at 15:57, John Lato wrote:
>> 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.
> I just want to be sure I understand this. For this plan, you aren't
> intending to use a perfect hash function at all, correct?
Yes, this is another idea. In a hash table, it is not important to
have different indices, only that that table entries are as flat as
> Are you
> basically just suggesting to stick everything in an array with the key
> as an index?
You still need to fold the key values onto some interval.
> Or are you suggesting an actual hash table?
The hash function folds the keys onto an interval. Since you have Int
values k, you might just use a mod k n function for that.
> If it's the
> latter, I'm not certain where the array fits into the picture. I'm
> pretty sure I'm missing something here.
There is a module Data.HashTable. The array is just to make lookup
fast. Like in:
ST s (STArray s HashKey (Map Key Value))
> In either case, I don't think this would be as good as what I thought
> was your original suggestion, i.e. using a minimal perfect hash
> function mphf that hashes keys to a value 0..v-1. With v=number of
> values, valArr = array of all values, then
> lookup k = valArr ! mphf k
Right, but you may have to avoid implementing the perfect hash
function by yourself, if it is only available in C. :-) There is a
More information about the Haskell-Cafe