[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>.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4