On Fri, Jan 29, 2010 at 12:46 PM, Hans Aberg
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.
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? Are you basically just suggesting to stick everything in an array with the key as an index? Or are you suggesting an actual hash table? 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. 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 Cheers, John