Data.HashTable and duplicate keys

Simon Marlow 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.

Cheers,
	Simon


More information about the Libraries mailing list