Hash collisions explained with a tiny phone book
Trace separate chaining in a five-bucket phone book, distinguish a hash collision from a duplicate key, and explain the assumptions behind expected constant time.
A hash collision occurs when two different keys choose the same bucket. It is an ordinary condition in a hash table, so a correct implementation must handle it without overwriting unrelated entries. If you are learning dictionaries, a phone book with only five buckets makes the collision visible enough to trace by hand.
Use names as keys and fictional extension strings as values. The illustrative hash adds the character codes in a name and takes the remainder modulo five. This function is intentionally weak and predictable. It helps explain storage and lookup, but it is unsuitable as a recommendation for a production hash function.
Different names can select the same bucket
The ASCII character codes in Amy add to 295, as do those in May. Both therefore select bucket zero. Bob adds to 275 and also selects bucket zero. The table cannot infer that the names are equal from their bucket number; it still has to compare the original keys.
Separate chaining stores a collection of entries in each bucket. On lookup, compute the bucket, then inspect that bucket’s entries until a key matches. A missing key returns no value only after every relevant entry has been checked.
buckets = [[] for _ in range(5)]
def bucket_for(name):
return sum(ord(character) for character in name) % len(buckets)
def put(name, extension):
bucket = buckets[bucket_for(name)]
for position, (key, _) in enumerate(bucket):
if key == name:
bucket[position] = (name, extension)
return
bucket.append((name, extension))
def get(name):
comparisons = 0
for key, extension in buckets[bucket_for(name)]:
comparisons += 1
if key == name:
return extension, comparisons
return None, comparisons
put('Amy', '201')
put('May', '202')
put('Bob', '203')
assert get('May') == ('202', 2)
assert get('Ann') == (None, 3)
put('May', '220')
assert get('May') == ('220', 2)Ann has character sum 285, so its failed lookup visits bucket zero and compares all three stored names. A missing name mapped to an empty bucket would need no key comparisons. Both queries are unsuccessful, but they follow different amounts of work.
The first figure shows the three insertions before May’s value is updated.
Updating May changes its existing value. It does not append a second May, because this implementation defines a map with one value per exact key. Amy and May remain separate entries despite sharing both a character sum and a bucket.
The load factor describes an average
For n entries and m buckets, the load factor is alpha = n / m. The example has three entries and five buckets, so its load factor is 0.6. That small average does not prevent one bucket from holding all three entries.
Under a suitable randomized hashing model, the expected number of keys sharing a bucket is controlled by the load factor. Lookup in separate chaining then costs expected O(1 + alpha) key comparisons. If the table grows its bucket array to keep the load factor bounded, this becomes expected O(1). The ChainedHashTable chapter of Open Data Structures develops the hashing assumptions behind that result.
Without those assumptions, a lookup may inspect every stored key. Our additive hash makes anagrams collide automatically and leaves many other predictable collisions. Increasing the bucket count alone cannot repair equal character sums: Amy and May collide under every modulus. A stronger mixing function changes how the information in the key affects the hash.
The count also treats a key comparison as one operation. Comparing long strings can examine several characters, and computing a string’s hash requires reading it unless a previously computed hash is available. If key length grows with the problem, include it in the model. The O(1) dictionary shorthand normally assumes bounded-size keys or separates hashing cost from bucket access.
Resizing redistributes existing entries
Changing the bucket count changes the remainder calculation. An entry that belonged to bucket zero with five buckets may belong elsewhere with eleven. A resize therefore needs to reinsert existing entries using the new bucket count; copying each old bucket to the same numbered bucket is incorrect.
With a bucket count proportional to the number of entries, a direct rehash costs O(n) work for bounded-size keys. Growing geometrically allows that occasional expense to be spread across many insertions, producing an amortized bound when combined with the expected hashing analysis. Expected and amortized describe different things: one averages over random choices, while the other spreads cost over an operation sequence.
Move the entries when the modulus changes
The resize can move entries directly because the existing table already has at most one entry per exact key. It does not need to search for duplicates again. Allocate the new buckets, recompute the destination for every stored name, and only then replace the table’s bucket array.
def resize(new_count):
global buckets
if new_count <= 0:
raise ValueError('bucket count must be positive')
new_buckets = [[] for _ in range(new_count)]
for bucket in buckets:
for name, extension in bucket:
slot = sum(ord(character) for character in name) % new_count
new_buckets[slot].append((name, extension))
buckets = new_buckets
before = {name: extension for bucket in buckets for name, extension in bucket}
resize(11)
after = {name: extension for bucket in buckets for name, extension in bucket}
assert after == before
assert bucket_for('Amy') == bucket_for('May') == 9
assert bucket_for('Bob') == 0
assert get('May') == ('220', 2)
assert get('Ann') == (None, 0)
With eleven buckets, 295 leaves remainder nine, 275 leaves remainder zero, and 285 leaves remainder ten. Amy and May remain together because their full additive sums are equal. Bob separates from them because its equal remainder under five did not imply an equal sum. Ann’s unsuccessful lookup now checks an empty bucket, so its key-comparison count drops from three to zero. May still needs two comparisons in its new chain.
For n bounded-size keys, this implementation scans old_count buckets, allocates new_count empty buckets, and appends each known entry once. Its cost is O(n + old_count + new_count). When both bucket counts are proportional to the nonzero entry count, the resize is O(n). Asking for a billion mostly empty buckets is not an O(n) operation merely because three entries are stored. Both the old and new bucket arrays exist during the move, which also affects peak memory.
Reinserting through the public put function would repeat the search for an existing key. Under bad persistent collisions, those searches can inspect successively longer chains and make the rebuild quadratic. Direct relocation avoids those duplicate checks because the old map’s uniqueness invariant already supplies the needed fact. Ordinary lookup after the rebuild still suffers if the hash distribution is poor.
The code accepts a positive integer bucket count and changes the global table for this small example. An application container would normally keep the state on an instance and define what existing iterators observe during a resize. The example is not safe for concurrent reads and writes. That concern is separate from whether every key is placed in the correct new bucket.
Try resizing the three-name table to one bucket, then eleven, then five. Verify every key and updated extension after each move. Also test an empty table and a rejected zero capacity. Predict which collisions can disappear when only the modulus changes, and which anagram collisions must remain.
In a service accepting keys chosen by outsiders, predictable collisions can become a denial-of-service concern. Python randomizes string and byte hashes by default, and its data-model documentation explains both hash consistency and the reason for salting. That does not turn every possible custom key or dictionary operation into a worst-case constant-time guarantee.
Hashing here does not hide the names
The table stores the original key to resolve collisions. Anyone reading this structure can read the names and extension values. The small bucket number is not encryption, a password hash, or a secure anonymization scheme. Cryptographic hashing has different design goals, and even a cryptographic hash used for bucketing would not encrypt the stored entries.
Test insertion, replacement, a missing key in an occupied bucket, and a missing key in an empty bucket. Also verify that updating one colliding key leaves the others unchanged. Those tests target the map contract directly. In application code, use the language’s standard dictionary unless you have a specific reason to implement and maintain the collision policy yourself.
