[m-dev.] hash tables in standard library

[Jonathan Morgan]

On Wed, Aug 13, 2008 at 1:27 PM, Zoltan Somogyi <zs at csse.unimelb.edu.au> wrote:
> On 07-Aug-2008, Julien Fischer <juliensf at csse.unimelb.edu.au> wrote:
>> The two hash table modules in the standard library  (hash_table.m and
>> version_hash_table.m) both have broken delete operations.  PeterW
>> has suggested that we replacing the existing implementation with
>> one that uses separate chaining; I agree with him.
>>
>> (See the notes for bug #68 for details)
>
> No. In fact, (on an unrelated note) I always thought the time we spent in
> 433-253 on describing open addressing versions of hashing to be time
> ill-spent, since I have always thought that in real life, only chaining
> is practical.

Python is a language which relies very heavily on dictionaries, and
its dictionary uses an open addressing hashing scheme.  This is not
only practical, but used by hundreds of thousands of people.

I personally would almost always use separate chaining, but apparently
the open addressing scheme used has better memory usage and better
locality, making it ideal for Python where the dictionary must be
extremely efficient.

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