Unexpected comparisons in dict lookup

[Ian Kelly]

On Tue, Mar 18, 2014 at 8:20 AM, Steven D'Aprano
<steve+comp.lang.python at 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