[m-dev.] hash tables in standard library

[Ralph Becket]

Zoltan Somogyi, Friday, 15 August 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.

Oh yes, I recognise that.  It only works assuming deletions are rare
events.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------