[Tim]
I know the theoretical number of probes for dicts, but not for sets anymore. The latter use a mix of probe strategies now, "randomish" jumps (same as for dicts) but also purely linear ("up by 1") probing to try to exploit L1 cache.
It's not _apparent_ to me that the mix actually helps ;-) I just trust that Raymond timed stuff until he was sure it does.
To illustrate, I contrived a case where the set optimizations clearly pay off. Output (3.8.1, Win 10 Pro, quad core box with plenty of RAM): 11184810 nice keys dict build 0.54 dict iter 0.07 dict lookup 0.81 set build 0.54 set iter 0.08 set lookup 0.82 11184810 nasty keys dict build 23.32 dict iter 0.09 dict lookup 13.26 set build 9.79 set iter 0.28 set lookup 8.46 I didn't make heroic efforts to keep the machine quiet, and there's substantial variation across runs. For example, there's no real difference beteen "0.07" and "0.08". Some things to note: - The "nice" keys act much the same regardless of whether dict or set. Dicts have an advantage for iteration "in theory" in the absence of deletions because there are no "holes" in the area storing the hash+key+value records. But for these specific keys, the same is true of sets: the initial hash probes are at indices 0, 1, 2, ..., len(the_set)-1, and there are no holes in its hash+key records either (all the empty slots are together "at the right end"). - Sets get a lot of value out of their fancier probe sequence for the nasty keys. There are lots of collisions, and sets can much more often resolve them from L1 cache. Better than a factor of 2 for build time is nothing to sneeze at. - Iteration for sets is substantially slower in this case, for two reasons: (1) sets _do_ have holes for this collection of keys; and, (2) while I don't think it's documented, the maximum load factor for sets is lower than for dicts, and 11184810 was picked to give the maximum load factor for a dict with 2**24 slots. The set in this case has twice as many slots as the dict, and all the extras are empty slots that iteration has to skip over. - I don't have a theory for why dict build time is _so_ much higher than dict lookup time for the nasty keys. - If you don't know a lot about how these things are implemented, just about everything is baffling ;-) Integer keys are important in practice, but things about how modern dicts are implemented were _driven_ by opportunities to exploit properties of the mostly-trivial int hash function. For "general" timing, it's better to use string keys, whose hash codes are "pretty randomish" (but can vary across runs). When using int keys, it's really easy to _end up_ measuring happy behaviors _specific_ to int keys. Code: from time import perf_counter as now import sys from collections import deque def disp(text, f): print(f"{text:20s} {f:5.2f}") M = sys.hash_info.modulus targetlen = 2**24 * 2 // 3 # highest load factor for dict hc = 1 badkeys = [] while len(badkeys) < targetlen: # add no more than 100 ints with hash code `hc` toadd = min(100, targetlen - len(badkeys)) badkeys.extend(hc + i * M for i in range(toadd)) hc += 713 # more than less arbitrary goodkeys = list(range(targetlen)) for tag, keys in ("nice", goodkeys), ("nasty", badkeys): print() print(len(keys), tag, "keys") for thetype, builder in ("dict", dict.fromkeys), ("set", set): s = now() d = builder(keys) f = now() disp(thetype + " build", f-s) s = now() deque(d, maxlen=0) f = now() disp(thetype + " iter", f-s) s = now() for k in keys: assert k in d f = now() disp(thetype + " lookup", f-s) del d