How does a dictionary work exactly?

[Skip Montanaro]

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