Data.HashTable and duplicate keys
simonmar at microsoft.com
Tue Sep 28 08:40:55 EDT 2004
On 28 September 2004 13:37, Marcin 'Qrczak' Kowalczyk wrote:
> "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.
The implementation uses buckets. I think buckets are also easier if the
hash tables are variable in size (which ours are).
I've now added
update :: HashTable key val -> key -> val -> IO Bool
to the interface, and improved the documentation.
More information about the Libraries