Hash tables

Finding Elvin's number in a phone book by scanning the whole list takes O(n) time; binary search in a sorted list takes O(log n). What if the number of steps did not depend on n at all? That is what a hash table does: it turns the key directly into an array index. Python's dict and set, database hash indexes, caches and compilers' symbol tables are all built on this idea.

The hash function

• Deterministic: the same key always gives the same hash.
• Uniformity: keys spread roughly evenly over the buckets.
• Speed: computing it takes O(key length) time.
• Uses the whole key: a function that looks only at the first letter sends “Aysel” and “Anar” to the same bucket.

Collisions and how to resolve them

There are far more possible keys than buckets, so by the pigeonhole principle two different keys landing in the same bucket — a collision — is unavoidable. It also happens sooner than expected: this is the “birthday paradox”. In a group of just 23 people the chance that two share a birthday is already above 50%.

• Separate chaining: each bucket holds a list, and colliding keys are simply appended to it.
• Open addressing: all keys live in the array itself; if a bucket is taken, we look for the next free slot. Linear probing: h(k), h(k) + 1, h(k) + 2, … (mod m).
• Quadratic probing (h(k) + i²) and double hashing (h₁(k) + i · h₂(k)) reduce the piling-up of keys (clustering).

def insert_linear(table, key):
    m = len(table)
    i = key % m
    probes = 1
    while table[i] is not None:
        i = (i + 1) % m
        probes += 1
    table[i] = key
    return probes

table = [None] * 11
for k in [12, 44, 13, 88, 23, 94, 11, 39, 20]:
    p = insert_linear(table, k)
    print(k, '-> slot', table.index(k), 'probes:', p)
print(table)
print('load factor:', round(9 / 11, 2))

12 -> slot 1 probes: 1
44 -> slot 0 probes: 1
13 -> slot 2 probes: 1
88 -> slot 3 probes: 4
23 -> slot 4 probes: 4
94 -> slot 6 probes: 1
11 -> slot 5 probes: 6
39 -> slot 7 probes: 2
20 -> slot 9 probes: 1
[44, 12, 13, 88, 23, 11, 94, 39, None, 20, None]
load factor: 0.82

Load factor and O(1) on average

When α crosses a threshold (0.75 in Java's HashMap, for example), the table roughly doubles and every key is hashed again for the new m (rehashing). This occasional O(n) work is amortised exactly as in a dynamic array, so insert, search and delete stay O(1) on average. In the worst case — all keys in one bucket — they are O(n).

class HashMap:
    def __init__(self, m=5):
        self.buckets, self.n = [[] for _ in range(m)], 0
    def _index(self, key):
        h = 0
        for ch in key:
            h = h * 31 + ord(ch)
        return h % len(self.buckets)
    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value
                return
        bucket.append([key, value])
        self.n += 1
        if self.n / len(self.buckets) > 0.75:
            pairs = [p for b in self.buckets for p in b]
            self.buckets = [[] for _ in range(2 * len(self.buckets) + 1)]
            for p in pairs:
                self.buckets[self._index(p[0])].append(p)
    def get(self, key):
        for k, v in self.buckets[self._index(key)]:
            if k == key:
                return v

caps = HashMap()
for pair in ['Azerbaijan:Baku', 'Georgia:Tbilisi', 'Japan:Tokyo', 'Italy:Rome', 'Egypt:Cairo']:
    caps.put(*pair.split(':'))
print(caps.get('Azerbaijan'), caps.get('Japan'), caps.get('France'))
print(len(caps.buckets), [len(b) for b in caps.buckets])

Baku Tokyo None
11 [1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0]