[m-dev.] hash tables in standard library

[Ralph Becket]

Jonathan Morgan, Friday, 15 August 2008:
> 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.

My understanding is that Python uses hash tables as method tables, from
which you never delete anything.  Does it also use them for associative
arrays?
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------