On 29 Jan 2010, at 15:57, John Lato wrote:
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.
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
possible.
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
FFI, though.
Hans
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
