Lists implemented as integer-hashed Dictionaries?
tjreedy at udel.edu
Sat Feb 7 08:31:20 CET 2009
> Somebody much more intelligent than I said today that someone told him
> that Python lists are just dictionaries with lists hashed by integers.
Abstractly, which is to say, behaviorally, a Python list is a sequence
class as defined under Built-in Types in the Library manual.
Dictionaries are a mapping class. The two categories have different
methods. So at this level, the claim is nonsensical, wrong by
definition. A list *must* have it n entries indexed from 0 to n-1 and
dicts do not and could not enforce such an invariant.
Concretely, an implementation could do as claimed under the covers, but
CPython and I suspect all the other implementations actually use
extensible arrays. People *do* use dicts for sparse arrays, but then
they are *not* sequences.
Good for you for asking here.
Terry Jan Reedy
More information about the Python-list