How does a dictionary work exactly?

[Ned Batchelder]

On Thursday, July 16, 2015 at 2:59:02 PM UTC-4, Skip Montanaro wrote:
> On Thu, Jul 16, 2015 at 1:36 PM, yoursurrogategod at gmail.com
> <yoursurrogategod at gmail.com> wrote:
> > If I understand correctly, lookup would not be a constant, yes?
> 
> On the contrary, that's what you desire, nearly constant time
> execution. To the greatest extent possible, you want the linked lists
> to be of length zero or one. Part of the magic is in figuring out good
> places to expand the size of the hash array. You don't want it to grow
> too big, but you still want most linked lists to be very short. The
> resize operation isn't done too often because it itself is expensive.
> I believe Python dicts start out with an overly large initial hash
> array (again, dredging up old memories of threads on python-dev) as an
> optimization to avoid lots of early resize operations.
> 
> Skip

Maybe people are reading a different implementation than I am.  Python's
dict object doesn't use linked lists to deal with hash collisions, it probes
other slots instead.

Brandon Rhodes did a great talk about how dicts work:
http://pyvideo.org/video/276/the-mighty-dictionary-55

BTW: The Python 3 implementation is more complicated than in Python 2, I
think to deal with sharing keys among dictionaries that have the same set
of keys.

--Ned.