[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>.

[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>.