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

Groups > comp.lang.python > #68514

Re: Unexpected comparisons in dict lookup

Show all headers | View raw

On Tue, Mar 18, 2014 at 8:20 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> I stumbled across this unexpected behaviour with Python 2.7 and 3.3. When
> you look up a key in a dict, the key is sometimes compared against other
> keys twice instead of just once.

>From what I can see in the code, it adds a perturbation based on the
upper bits of the hash value to the probing scheme, to reduce
collisions for keys with unequal hashes.  On the downside, this
cancels the guarantee that each bucket can only be checked at most
once.  The perturbation gradually shifts to 0 after a few iterations,
so every bucket can still be reached within O(n) iterations.

See the comments starting at "Major subtleties ahead":
http://hg.python.org/cpython/file/f8b40d33e45d/Objects/dictobject.c#l106

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

Thread

Unexpected comparisons in dict lookup Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-18 14:20 +0000
  Re: Unexpected comparisons in dict lookup Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-18 14:15 -0600

csiph-web