Quadratic Probing and Double Hashing

EMPTY = None


def quadratic_insert(slots, key):
    m = len(slots)
    for i in range(m):
        at = (key % m + i * i) % m
        if slots[at] is EMPTY:
            slots[at] = key
            return at
    return None


for M in (16, 11):
    slots = [EMPTY] * M
    reachable = sorted({(0 + i * i) % M for i in range(M)})
    print("m = %d (%s)" % (M, "a power of 2" if M == 16 else "prime"))
    print("   offsets i*i mod m, for i = 0..%d : %s"
          % (M - 1, [(i * i) % M for i in range(M)]))
    print("   DISTINCT slots a key hashing to 0 can ever reach: %s" % reachable)
    print("   that is %d of %d slots, which is %.0f%%"
          % (len(reachable), M, 100 * len(reachable) / M))

    placed, refused = 0, []
    for j in range(M):
        key = j * M                              # every key is 0 mod M
        at = quadratic_insert(slots, key)
        if at is None:
            refused.append(key)
        else:
            placed += 1
    free = sum(1 for s in slots if s is EMPTY)
    print("   inserting %d keys that all hash to 0: %d placed, %d REFUSED"
          % (M, placed, len(refused)))
    print("   and the table still has %d free slots out of %d" % (free, M))
    print()

print("so quadratic probing can refuse an insertion into a table that is")
print("mostly empty. this is not a bug in the code; it is the arithmetic.")
print("i*i mod m simply does not visit every residue.")

def reachable_count(m):
    return len({(i * i) % m for i in range(m)})


print("%8s %10s %18s %16s %14s"
      % ("m", "prime?", "slots reachable", "(m+1)/2", "fraction"))


def is_prime(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += 1
    return True


for m in (11, 13, 16, 17, 31, 32, 101, 128):
    count = reachable_count(m)
    print("%8d %10s %18d %16d %13.0f%%"
          % (m, "yes" if is_prime(m) else "NO", count, (m + 1) // 2,
             100 * count / m))

print()
primes = [m for m in (11, 13, 17, 31, 101) ]
print("for every prime above, reachable slots equal (m+1)/2 exactly:",
      all(reachable_count(m) == (m + 1) // 2 for m in primes))
print("for the powers of 2 it is far worse:",
      [(m, reachable_count(m)) for m in (16, 32, 128)])
print()
print("hence the two rules together: m PRIME, and alpha below 0.5.")
print("neither rule alone is enough.")

M = 101

same_hash = [i * M + 7 for i in range(5)]       # all 7 mod 101
print("five keys, all %d mod %d:" % (7, M), same_hash)
print()
print("their quadratic probe sequences, first 6 steps:")
for k in same_hash:
    seq = [(k % M + i * i) % M for i in range(6)]
    print("   %-8d %s" % (k, seq))
print()
print("identical, because the sequence depends only on h(k) = %d." % 7)
print("that is SECONDARY clustering: fewer keys are affected than under")
print("primary clustering, but those that are, are affected completely.")

M = 11
EMPTY = None


def h1(k, m):
    return k % m


def h2(k, m):
    return 1 + (k % (m - 1))                     # never 0, always coprime with a prime m


def double_insert(slots, key, trace=False):
    m = len(slots)
    step = h2(key, m)
    for i in range(m):
        at = (h1(key, m) + i * step) % m
        if slots[at] is EMPTY:
            slots[at] = key
            if trace:
                print("   %-4d h1=%-3d h2=%-3d i=%-2d -> slot %-3d (%d probes)"
                      % (key, h1(key, m), step, i, at, i + 1))
            return at
    return None


slots = [EMPTY] * M
KEYS = [25, 36, 47, 58, 69, 80]
print("double hashing, m = %d, the same six keys that all hash to slot 3:" % M)
for k in KEYS:
    double_insert(slots, k, trace=True)

print()
print("the table:")
print("   " + " ".join("%4s" % (s if s is not None else "-") for s in slots))
print("   " + " ".join("%4d" % i for i in range(M)))
print()
print("every key has its OWN step, so no two sequences agree:")
for k in KEYS:
    print("   %-4d step %-3d sequence %s"
          % (k, h2(k, M), [(h1(k, M) + i * h2(k, M)) % M for i in range(5)]))
print()
print("no two of those sequences are the same, although all six keys have")
print("the same h1. that is secondary clustering removed.")
print()
print("and with m prime and h2 between 1 and m-1, a sequence reaches every")
print("slot. for key 25, step %d:" % h2(25, M))
print("   ", sorted({(h1(25, M) + i * h2(25, M)) % M for i in range(M)}))
print("   all %d slots:" % M,
      len({(h1(25, M) + i * h2(25, M)) % M for i in range(M)}) == M)

def mix(i):
    x = ((i + 1) * 2654435761) % (2 ** 32)
    x ^= x >> 13
    x = (x * 2246822519) % (2 ** 32)
    x ^= x >> 17
    return x


M = 1009
EMPTY = None


def fill(n, step_of):
    slots = [EMPTY] * M
    total = 0
    for j in range(n):
        k = mix(j)
        for i in range(M):
            at = step_of(k, i)
            total += 1
            if slots[at] is EMPTY:
                slots[at] = k
                break
    return slots, total / n


def linear(k, i):
    return (k % M + i) % M


def quadratic(k, i):
    return (k % M + i * i) % M


def double(k, i):
    return (k % M + i * (1 + k % (M - 1))) % M


def longest_run(slots):
    best = run = 0
    for cell in slots + slots:                   # as a ring
        run = run + 1 if cell is not EMPTY else 0
        best = max(best, run)
    return min(best, M)


def chance_fill(n):
    """Occupy n slots with NO probing at all: the baseline for a run length."""
    slots = [EMPTY] * M
    placed, j = 0, 0
    while placed < n:
        at = mix(j + 10 ** 6) % M
        j += 1
        if slots[at] is EMPTY:
            slots[at] = True
            placed += 1
    return slots


print("%7s %22s %16s %14s %14s"
      % ("alpha", "scheme", "probes per insert", "longest run", "x chance"))
for alpha in (0.4, 0.6, 0.8):
    n = int(alpha * M)
    base = longest_run(chance_fill(n))
    for name, fn in (("linear probing", linear),
                     ("quadratic probing", quadratic),
                     ("double hashing", double)):
        slots, avg = fill(n, fn)
        run = longest_run(slots)
        print("%7.2f %22s %17.2f %14d %13.1fx"
              % (alpha, name, avg, run, run / base))
    print("%7.2f %22s %17s %14d %13.1fx"
          % (alpha, "(no probing: chance)", "n/a", base, 1.0))
    print()

print("double hashing needs the fewest probes per insert at every alpha and")
print("quadratic probing is second. that is the column that matters.")
print()
print("the longest-run column needs the chance row beside it. a run of")
print("ADJACENT occupied slots is what linear probing builds on purpose, and")
print("at alpha 0.8 its run is almost 5 times what chance alone gives. the")
print("other two are above chance as well, at roughly 1.5 and 2.5 times, so")
print("they are not free of adjacency at high load: they are merely far")
print("better than linear probing at it. the ordering between those two is")
print("not stable and should not be read as a result.")