On 28 September 2004 13:37, Marcin 'Qrczak' Kowalczyk wrote:

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