tree d6a2ae54e7b853d0e618909a96784c1b749ff19e
parent a661f4531e2c8d189dc4a6c22ce74d2bfd18cbcd
author Raymond Hettinger <python@rcn.com> 1378117401 -0700
committer Raymond Hettinger <python@rcn.com> 1378117401 -0700
HG:rename-source hg

Instead of XORed indicies, switch to a hybrid of linear probing and open addressing.

Modern processors tend to make consecutive memory accesses cheaper than
random probes into memory.

Small sets can fit into L1 cache, so they get less benefit.  But they do
come out ahead because the consecutive probes don't probe the same key
more than once and because the randomization step occurs less frequently
(or not at all).

For the open addressing step, putting the perturb shift before the index
calculation gets the upper bits into play sooner.