[Haskell-cafe] Boxed Mutable Arrays

[Richard Kelsall]

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.