[Python-Dev] {}.popitem() (was Re: {}.first[key,value,item] ...)

[Tim Peters]

[Tim]
> Well, anyone can play.  When keys collide, what we need is a
> function f(i) such that repeating
>     i = f(i)
> visits every int in (0, 2**N) exactly once before setting i back to its
> initial value, for a fixed N and where the first i is in (0, 2**N).

[Moshe Zadka]
> OK, maybe this is me being *real* stupid, but why? Why not [0, 2**n)?
> Did 0 harm you in your childhood, and you're trying to get
> back? <0 wink>.

We don't need f at all unless we've already determined there's a collision
at some index h.  The i sequence is used to offset h (mod 2**N).  An
increment of 0 would waste time (h+0 == h, but we've already done a full
compare on the h'th table entry and already determined it wasn't equal to
what we're looking for).

IOW, there are only 2**N-1 slots still of interest by the time f is needed.

> If we had an affine operation, instead of a linear one, we could have
> [0, 2**n). I won't repeat the proof here but changing
>
> def f(i):
>     i <<= 1
>     i^=1 # This is the line I added
>     if i >= 2**N:
>         i ^= MAGIC_CONSTANT_DEPENDING_ON_N
>     return i
>
> Makes you waltz all over [0, 2**n) if the original made you comple
> (0, 2**n).

But, Moshe!  The proof would have been the most interesting part <wink>.