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

Groups > comp.lang.python > #93950 > unrolled thread

Re: How does a dictionary work exactly?

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  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

#93950 — Re: How does a dictionary work exactly?

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

[toc] | [next] | [standalone]

#94012

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.

[toc] | [prev] | [next] | [standalone]

#94014

On Fri, Jul 17, 2015 at 9:32 AM, Ned Batchelder <ned@nedbatchelder.com> wrote:
> 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.

No, I was working a) from memory, and b) not looking at the
implementation, which I last did a long, long time ago...

Skip

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web