Lesson 3 · Non-linear structures

Hash Tables, Hash Maps, and Hash Sets

A hash table uses a mathematical function to compute an array index directly from a key. It offers average O(1) time complexity for insertions, deletions, and lookups, at the cost of unordered elements and potential collisions.

From Key to Index in One Step

A hash table stores key-value pairs and finds any of them without searching. The mechanism is a hash function that converts a key into an integer, which is reduced modulo the array size to produce a bucket index. Lookup computes the index and reads that slot — no comparison against other keys, no traversal.

That is the whole idea, and it is why the operation is O(1) on average rather than O(log n): the cost does not grow with the number of entries, because the position is computed rather than located.

A good hash function needs three properties. It must be deterministic — the same key always yields the same value, which is why mutable objects make dangerous keys. It must distribute uniformly, spreading keys across buckets so no bucket becomes a hotspot. And it must be fast, since it runs on every single operation; a cryptographically strong hash is far too slow here.

Java's String.hashCode illustrates the shape: h = 31·h + c for each character, a polynomial accumulation where the odd multiplier and overflow together scramble the bits. Note it is not random — it is a fixed function that happens to spread typical inputs well.

The equality contract is the part that causes real bugs. If two keys are equal they must hash identically, or a lookup will probe the wrong bucket and report a stored key as missing. In Java, overriding equals without overriding hashCode produces exactly this failure, and it is why the two must always be changed together. The converse is not required — unequal keys may share a hash, which is the collision case below.

Hash the key, reduce modulo the array size, index the bucket
Deterministic, uniformly distributed, and fast — all three matter
Equal keys must hash equally, or lookups silently fail
Mutating a key after insertion makes it unfindable

Collisions Are Certain

Two distinct keys mapping to the same bucket is a collision, and it is not an edge case to be avoided — it is a mathematical certainty. There are infinitely many possible keys and finitely many buckets, so collisions must occur.

They occur far sooner than intuition suggests. By the birthday paradox, a table with 365 buckets holding just 23 random keys already has a 50% chance of a collision. Any hash table design must therefore handle them as a normal case.

Separate chaining makes each bucket a container — usually a linked list — holding every entry that hashed there. Insertion appends; lookup hashes to the bucket then scans the chain comparing keys. It is simple, tolerates a load factor above 1, and deletion is trivial.

Its weakness is that chains are pointer-chasing. Java's HashMap mitigates this by converting a chain to a balanced tree once it exceeds 8 entries, capping the worst case at O(log n) per bucket instead of O(n).

Open addressing keeps everything in the array itself. On a collision it probes for another free slot by a fixed rule. Linear probing tries the next slot, then the next — excellent for cache locality since it reads adjacent memory, but it suffers primary clustering, where occupied runs grow and lengthen future probes. Quadratic probing steps by 1, 4, 9, … which breaks up those clusters but can fail to visit every slot unless the table size and step are chosen carefully. Double hashing uses a second hash to pick the step size, giving the best distribution at the cost of another hash computation.

Open addressing has one genuinely awkward consequence: deletion cannot simply clear a slot. Doing so breaks the probe chain, and entries beyond the gap become unreachable. The standard fix is a tombstone — a marker meaning 'nothing here, but keep probing' — which accumulates and requires periodic rehashing to clear.

Collision strategies compared
Strategy	Where entries live	Strength	Weakness
Separate chaining	A list per bucket	Simple; load factor may exceed 1	Pointer chasing, extra memory
Linear probing	The next free slot	Best cache locality	Primary clustering
Quadratic probing	Slot + 1, 4, 9, …	Breaks up clusters	May not probe every slot
Double hashing	Step from a second hash	Best distribution	A second hash per probe

Collisions are certain — the birthday paradox makes them early too
Chaining stores a list per bucket; probing finds another array slot
Linear probing is cache-friendly but clusters
Open addressing needs tombstones, because clearing a slot breaks probes

Load Factor and Rehashing

The load factor is entries divided by buckets, and it is the single number governing a hash table's performance. A near-empty table wastes memory; a crowded one collides constantly.

