Skip to content
Velloreth
Programming 8 min read

Hash Tables Explained: How O(1) Lookup Really Works

Hash tables turn keys into array indexes with a hash function. Learn how they work, how collisions are handled, and why lookups are O(1) on average.

By

The core idea

A hash table stores key-value pairs and finds a value from its key in constant time. It achieves this by computing where the value should live rather than searching for it.

The mechanism has three steps:

  1. Run the key through a hash function to get an integer.
  2. Reduce that integer to a valid array index, usually with the modulo operator.
  3. Store or retrieve the value at that index.
// A hash table in about fifteen lines
class HashTable {
  constructor(size = 16) {
    this.buckets = new Array(size).fill(null).map(() => []);
  }

  hash(key) {
    let h = 0;
    for (let i = 0; i < key.length; i++) {
      h = (h * 31 + key.charCodeAt(i)) | 0;
    }
    return Math.abs(h) % this.buckets.length;
  }

  set(key, value) {
    const bucket = this.buckets[this.hash(key)];
    const entry = bucket.find((e) => e[0] === key);
    if (entry) entry[1] = value;
    else bucket.push([key, value]);
  }

  get(key) {
    const bucket = this.buckets[this.hash(key)];
    const entry = bucket.find((e) => e[0] === key);
    return entry ? entry[1] : undefined;
  }
}

That is the whole structure. Everything else is refinement.

Why lookup is O(1)

The key insight is that the hash function computes the location directly. It does not scan, compare, or search. Given the key, it produces an index in constant time, and the array access at that index is also constant time.

This is why a hash table with ten entries and one with ten million entries both look up a key in roughly the same time. The cost does not scale with the number of entries.

That is a remarkable property. Every other structure in common use — arrays, trees, lists — has lookup cost that grows with size. The hash table is the only one that does not, which is why it underpins caching, indexing, deduplication, and symbol tables.

Collisions are unavoidable

Here is the problem. A hash function maps an unbounded set of keys to a bounded set of indexes. By the pigeonhole principle, different keys must sometimes produce the same index. This is a collision, and no hash function can avoid it.

There are two standard ways to handle collisions.

Chaining

Each bucket holds a list of entries. Colliding keys are appended to the same list.

// bucket 5 might hold: [['apple', 1], ['grape', 7]]

Lookup hashes the key, goes to the bucket, and scans the short list for a matching key. When the load factor is low, those lists are almost always length zero or one, so the scan is effectively constant.

Chaining is simple and degrades gracefully. Its weakness is memory: each entry needs a pointer for the list, and the lists are scattered in memory.

Open addressing

Instead of lists, each bucket holds at most one entry. On collision, the table probes for the next free slot.

// Linear probing: try index, index+1, index+2, ...
let i = hash(key);
while (buckets[i] !== null && buckets[i].key !== key) {
  i = (i + 1) % buckets.length;
}

Open addressing is more cache-friendly because everything lives in one array, and it uses less memory. Its weakness is clustering: consecutive occupied slots form runs that grow and slow down probing. Variants like quadratic probing and double hashing spread the probes out to reduce this.

Most production hash tables use one of these two approaches. Python’s dict uses open addressing. Java’s HashMap uses chaining, switching to a tree when a bucket grows large.

The load factor

The load factor is the number of entries divided by the number of buckets. It is the single number that governs hash table performance.

Load factorBehaviour
0.25Fast lookups, most memory wasted
0.75The common default — good balance
1.0Frequent collisions, lookups slow
2.0Severe degradation, approaching O(n)

When the load factor crosses the implementation’s threshold, the table resizes — typically doubling — and every entry is rehashed into the new bucket array. That resize is O(n), but because the table doubles, resizes happen at exponentially increasing intervals, so the amortised cost per insertion stays O(1).

This is the same amortisation argument as appending to a dynamic array.

What makes a good hash function

A good hash function has three properties:

  • Deterministic — the same key always produces the same hash.
  • Uniform — keys spread evenly across buckets, with no clustering.
  • Fast — hashing is on the critical path of every operation.

The classic simple hash multiplies by a prime and adds each character:

h = (h * 31 + charCode) | 0;

The multiplier 31 is chosen because it is prime and because h * 31 can be computed as (h << 5) - h, which is fast. Java’s String.hashCode uses exactly this.

Cryptographic hashes like SHA-256 are also uniform but far too slow for a hash table. They are designed for security, not speed, and they are used for different purposes — verifying integrity, not indexing.

Keys must be immutable

This is the rule that trips people up most often.

