Load Factor and Rehashing

OLD, NEW = 11, 23
KEYS = [25, 36, 47, 58, 69]

print("%8s %14s %14s %s" % ("key", "slot in %d" % OLD, "slot in %d" % NEW, "same?"))
for k in KEYS:
    a, b = k % OLD, k % NEW
    print("%8d %14d %14d %s" % (k, a, b, a == b))

print()
same = sum(1 for k in KEYS if k % OLD == k % NEW)
print("%d of %d keys keep their slot." % (same, len(KEYS)))
print("so the old array cannot be copied into the new one. every record")
print("must be hashed again with the NEW m and placed accordingly.")
print()
print("this is also why a hash table cannot be written to disk and reloaded")
print("into a table of a different size without rebuilding it.")

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

    while not prime(n):
        n += 1
    return n


class GrowingTable:
    """Chaining, with automatic growth at a threshold."""

    THRESHOLD = 0.75

    def __init__(self, buckets=7):
        self.table = [[] for _ in range(buckets)]
        self.count = 0
        self.rehashes = 0
        self.records_moved = 0

    def load_factor(self):
        return self.count / len(self.table)

    def insert(self, key, value):
        chain = self.table[key % len(self.table)]
        for i, (k, _v) in enumerate(chain):
            if k == key:
                chain[i] = (key, value)
                return
        chain.append((key, value))
        self.count += 1
        if self.load_factor() > self.THRESHOLD:
            self._rehash()

    def _rehash(self):
        old = self.table
        size = next_prime(2 * len(old) + 1)
        self.table = [[] for _ in range(size)]
        for chain in old:
            for key, value in chain:
                self.table[key % size].append((key, value))
                self.records_moved += 1
        self.rehashes += 1

    def search(self, key):
        for k, v in self.table[key % len(self.table)]:
            if k == key:
                return v
        return None


t = GrowingTable(buckets=7)
print("%8s %10s %10s %12s %12s"
      % ("inserted", "buckets", "alpha", "rehashes", "moved so far"))
for i in range(1, 201):
    t.insert(i * 13, "record %d" % i)
    if i in (5, 6, 10, 20, 50, 100, 200):
        print("%8d %10d %10.2f %12d %12d"
              % (i, len(t.table), t.load_factor(), t.rehashes, t.records_moved))

print()
print("200 records ended in a table of %d buckets at alpha %.2f."
      % (len(t.table), t.load_factor()))
print("it rehashed %d times and moved %d records in total."
      % (t.rehashes, t.records_moved))
print("that is %.2f moves per record inserted."
      % (t.records_moved / 200))
print()
print("every record is still findable after all that rehashing:",
      all(t.search(i * 13) == "record %d" % i for i in range(1, 201)))

def total_moves(n, grow):
    """Count every record move while inserting n records."""
    size, count, moved, rehashes = 7, 0, 0, 0
    for _ in range(n):
        count += 1
        if count / size > 0.75:
            size = grow(size)
            moved += count
            rehashes += 1
    return moved, rehashes


print("%10s %18s %12s %14s %18s %12s %14s"
      % ("records", "doubling moves", "rehashes", "moves/record",
         "add 10 moves", "rehashes", "moves/record"))
for n in (100, 1000, 10000, 100000):
    d_moved, d_rehash = total_moves(n, lambda s: 2 * s + 1)
    a_moved, a_rehash = total_moves(n, lambda s: s + 10)
    print("%10d %18d %12d %14.2f %18d %12d %14.2f"
          % (n, d_moved, d_rehash, d_moved / n,
             a_moved, a_rehash, a_moved / n))

print()
d = [total_moves(n, lambda s: 2 * s + 1)[0] / n
     for n in (100, 1000, 10000, 100000)]
a = [total_moves(n, lambda s: s + 10)[0] / n
     for n in (100, 1000, 10000, 100000)]
print("doubling: the moves per record stay BOUNDED, between %.1f and %.1f"
      % (min(d), max(d)))
print("across a thousandfold increase in n. they rise and fall with where")
print("the last rehash happened to land, and they do not grow. that bound")
print("is what AMORTISED O(1) means: one insert may cost O(n), but the")
print("average over all of them is a constant.")
print()
print("growing by a fixed 10: the moves per record go from %.1f to %.1f,"
      % (a[0], a[-1]))
print("a thousandfold rise, because the number of rehashes grows with n and")
print("each one copies everything. the total is O(n squared), which destroys")
print("the structure.")
print()
print("at 100,000 records, doubling moved %d and adding 10 moved %d."
      % (total_moves(100000, lambda s: 2 * s + 1)[0],
         total_moves(100000, lambda s: s + 10)[0]))

def simulate(grow_at, shrink_at, operations):
    """One record added and removed repeatedly, right at the boundary."""
    size, count, rehashes = 101, 76, 0          # alpha just above 0.75
    adding = False
    for _ in range(operations):
        count += 1 if adding else -1
        adding = not adding
        if count / size > grow_at:
            size = 2 * size + 1
            rehashes += 1
        elif count / size < shrink_at:
            size = max(11, size // 2)
            rehashes += 1
    return rehashes


print("100 operations alternating one insert and one delete at the boundary:")
print("   grow at 0.75, shrink at 0.75 :", simulate(0.75, 0.75, 100), "rehashes")
print("   grow at 0.75, shrink at 0.25 :", simulate(0.75, 0.25, 100), "rehashes")
print()
print("the same work, and the first arrangement rebuilt the whole table")
print("on %d of the 100 operations. the gap between the two thresholds is"
      % simulate(0.75, 0.75, 100))
print("called HYSTERESIS, and without it a table at the boundary thrashes.")

class Tombstone:
    def __repr__(self):
        return "DELETED"


EMPTY = None
DELETED = Tombstone()


def rehash(slots, new_size):
    """Only live records are carried over. Tombstones are simply not copied."""
    fresh = [EMPTY] * new_size
    carried = 0
    for cell in slots:
        if cell is not EMPTY and cell is not DELETED:
            at = cell % new_size
            while fresh[at] is not EMPTY:
                at = (at + 1) % new_size
            fresh[at] = cell
            carried += 1
    return fresh, carried


M = 23
slots = [EMPTY] * M
for k in range(1, 18):
    at = (k * 7) % M
    while slots[at] is not EMPTY:
        at = (at + 1) % M
    slots[at] = k * 7
for k in range(1, 14):                           # delete 13 of the 17
    for i in range(M):
        at = ((k * 7) % M + i) % M
        if slots[at] is not DELETED and slots[at] == k * 7:
            slots[at] = DELETED
            break

print("before rehashing:")
print("   live records :", sum(1 for s in slots
                               if s is not EMPTY and s is not DELETED))
print("   tombstones   :", sum(1 for s in slots if s is DELETED))
print("   empty        :", sum(1 for s in slots if s is EMPTY))

fresh, carried = rehash(slots, M)
print()
print("after rehashing into a table of the same size %d:" % M)
print("   live records :", sum(1 for s in fresh
                               if s is not EMPTY and s is not DELETED))
print("   tombstones   :", sum(1 for s in fresh if s is DELETED))
print("   empty        :", sum(1 for s in fresh if s is EMPTY))
print()
print("records carried over:", carried)
print("tombstones remaining:", sum(1 for s in fresh if s is DELETED))
print("so a delete-heavy table is repaired by rehashing even without")
print("growing, which is why implementations rehash on a tombstone count")
print("as well as on a load factor.")