4.1 Hash Table Basics

Prerequisites: Arrays and Linked Lists, approximately 35 minutes. This lesson begins by exploring the relationship between keys, hash values, buckets, and equality checks, then gradually implements a chained-hash table that supports insert, update, lookup, and deletion operations.

The First Rule Connecting Keys, Buckets, and Equality

The table receives a key and a value. A later lookup hashes the same key to locate a bucket, then uses equality within that candidate set to confirm identity. Hashing narrows the search; it does not replace equality.

First, Build a Map

A hash table stores a mapping from key to value. In a phone book, the name is the key and the phone number is the value. In a compiler's symbol table, the variable name is the key, and the type and memory address are the value.

A single lookup follows four steps:

key
  │  Hash function
  ▼
hash code (hash value)
  │  Locates bucket using capacity, e.g., hash code % bucket_count
  ▼
bucket
  │  Uses equality comparison to confirm the exact key
  ▼
value

These four concepts must not be confused:

Concept	Responsibility	Phone Book Example
key	Identifies a single mapping	"Bob"
value	The data associated with the key	"456"
hash code	Integer result of the hash function	Some integer value
bucket index	The selected bucket position based on bucket count	hash_code % 8

Hash values typically span a larger range than bucket indices. After table resizing, a key’s hash value can remain unchanged while its bucket index may change.

Why Not Iterate Through an Array One by One?

Let's look at a linear phone directory:

phone_book = [("Alice", "123"), ("Bob", "456"), ("Charlie", "789")]

def find_phone(entries, name):
    for key, value in entries:
        if key == name:
            return value
    raise KeyError(name)

assert find_phone(phone_book, "Bob") == "456"

Arrays support random access by integer index, but here we're dealing with names. A linear list must start from the beginning and compare each entry sequentially, worst-case, it examines all n records, resulting in O(n) time complexity.

A hash table first computes a bucket position using the key, then checks only the candidates within that bucket. Under uniform hashing, growing the bucket count to keep average bucket length bounded can keep the expected candidate count O(1). Hashing and key comparisons still have their own costs.

What Hash Functions Are Responsible For

The following teaching function folds a string into a non-negative integer. It's included solely to illustrate the process and is not suitable for passwords, signatures, persistent IDs, or real hash table implementations.

def stable_hash(key):
    if not isinstance(key, str):
        raise TypeError("this teaching hash accepts strings only")

    value = 0
    for char in key:
        value = (value * 31 + ord(char)) & 0xFFFFFFFF
    return value

assert stable_hash("Bob") == 66965
assert stable_hash("Bob") == stable_hash("Bob")

ord(char) returns a Unicode code point. Multiplying the accumulated value by 31 makes character order affect the result. Thus, "ab" and "ba" typically produce different hashes. & 0xFFFFFFFF constrains the teaching output to a 32-bit unsigned range.

When there are currently 8 buckets, you can use modulo arithmetic to determine the bucket index:

def bucket_index(hash_code, bucket_count):
    if bucket_count <= 0:
        raise ValueError("bucket_count must be positive")
    return hash_code % bucket_count

assert bucket_index(66965, 8) == 5
assert bucket_index(66965, 16) == 5
assert bucket_index(73, 8) == 1
assert bucket_index(73, 16) == 9

Bob stays in the same bucket after this resize, while I (hash 73) moves from bucket 1 to 9. Resizing requires recalculating positions; not every key must change buckets.

Modulo is just a common teaching example. Real libraries use bucket layout, hash mixing strategies, and runtime constraints to determine bucket placement. Understanding that "hash value" and "bucket index" belong to two distinct layers is more reliable than memorizing a specific formula.

Why Collisions Are Inevitable

If the possible keys outnumber the buckets, at least two distinct keys must map to one bucket. This is the pigeonhole principle.

In the teaching function above, the code points of the single-character keys "A" and "I" differ by 8. When the bucket capacity is 8, both keys hash into bucket 1:

stable_hash("A") % 8 = 65 % 8 = 1
stable_hash("I") % 8 = 73 % 8 = 1

A collision does not mean the two keys are equal, nor does it indicate that the hash function has failed. The hash table must still compare the keys within the same bucket.

Key Equality and Hashing Contract

A hash container relies on at least two rules:

