Tim Peters <t...@python.org> added the comment:
Note that you can contrive similar cases with positive hash codes too. For example, force both hash codes to 2**60 - 2. The salient points are that 0 * 5 is congruent to 0 mod any power of 2, while -2 * 5 = -10 is congruent to -2 mod 8, so they're fixed points of the `i = 5*i + 1 + perturb` iteration _given that_ perturb is congruent to -1 (so cancels out the +1) until enough shifts have been done to get 0 bits into the lowermost bits retained by the mask (in which case perturb is no longer congruent to -1, and so no longer cancels out the +1). Since PERTURB_SHIFT is 5, on a 64-bit box it can take 13 shifts before `perturb` is entirely cleared. As internal comments note, it's only _then_ that the recurrence is guaranteed to visit every slot exactly once. I don't care. It would be nice if it could guarantee to visit every slot exactly once from the start - which it _would_ do if we didn't use `perturb` at all. But using `perturb` is extremely valuable for avoiding quadratic-time behavior in large tables in bad real cases. The drawback is that it can stick in a fixed point for 13 shifts on a 64-bit box (7 shifts on a 32-bit box). But that's the worst it can do, and it's rare. I don't believe it's worth a single cycle, overall, to avoid it. ---------- nosy: +tim.peters _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue38105> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
