On Tue, Mar 18, 2014 at 8:20 AM, Steven D'Aprano <steve+comp.lang.pyt...@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 -- https://mail.python.org/mailman/listinfo/python-list
