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