1. If two keys are considered equal, they must produce the same hash value.
2. While a key exists in the container, its hash value and equality relationship must remain stable.

The reverse does not hold: different keys may share a hash value. Collision handling exists for this case.

Python uses __eq__() to determine equality and __hash__() to provide a hash value. Mutable objects that are compared by value are prone to "bucket migration" after insertion, so list and dict cannot be used as dict keys; a tuple is hashable only when all its elements are hashable. Mutability alone does not forbid hashing: a custom instance using default identity equality and hashing may change fields unrelated to those rules.

valid = {
    "apple": "fruit",
    (12, 7): "grid coordinates",
}

try:
    invalid = {["mutable", "list"]: "value"}
except TypeError:
    pass
else:
    raise AssertionError("a list must not be accepted as a dict key")

assert valid["apple"] == "fruit"

Python defaults to randomizing the hash seeds for str and bytes. The value of hash("apple") remains stable within a single process but may change across process boundaries. It is suitable for hash containers within the current process but is not appropriate for use as a stable identifier when written to files, nor does it provide cryptographic security.

Implementing the First Table with Chaining

The chaining method allows each bucket to store a group of (key, value). The teaching code uses Python list to represent buckets, with emphasis on the mapping contract; production libraries can opt for alternative bucket structures.

def stable_hash(key):
    if not isinstance(key, str):
        raise TypeError("this teaching map accepts string keys only")
    value = 0
    for char in key:
        value = (value * 31 + ord(char)) & 0xFFFFFFFF
    return value

class ChainedHashMap:
    def __init__(self, capacity=8):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self._buckets = [[] for _ in range(capacity)]
        self._size = 0

    def __len__(self):
        return self._size

    def _bucket(self, key):
        index = stable_hash(key) % len(self._buckets)
        return self._buckets[index]

    def put(self, key, value):
        bucket = self._bucket(key)
        for position, (stored_key, _) in enumerate(bucket):
            if stored_key == key:
                bucket[position] = (key, value)
                return
        bucket.append((key, value))
        self._size += 1

    def get(self, key):
        for stored_key, value in self._bucket(key):
            if stored_key == key:
                return value
        raise KeyError(key)

    def remove(self, key):
        bucket = self._bucket(key)
        for position, (stored_key, value) in enumerate(bucket):
            if stored_key == key:
                bucket.pop(position)
                self._size -= 1
                return value
        raise KeyError(key)

notes = ChainedHashMap(8)
notes.put("A", "apple note")
notes.put("I", "ink note")       # Lands in the same bucket as A
notes.put("A", "new apple note") # Updates the value without increasing size

assert len(notes) == 2
assert notes.get("A") == "new apple note"
assert notes.get("I") == "ink note"
assert notes.remove("A") == "new apple note"
assert notes.get("I") == "ink note"

Walking Through a Single put

Assume a capacity of 8. First insert "A", then insert "I":

1. Both keys are hashed and placed into bucket 1.
2. put("A", ...) scans the empty bucket and appends the first mapping.
3. put("I", ...) scans bucket 1 and finds "I" != "A", so it appends the second mapping.
4. On a subsequent put("A", ...), the loop finds a matching key and replaces the value; size remains 2.

The internal state of the bucket is as follows:

buckets[1] -> [("A", "new apple note"), ("I", "ink note")]

get("I") cannot simply see the bucket and return "A"'s value. It must iterate through each entry until it finds a key that truly matches.

Complexity Must Be Tracked Along with Conditions

Let n count mappings, m count buckets, and L be the string key’s length. This implementation never resizes; with fixed m, average bucket length cannot remain bounded as n keeps growing.

Operation	When bucket distribution is good and n/m is controlled	Worst-case bucket comparisons	Additional Notes
get	Expected O(1) bucket-level comparisons	O(n)	Still incurs O(L) cost for computing the hash
put	Expected O(1) bucket-level comparisons	O(n)	Updates must first locate the key
remove	Expected O(1) bucket-level comparisons	O(n)	In this implementation, the bucket-level pop also shifts subsequent references
Space	O(m + n)	O(m + n)	m buckets plus n key-value pairs

"The hash table lookup is O(1)" omits three critical assumptions: a well-distributed hash, controlled load factor, and a bounded cost for computing the hash and comparing keys. If all keys hash to the same bucket, lookup degrades to a linear scan.

