[Haskell-cafe] Boxed Mutable Arrays
r.kelsall at millstream.com
Wed Dec 16 14:42:48 EST 2009
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
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
I expect if it's any good it has already been done.
More information about the Haskell-Cafe