Hash Tables

The previous topic brought search down to logarithmic cost in the best case. Is anything lower possible? Not for every structure based on ordering and comparison; structures that search by comparison are stuck at this bound.

A different idea is needed: computing where an element is stored from the element itself. If the location of a sought value can be computed, search comes down to a single step.

Direct Addressing

The plainest form of this idea is this: if the key is an integer and its range is small, the key itself can be used as an index.

# Let the keys be in the range 0-9; the key is directly the index.
table = [None] * 10
table[3] = "three"
table[7] = "seven"
print(table[3], table[7])        # three seven

Access is constant time, and no search is done. The problem is the size of the key space: if the keys are nine-digit identification numbers, direct addressing requires an array of a billion slots. If the keys are strings, they cannot be used as an index at all.

The Hash Function

A hash function maps any key to an integer within a fixed range. This number determines the location (bucket) in the table:

$$\text{location} = h(\text{key}) \bmod m$$

Here $m$ is the table size. No matter how large the key space is, the location falls between $0$ and $m-1$.

This solves direct addressing’s memory problem — but introduces a new one: two different keys can fall into the same location. This is called a collision, and it is unavoidable. As long as the key space is larger than the table size, it is certain that at least two keys will map to the same location. This is a direct consequence of the pigeonhole principle: when $n$ objects are distributed into $m < n$ boxes, at least one box receives more than one object.

How to deal with collisions is the subject of the next lesson. This lesson is concerned with the conditions that make collisions rare.

A Good Hash Function

Three qualities are sought.

Determinism. The same key must always produce the same value. The mapping must not change while the program runs; otherwise stored data cannot be found.

Uniform distribution. Keys should spread as evenly as possible across buckets. Piling up in one bucket turns search in that bucket linear. In a good function, changing a single bit of the key changes roughly half the output; this property is called the avalanche effect.

Speed. Computing the hash must not be more expensive than the search itself. Cryptographic hash functions provide the avalanche effect strongly, but they are slower than necessary for a data structure; lightweight functions are used for tables.

A common method for strings is to evaluate the characters as a polynomial over a base:

def string_hash(text: str, base: int = 31, mod: int = 1_000_003) -> int:
    """Evaluates the characters as a polynomial."""
    value = 0
    for char in text:
        value = (value * base + ord(char)) % mod
    return value


print(string_hash("value"))          # 972388
print(string_hash("valuf"))          # 972389  — one-letter difference
print(string_hash("aluev"))          # 914375  — same letters, different order

Using the base as a multiplier makes the character order affect the result: different strings made of the same letters produce different values. If order were not taken into account, a function that summed the letters would collide on every permutation of the letters.

The Load Factor

The table’s fill ratio is the determinant of performance:

$$\alpha = \frac{n}{m}$$

$n$ is the number of elements, $m$ the number of buckets. As the load factor grows, the probability of collision increases; as it shrinks, memory is wasted.

Implementations set a threshold (commonly around $0.7$) and grow the table once it is exceeded. Growing means doubling capacity, as with a dynamic array, and relocating every element — because the location depends on the table size. This operation is called rehashing, and its cost is $O(n)$; amortized, it stays constant per insertion.

The Hash Value and the Location Are Separate Things

It is common to confuse the two concepts. The hash value is the number computed from the key, independent of the table size. The location is that value reduced to the table size.

The practical consequence of this distinction is that the hash value can be stored. Implementations write the hash value alongside the key in every slot. This provides two gains: during rehashing, values are not recomputed, only reduced to the new table size; and during search, hash values are compared before the keys themselves — if they differ, the expensive equality test is never entered.

The second gain is significant when keys are long strings: comparing two integers is far cheaper than comparing two strings character by character.

Average and Worst Case

The hash table’s cost guarantee is conditional:

Case	Search, insert, delete
Average (uniform distribution, bounded load factor)	$O(1)$
Worst case (all keys in the same bucket)	$O(n)$

The worst case is not merely theoretical. If the hash function is known, keys that fall into the same bucket can be deliberately produced; this is a form of attack that forces the server into linear cost. The defense is adding a seed determined at run time to the hash function — so the distribution of buckets cannot be predicted from outside. This subject is covered separately in the application security curriculum.

The Immutability of the Key

If a key is modified after being placed in the table, its hash value also changes; the element is no longer searched for in the bucket it occupies and becomes unreachable.

This is why immutable values are used as keys. This is one of the practical consequences of the immutable–mutable distinction introduced in the Programming Fundamentals course: languages often directly forbid mutable objects from being keys.

The second rule is consistency between equality and the hash: two keys considered equal must produce the same hash value. Failing to update the hash computation while customizing equality behavior leads to silently broken tables.

Cost Table

Structure	Search	Insert	Delete	Order preserved
Sorted array	$O(\log n)$	$O(n)$	$O(n)$	Yes
Skip list	$O(\log n)$ expected	$O(\log n)$	$O(\log n)$	Yes
Hash table	$O(1)$ average	$O(1)$ average	$O(1)$ average	No

Some implementations separately preserve insertion order, independent of bucket layout; this is insertion order, not sorted order, and has nothing to do with the magnitude of the keys. Range queries still cannot be done.

The last column is the price the hash table pays: because elements are distributed by bucket order, key order is not preserved. If sorted traversal or range queries are needed, tree-based structures are chosen.

One last warning: a hash value is not an identity. It is ordinary for two different keys to produce the same hash value; this is why, once a hash match is found, the keys themselves are also compared. Skipping this step leads to a table that silently returns the wrong value.

Summary

• A hash table brings search down to average constant time by computing the location from the key.
• Direct addressing is applicable only to small, integer key spaces; a hash function removes this restriction.
• A good hash function is deterministic, distributes uniformly, and is fast; the avalanche effect is a sign of uniform distribution.
• Collisions are unavoidable; the load factor is the fill ratio, and once the threshold is exceeded, the table is grown and every element relocated.
• The worst case is linear and can be deliberately triggered; a seeded hash reduces this risk.
• Keys must be immutable, and equality must stay consistent with the hash.

Next Step

It has been established that collisions are unavoidable, but not what to do about them. Where are two elements that fall into the same bucket placed, and how does that decision affect search cost? The next lesson compares the two main families of solutions — chaining and open addressing.