[m-dev.] hash tables in standard library

[Ralph Becket]

Jonathan Morgan, Friday, 15 August 2008:
> 
> Or possibly (depending on how you implement it) just resize the hash
> table.  There will be different tradeoffs for different
> implementations, and I'm sure all of these ideas have been tried
> before (I know in 253 using a balanced tree or some other log n search
> mechanism was suggested as one way to prevent linear searches).  I'm
> not sure what it is best for a standard library to do - I just know if
> I were designing a generic hash table I would use separate chaining,
> because it seems more logical than open addressing to me.  The Python
> implementers obviously think differently, and their dictionary is
> pretty fast and has been very carefully tuned to suit their usage
> pattern.

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.

I think for simplicity and robustness I'd be inclined to use single
hashing now, however.

-- Ralph
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------