With chaining, the average chain length is the load factor, so a load factor of 0.75 means most lookups compare against one or two keys. With open addressing the relationship is far sharper: expected probes for linear probing grow roughly as (1 + 1/(1−α)²)/2, which is about 8.5 probes at α = 0.9 and unbounded as α approaches 1. Open addressing must stay well below full, typically under 0.7, while chaining tolerates more.

When the load factor crosses a threshold, the table rehashes: allocate a larger array — usually double — and reinsert every entry. Reinsertion is required rather than copying, because the bucket index depends on the array size, so every key's position changes.

Rehashing is O(n), and it is why insertion is amortised O(1) rather than guaranteed. Most insertions are constant; one occasionally rebuilds the entire table. For latency-sensitive code that pause is a real problem, and the mitigation is to size the table up front when the count is roughly known — Java's new HashMap<>(expectedSize) exists for exactly this.

The doubling policy is what makes the amortisation work: each rehash costs more but happens exponentially less often, so total rehashing work across n insertions stays O(n).

Table size interacts with the hash. With a power-of-two size the modulo becomes a bitmask — very fast, but it uses only the low bits, so a hash with poor low-bit entropy clusters badly. Java addresses this by XOR-ing the high bits down before masking. A prime size mixes all bits naturally but requires a slower modulo operation.

Load factor = entries ÷ buckets, and it drives everything
Chaining tolerates ~1; open addressing needs to stay under ~0.7
Rehashing reinserts every entry because indices depend on table size
Insertion is amortised O(1); pre-size the table to avoid the pause

Key reference

Terms, operations, and practical uses

Core vocabulary

Hash FunctionAn algorithm that converts a key of any size into a fixed-size integer index.
BucketA specific slot in the hash table's underlying array where values are stored.
CollisionWhen two distinct keys are mapped to the exact same bucket index by the hash function.

Collision resolution

Separate ChainingHandling collisions by storing a linked list of entries at each bucket.
Open AddressingHandling collisions by probing forward in the array to find the next empty bucket.
Linear ProbingThe simplest open addressing method: checking buckets one by one (i+1, i+2) until an empty spot is found.

Performance

Load FactorThe ratio of stored items to available buckets. High load factors increase collision rates.
RehashingCreating a larger underlying array and recalculating bucket indexes for all existing elements.
Amortized O(1)While rehashing is an O(N) operation, it happens so rarely that the average cost per insertion remains O(1).

Implementation

Insert keys into a hash table with chaining

def insert(hash_table, key):
    bucket = key % 5
    hash_table[bucket].append(key)

table = [[] for _ in range(5)]
insert(table, 15)
insert(table, 23)
insert(table, 10)
print('Bucket 0: ' + str(table[0]) + ', Bucket 3: ' + str(table[3]))

#include <iostream>
#include <vector>
using namespace std;
void insert(vector<vector<int>>& hashTable, int key) {
    int bucket = key % 5;
    hashTable[bucket].push_back(key);
}
int main() {
    vector<vector<int>> table(5);
    insert(table, 15);
    insert(table, 23);
    insert(table, 10);
    cout << "Bucket 0: [";
    for (size_t i = 0; i < table[0].size(); i++) {
        if (i) cout << ", ";
        cout << table[0][i];
    }
    cout << "], Bucket 3: [";
    for (size_t i = 0; i < table[3].size(); i++) {
        if (i) cout << ", ";
        cout << table[3][i];
    }
    cout << "]\n";
}

import java.util.*;
public class Main {
    static void insert(ArrayList<LinkedList<Integer>> hashTable, int key) {
        int bucket = key % 5;
        hashTable.get(bucket).add(key);
    }
    public static void main(String[] args) {
        ArrayList<LinkedList<Integer>> table = new ArrayList<>();
        for (int i = 0; i < 5; i++) table.add(new LinkedList<>());
        insert(table, 15);
        insert(table, 23);
        insert(table, 10);
        System.out.println("Bucket 0: " + table.get(0) + ", Bucket 3: " + table.get(3));
    }
}

Watch it run

Step through it

Running on Keys: 15, 23, 10 into 5 buckets

Output

Read all 7 Steps

