[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:
> > My understanding is that Python uses hash tables as method tables, from
> > which you never delete anything.
> 
> That is one limitation of open addressing. The other is that as the
> hash table gets closer and closer to full, the performance falls off a cliff.
> With chaining, there is no such effect, and a table with N slots can in fact
> contain more than N items. As the ratio between the number of items
> and the number of slots increases beyond one, the performance comes to
> be dominated more and more by the linear search of the chains, but
> even this can be fixed by using expandable hash tables (as in e.g.
> linear hashing).

I guess one could use a map rather than a list for each bucket in order
to limit worst case behaviour.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------