[m-dev.] hash tables in standard library

[Zoltan Somogyi]

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).

This issue DOES affect method tables and environments (tables mapping symbols
to information about them), but only for Python programs with bad style.

Zoltan.

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