[m-dev.] hash tables in standard library

Zoltan Somogyi zs at csse.unimelb.edu.au
Fri Aug 15 16:20:54 AEST 2008


On 15-Aug-2008, Ralph Becket <rafe at csse.unimelb.edu.au> wrote:
> I did some benchmarking when I wrote the hash_table module and double
> hashing was definitely a bit faster.  I'm not sure how to gracefully
> handle deletes, other than to add a "deleted" bucket state to the
> existing "empty" and "occupied" states.

If you do that, then after a long sequence of additions and deletions,
you could end up with a hash table in which *every single item* in the
table requires a long search to find it, even though it could be back
in its home bucket.

Zoltan.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at csse.unimelb.edu.au
Administrative Queries: owner-mercury-developers at csse.unimelb.edu.au
Subscriptions:          mercury-developers-request at csse.unimelb.edu.au
--------------------------------------------------------------------------



More information about the developers mailing list