Initialize table Start with an array of 5 empty buckets.
Hash 15 15 % 5 = 0. The key maps to bucket 0.
Insert 15 Append 15 to the list at bucket 0.
Hash 23 23 % 5 = 3. The key maps to bucket 3.
Insert 23 Append 23 to the list at bucket 3.
Hash 10 10 % 5 = 0. The key maps to bucket 0, where 15 is already stored.
Collision: Append 10 Because we use chaining, both items can live in bucket 0 as a linked list.

Hash Table vs HashMap

The question hash table vs hashmap has a different answer depending on whether you mean the concept or a specific class, and conflating the two is where the confusion starts.

As concepts they are the same thing. A hash map is a hash table that stores key-value pairs. A hash set is a hash table that stores keys only. All three are the same machinery — hash function, buckets, collision resolution — differing only in what each slot holds.

As classes in Java, they are genuinely different and the distinction is examinable. Hashtable is the legacy class from Java 1.0: every method is synchronized, and it rejects null keys and values. HashMap arrived in Java 1.2, is not synchronised, and permits one null key and any number of null values. HashMap is faster in single-threaded code precisely because it does no locking; for concurrent use the modern answer is neither, but ConcurrentHashMap, which locks per-bin rather than per-table.

Other languages do not carry this baggage. Python's dict, C++'s std::unordered_map, Go's map and JavaScript's Map are all hash tables under one name each — so outside Java, hash table and hash map mean the same thing.

Java: Hashtable vs HashMap vs ConcurrentHashMap
	`Hashtable`	`HashMap`	`ConcurrentHashMap`
Thread-safe	Yes — every method synchronized	No	Yes — per-bin locking
`null` key	Not allowed	One permitted	Not allowed
`null` values	Not allowed	Any number	Not allowed
Introduced	Java 1.0	Java 1.2	Java 5
Use it when	Legacy code only	Single-threaded — the default	Shared across threads

As data structures: hash table, hash map and hash set are the same mechanism
In Java: Hashtable is legacy and synchronized, HashMap is the default
For concurrency use ConcurrentHashMap, not Hashtable
Outside Java the two names are used interchangeably

The Guarantees, and What Breaks Them

The honest statement of complexity is that insertion, lookup, and deletion are O(1) on average and O(n) in the worst case. The worst case occurs when every key hashes to the same bucket, collapsing the table into a single list.

This is not merely theoretical. Because hash functions are public and deterministic, an attacker who controls the keys — form fields, JSON payloads, HTTP headers — can craft thousands that collide deliberately, turning every insertion into O(n) and the request into O(n²). These hash-flooding denial-of-service attacks were demonstrated against most major web frameworks in 2011.

The defence is randomised hashing: seed the hash function with a per-process random value so an attacker cannot predict which keys collide. Python, Ruby, and the JVM all do this now, and Python's PYTHONHASHSEED controls it — which also explains why iteration order of a Python set varies between runs.

Two other properties are worth stating plainly, since they are what you give up for O(1). Hash tables are unordered. Iteration order reflects bucket layout and rehashing history, not insertion or sort order. Anything needing sorted iteration or range queries needs a balanced tree instead, accepting O(log n). Python's dict preserving insertion order is an implementation guarantee from 3.7, not a property of hashing.

And there is memory overhead beyond the entries. A table deliberately keeps empty buckets to stay below its load factor, so it typically occupies 1.3 to 2 times the space of the data it holds.

The common mistakes follow from all of the above: mutating a key after insertion, which strands the entry in the wrong bucket; overriding equals without hashCode; relying on iteration order; and assuming O(1) is a guarantee in latency-critical or adversarial contexts where it is only an average.

Hash table time complexity, by operation
Operation	Average	Worst case	Why the worst case happens
Lookup / search	O(1)	O(n)	Every key lands in one bucket, so the lookup degrades to scanning a list
Insertion	O(1)	O(n)	Same collision collapse; a rehash also costs O(n), amortised to O(1) per insert
Deletion	O(1)	O(n)	The entry must be found first, so it inherits lookup's worst case
Iteration	O(n + m)	O(n + m)	Every bucket is visited, including the empty ones — m is the table size

O(1) average, O(n) worst case when all keys land in one bucket
Crafted colliding keys enable hash-flooding denial of service
Randomised seeds are the defence — and why iteration order varies
Unordered by nature; use a balanced tree for range or sorted queries