[Python-Dev] PyBench DictCreation (was Re: Performance compares)

[Neil Schemenauer]

Guido van Rossum wrote:
> What's an association table?

A table of keys and values.  Values are looked up by looping over
the table comparing each key until the correct one is found (ie.
its O(n) where n is the size of the table).  For Python, the cost
of doing compares probably outweighs the cost of doing the
hashing, even for small tables.

Its not clear to me though if it would be a win.  Assuming that
interned strings are the most common key, a assocation table with
four entries would take on average two pointer compares to look
up a value.

  Neil