This example rescans the key on every operation, spending Θ(L) time on hashing. A string equality check can also scan the whole string. With key lengths bounded by L and b entries in the bucket, a lookup can cost O((b+1)(L+1)). The table’s O(n) counts candidate comparisons, not total time independent of key length. Its space row counts buckets and references, excluding key/value payloads.

When analyzing long strings, composite objects, or inputs under attacker control, the cost of hashing and worst-case collisions must be explicitly modeled. In practice, if business logic only handles keys with bounded length (such as short IDs) engineers often treat key operations as constant-time operations.

Use the Language’s Mapping Types

Implementing a map helps explain its contract. For application code, start with the standard library:

Language	Common Types	Order and Failure Semantics
Python	dict	Preserves insertion order in Python 3.7+; raises KeyError if d[key] is missing
Java	HashMap<K,V>	Does not guarantee iteration order; allows null key and value pairs; not thread-safe
C++	std::unordered_map<Key,T>	Does not provide key-based sorting during traversal; interface distinguishes between find, at, and operator[]

Java's HashMap documentation states that constant-time operations depend on a well-distributed hash. C++ unordered associative containers require that equivalent keys produce the same hash; most operations are fast on average, though worst-case performance may degrade to linear time. Return values, exception behaviors, and iterator invalidation rules differ across languages. When writing production code, always consult the corresponding version's API documentation.

Common Misconceptions

Treating a hash value as a bucket index

The hash value is generated first, and the bucket index is then computed based on the current table layout. Resizing may change bucket indices, so entries must be arranged under the new layout. An implementation with cached hashes need not rescan the keys.

Only comparing hash values

A matching hash does not imply key equality. Reaching a candidate bucket is not enough; key equality must still be checked.

Using mutable content as a key

If a key’s hash changes after insertion, subsequent lookups may search the wrong bucket. Prefer immutable values, or for custom types, design consistent and stable __eq__ / __hash__.

Misusing hash() as a persistent identifier

Python string hashes change across processes by default. A stable digest needs a specified algorithm, encoding, and collision policy. Determinism alone does not make it a unique identifier. For cryptographic operations, digital signatures, or integrity protection, use dedicated cryptographic libraries and protocols.

Expecting hash tables to maintain sorted order

The insertion order in Python dict does not correspond to key ordering. To query by key range or traverse keys in order, sort the keys first, or use tree-based structures designed for ordered access.

Debugging Order

1. Document the type of the key, its equality rules, and hash stability.
2. Print the hash value and bucket index separately to ensure they are not conflated into a single concept.
3. Construct two keys that would hash to the same bucket and test insertion, update, query, and deletion operations.
4. Verify that the size counter does not incorrectly increment when updating an existing key.
5. Examine the failure contract for missing keys, determine whether it raises an exception, returns null, or yields an explicit result.
6. When analyzing complexity, clearly define what n, m, and key length represent in the context of the algorithm.

Hands-on Verify Hash Contracts

Difficulty	Task	Acceptance Criteria
Beginner	Add contains to ChainedHashMap	When value is None, clearly distinguish between "presence" and "absence"
Beginner	Count word frequencies in a text	First define rules for case and punctuation
Advanced	Add resizing to chained hashing	Old mappings are repositioned according to new capacity, and size is not double-counted
Advanced	Design composite keys	Equal keys must have equal hashes; unequal keys may collide
Engineering	Compare dict.get, in, and []	Clearly document the different semantic meanings of missing keys

Check the Hash Contract Once More

A hash table first narrows the candidate set using hashing, then verifies identity via equality comparison. The expected O(1) performance is not a guaranteed promise: it depends on hash distribution, load factor, and the cost of both hashing and key comparison. By separating these layers, it becomes clear why rehashing requires repositioning entries during expansion, and why key comparisons are still necessary even when collisions occur.

Deliberately place A and I in the same bucket; lookup must still return the correct value for each key. Continue to Hash Collisions and Resizing to see how collisions, tombstones, and rehashing preserve the lookup path.

Official References

• Python Data Model: __hash__
• Python Built-in Types: dict
• Java SE 17 HashMap
• C++ unordered associative container requirements