Data.HashTable and duplicate keys

Marcin 'Qrczak' Kowalczyk qrczak at knm.org.pl
Tue Sep 28 08:37:18 EDT 2004


"Simon Marlow" <simonmar at microsoft.com> writes:

> Making insert do delete+insert is pretty inefficient if you know that
> the key isn't in the table.  Providing update (==delete+insert) seems a
> reasonable solution, no?

This depends whether the implementation uses buckets for elements with
the same hash modulo size (like in OCaml), or stores elements directly
in the array, with some conflict resolution strategy (like in Python).

I don't know which scheme is more efficient in general. Buckets are
easier to implement if deletion is to be supported, but a flat array
may have a faster optimistic case. Their memory overhead is similar
because a flat array can't be as dense as an array of buckets.

-- 
   __("<         Marcin Kowalczyk
   \__/       qrczak at knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/


More information about the Libraries mailing list