Some explanations and cautions. An advantage of sticking with pure Python instead of C is that spare moments are devoted to investigating the problem instead of thrashing with micro-optimizations ;-) Why does the current scheme suffer for small tables? With hindsight it's pretty obvious: it can visit table slots more than once (the other schemes cannot), and while the odds of that happening are tiny in large tables, they're high for small tables. For example, in a 3-bit table (8 slots), suppose the initial index is 1, and there's a collision. The 5*i+1 recurrence _would_ visit slot 6 next, but we also shift in 5 new bits and add them. If those bits are "random", there's a 1-in-8 chance that we'll visit index 1 _again_. If we don't, and have another collision, shifting in the next 5 bits has a 2-in-8 chance of repeating one of the two slots we already visited. And so on. Here using the `str(i)` generator (which yields random-ish hash codes): """ bits 3 nslots 8 dlen 5 alpha 0.62 # built 20,000 ... prober current found min 1:74.80% max 15 mean 1.42 fail min 1:37.62% max 18 mean 2.66 """ So despite that only 5 slots are filled, in at least one case it took 15 probes to find an existing key, and 18 probes to realize a key was missing. In the other schemes, it takes at most 5 probes for success and 6 probes for failure. This is worse for 64-bit hash codes than for 32-bit ones, because we can loop around twice as often before `perturb` permanently becomes 0 (at which point the pure 5*i+1 recurrence visits each slot at most once). The larger the table, the less likely a repeat due to `perturb` becomes. For example, suppose we have an 8-bit table and again visit index 1 first. We may visit any index in range(6, 6+32) next (depending on the 5 fresh bits shifted in), but repeating 1 is _not_ a possibility. Why do the double hashing methods do better for the `i << 12` generator? In any case where the hash codes have "a lot" of trailing bits in common, they all map to the same table index at first, and the probe sequence remains the same for all until the loop shifts `perturb` far enough right that the rightmost differing bits finally show up in the addition. In the double hashing methods, _all_ the bits of the hash code affect the value of `inc` computed before the loop starts, so they have a good chance of differing already on the second probe. This is again potentially worse for the current scheme with 64-bit hash codes, since the sheer number of common trailing bits _can_ be up to 63. However, the double-hashing schemes have pathological cases too, that the current scheme avoids. The first I tried was a `yield i * 1023` generator. These are spectacularly _good_ values for all schemes except `uniform` for successful searches, because i*1023 = j*1023 (mod 2**k) implies i=j (mod 2**k) That is, there are no first-probe collisions at all across a contiguous range of `i` with no more than 2**k values. But the `double` scheme for a 10-bit table degenerates to linear probing in this case, because inc = (h % mask) | 1 # force it odd is always 1 when h is divisible by 1023 (== mask for a 10-bit table). This is terrible for a failing search; e.g., for a 20-bit table (note that 2**20-1 is divisible by 1023): """ bits 20 nslots 1,048,576 dlen 699,050 alpha 0.67 # built 1 theoretical avg probes for uniform hashing when found 1.65 not found 3.00 ... prober current found min 1:100.00% max 1 mean 1.00 fail min 1:33.33% max 34 mean 3.04 prober double found min 1:100.00% max 1 mean 1.00 fail min 1:33.33% max 699049 mean 1867.51 prober dfib found min 1:100.00% max 1 mean 1.00 fail min 1:33.33% max 427625 mean 8.09 prober uniform found min 1:66.65% max 24 mean 1.65 fail min 1:33.35% max 35 mean 3.00 """ While that's a failing-search disaster for `double`, it's also bad for `dfib` (& I don't have a slick explanation for that). So where does that leave us? I don't know. All schemes have good & bad points ;-) I haven't yet thought of a cheap way to compute an `inc` for double-hashing that isn't vulnerable to bad behavior for _some_ easily constructed set of int keys. If you forget "cheap", it's easy; e.g., random.seed(h) inc = random.choice(range(1, mask + 1, 2)) Regardless, I'll attach the current version of the code.