---
title: 'Hash Tables'
source: 'https://academia.sh/en/courses/data-structures/hash-tables'
course: 'Data Structures'
language: en
updated: '2026-08-17T18:07:51+00:00'
license: 'CC BY-SA 4.0'
---

# Hash Tables

Computing a location from a key, the qualities of a hash function, the load factor, and the conditions for average constant cost.

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.

```python
# 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:

```python
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.