If you mutate a key after inserting it, its hash changes, and the entry becomes unreachable. The table looks in the new bucket, finds nothing, and the value is effectively lost.

const map = new Map();
const key = { id: 1 };
map.set(key, 'value');
key.id = 2;          // mutating the key
map.get(key);        // still works — same object reference

In JavaScript, object keys are compared by reference, so mutating the object does not break the lookup — but it also means two structurally identical objects are different keys:

map.set({ id: 1 }, 'a');
map.get({ id: 1 }); // undefined — different object

In Python, the situation is stricter. Only hashable types can be keys, and mutable types like lists are rejected outright:

d = {}
d[(1, 2)] = 'tuple key works'
d[[1, 2]] = 'list key'  # TypeError: unhashable type

The rule is: keys must be immutable, or at least never mutated while in the table.

Hash tables in the wild

Caching. A memoisation cache is a hash map from arguments to results. This is what turns naive exponential recursion into linear dynamic programming.

Deduplication. A set is a hash table without values. Checking membership is O(1), which is why deduplicating a list is a single pass.

Counting. Frequency maps are hash tables from item to count.

Database indexes. A hash index gives O(1) equality lookup, though it cannot serve range queries — that is what B-trees are for.

Symbol tables. Compilers and interpreters store variable names in hash tables.

Routing. Web frameworks map URL patterns to handlers with hash tables.

Object representation. JavaScript objects, Python dicts, and Ruby hashes are all hash tables underneath.

The worst case

Hash table operations are O(1) on average, and the qualifier matters. The worst case is O(n), and it happens in two situations.

The first is a bad hash function that sends many keys to the same bucket. If every key hashes to index 0, the table degenerates into a linked list.

The second is adversarial input. If an attacker can choose keys that collide, they can force O(n) lookups and turn a fast service into a slow one. This is a real denial-of-service technique, and it is why many languages randomise their hash seed per process — so an attacker cannot predict which keys will collide.

Python, Ruby, and Java all randomise string hashing for this reason. It is a small detail with real security consequences.

Practical guidance

  • Reach for a hash map first when you need lookup by key, counting, grouping, or deduplication.
  • Do not rely on iteration order unless your language guarantees it. Python’s dict preserves insertion order as a language guarantee; JavaScript’s object does not for integer-like keys.
  • Prefer a set over a map when you only need membership.
  • Watch memory — hash tables have real overhead per entry, often 30 to 50 bytes beyond the data itself.
  • Do not use them for range queries — “all items between A and B” needs a sorted structure.

For how hash tables fit with the other structures, see data structures every developer should know and Big-O notation explained. For the security angle, encryption at rest vs in transit explains why the hashes used for storage are deliberately slow, the opposite of what a hash table needs.

Quotable summary

A hash table computes an array index from a key using a hash function, which is why lookup cost does not grow with the number of entries. Collisions are unavoidable because infinitely many keys map to finitely many indexes; chaining stores colliding entries in a list per bucket, while open addressing probes for the next free slot. Lookup is O(1) on average and O(n) in the worst case, which occurs with a poor hash function, a high load factor, or adversarial input. The load factor governs performance, and implementations typically resize at around 0.75. Keys must be hashable and immutable, because mutating a key changes its hash and makes the entry unreachable.

Frequently asked questions

What is a hash table in simple terms?
A hash table is a structure that stores values by key and finds them almost instantly. It runs the key through a hash function to get a number, uses that number as an array index, and stores the value there, so lookup does not require scanning.
Why is hash table lookup O(1)?
Because the hash function computes the storage location directly from the key, in constant time, regardless of how many entries exist. The array index is calculated, not searched for, so the cost does not grow with the number of items.
What is a hash collision?
A collision happens when two different keys produce the same array index. It is unavoidable because there are more possible keys than buckets. Hash tables handle it by storing multiple entries per bucket (chaining) or by probing for the next free slot (open addressing).
What is a good load factor for a hash table?
Around 0.75 is the common default. Below that, memory is wasted on empty buckets; above it, collisions become frequent and lookups slow down. Most implementations resize and rehash when the load factor crosses their threshold.
Can any type be used as a hash table key?
Only types that can be hashed consistently and compared for equality, and that are immutable. In JavaScript, objects and arrays are compared by reference, so two structurally identical objects are different keys. In Python, only hashable types like strings, numbers, and tuples can be keys.
What is the difference between a hash table and a hash map?
They are the same structure. Hash table is the general computer science term; hash map is the name used by many standard libraries, such as Java's HashMap or Rust's HashMap. Some languages use hash table for the concept and map for the interface.