Brad Larsen wrote:
I have considered using Data.IntMap to implement a sort of faux hash
table, e.g., introduce a Hashable class, and then use an IntMap to
lists of Hashable. The result would be a pure, persistent ``hash
table''. In such a case, however, lookup/insert/delete operations
would have average complexity logarithmic in the number of buckets.
I'll throw in an idea that has been nagging me about hash tables.
You could have a list of hash tables of increasing size. On an insert
collision in a smaller table all the entries get put into the next one
up. For a lookup you would have to check all the tables until you find
the hash.
e.g.
With three hash table in the list of these example sizes.
Table size 2^2 = 2 probable entries before collision.
2^4 = 4
2^6 = 8
h..h
...h.....h.h...h
h......h.......h....h...........h......h.h..........h...........
I expect if it's any good it has already been done.
Richard.
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
