Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #94012

Re: How does a dictionary work exactly?

Show all headers | View raw

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@gmail.com
> <yoursurrogategod@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.

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Re: How does a dictionary work exactly? Skip Montanaro <skip.montanaro@gmail.com> - 2015-07-16 13:58 -0500
  Re: How does a dictionary work exactly? Ned Batchelder <ned@nedbatchelder.com> - 2015-07-17 07:32 -0700
    Re: How does a dictionary work exactly? Skip Montanaro <skip.montanaro@gmail.com> - 2015-07-17 10:58 -0500

csiph-web