[Python-ideas] Reducing collisions in small dicts/sets

[Tim Peters]

Two bits of new info:  first, it's possible to get the performance of
"double" without division, at least via this way:

"""
# Double hashing using Fibonacci multiplication for the increment.  This
# does about as well as `double`, but doesn't require division.
#
# The multiplicative constant depends on the word size W, and is the
# nearest odd integer to 2**W/((1 + sqrt(5))/2).  So for a 64-bit box:
#
# >>> 2**64 / ((1 + decimal.getcontext().sqrt(5))/2)
# Decimal('11400714819323198485.95161059')
#
# For a 32-bit box, it's 2654435769.
#
# The result is the high-order `nbits` bits of the low-order W bits of
# the product.  In C, the "& M" part isn't needed (unsigned * in C
# returns only the low-order bits to begin with).
#
# Annoyance:  I don't think Python dicts store `nbits`, just 2**nbits.
def dfib(h, nbits, M=M64):
    mask = (1 << nbits) - 1
    i = h & mask
    yield i
    inc = (((h * 11400714819323198485) & M) >> (64 - nbits)) | 1
    while True:
        i = (i + inc) & mask
        yield i
"""

Second, the program I posted uses string objects as test cases.  The
current string hash acts like a good-quality pseudo-random number
generator:  change a character in the string, and the hash typically
changes "a lot".

It's also important to look at hashes with common patterns, because,
e.g., all "sufficiently small" integers are their _own_ hash codes
(e.g., hash(3) == 3).  Indeed, long ago Python changed its dict
implementation to avoid quadratic-time behavior for unfortunate sets
of real-life integer keys.

Example:  change `objgen()` to `yield i << 12` instead of `yield
str(i)`.  Then we generate integers all of whose final 12 bits are
zeroes.  For all sufficiently small tables, then, these ints _all_ map
to the same initial table slot (since the initial probe is taken from
the last `nbits` bits).  The collision resolution scheme is needed to
prevent disaster.

Here's a chunk of output from that, for dicts of size 2,730:

"""
bits 12 nslots 4,096 dlen 2,730 alpha 0.67 # built 37
theoretical avg probes for uniform hashing when found 1.65 not found 3.00
                                     crisp when found 1.65 not found 3.00
    prober linear
        found min 1:0.04% max 2730 mean 1365.50
        fail  min 2731:100.00% max 2731 mean 2731.00
    prober quadratic
        found min 1:0.04% max 2730 mean 1365.50
        fail  min 2731:100.00% max 2731 mean 2731.00
    prober pre28201
        found min 1:0.04% max 61 mean 6.17
        fail  min 5:28.94% max 68 mean 9.78
    prober current
        found min 1:0.04% max 58 mean 5.17
        fail  min 4:29.30% max 70 mean 8.62
    prober double
        found min 1:0.04% max 5 mean 2.73
        fail  min 2:41.47% max 9 mean 3.94
    prober dfib
        found min 1:0.04% max 9 mean 2.53
        fail  min 2:10.87% max 17 mean 4.48
    prober uniform
        found min 1:66.52% max 21 mean 1.65
        fail  min 1:33.41% max 30 mean 2.99
"""

It's a worst-case disaster for linear and quadratic probing.  The
`current` scheme does fine, but `double` and `dfib` do significantly
better on all measures shown.  `uniform` is oblivious, still achieving
its theoretical average-case performance.

That last isn't surprising "in theory", since it theoretically picks a
probe sequence uniformly at random from the set of all table slot
permutations.  It's perhaps a bit surprising that this approximate
_implementation_ also achieves it.  But `random.seed(h)` does a
relatively enormous amount of work to spray the bits of `h` all over
the Twister's internal state, and then shuffle them around.

In any case, the "double hashing" variants ("double" and "dfib") look
very promising, doing better than the current scheme for both small
tables and pathological key sets.