Lists implemented as integer-hashed Dictionaries?

Terry Reedy tjreedy at udel.edu
Sat Feb 7 08:31:20 CET 2009


er wrote:
> 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 mailing list