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.

What is a Hash Table?

A Hash Table (or Hash Map) is a data structure that pairs keys to values. Instead of searching linearly through a list, the hash table uses a 'hash function' to convert a key into a direct array index.

To retrieve a value, the table hashes the key to a bucket and then verifies candidate keys inside that bucket. With a controlled load factor and well-distributed hashes, the expected amount of work remains constant even though collisions are possible.

Stores key-value pairs (Dictionaries/Maps)
Hash Sets only store unique keys without values
A key's hash and equality behaviour must remain stable while stored

Why it is useful

Hash tables provide average O(1) time complexity for insertion, deletion, and lookup operations. This is vastly faster than the O(N) time required by arrays and linked lists for unsorted searching.

This speed makes them useful for caches, frequency counting, symbol tables, deduplication, and membership checks. Databases may offer hash indexes for equality queries, while ordered indexes commonly use B-tree families.

Average O(1) read and write operations
Excellent for counting item frequencies
Replaces slow linear searches in algorithms

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).

Code example

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]))

void insert(vector<vector<int>>& hashTable, int key) {
    int bucket = key % 5;
    hashTable[bucket].push_back(key);
}

static void insert(ArrayList<LinkedList<Integer>> hashTable, int key) {
    int bucket = key % 5;
    hashTable.get(bucket).add(key);
}

InputKeys: 15, 23, 10 into 5 buckets

OutputBucket 0: [15, 10], Bucket 3: [23]

Example

Run the example step by step

Output

Hash Functions and Buckets

A hash function takes an input of any size (like a long string) and produces a fixed-size integer. The table then uses the modulo operator to map that integer into the bounds of its internal array (the 'buckets').

A good hash function is deterministic (same input always gives same output), fast to compute, and distributes keys uniformly across all available buckets to prevent clustering.

Converts keys to array indexes
Must be deterministic and fast
Modulo operator keeps indexes within array bounds

Handling Collisions

Because the number of possible keys is infinite but the array size is finite, two different keys will eventually hash to the same bucket. This is called a collision.

The two main ways to resolve collisions are Separate Chaining (each bucket holds a linked list of entries) and Open Addressing (if a bucket is full, probe forward to the next empty slot).

Collisions happen when two keys share an index
Separate Chaining: lists grow at each bucket
Open Addressing: probe for the next empty space

Load Factor and Rehashing

As more items are added, collisions become more frequent and performance degrades. The 'load factor' is the ratio of stored items to total buckets.

When the load factor exceeds a certain threshold (often 0.75), the hash table allocates a new underlying array—usually double the size—and rehashes every existing item into it.

Load factor = (total items) / (total buckets)
Rehashing restores O(1) performance
Rehashing takes O(N) time but happens infrequently

Time and space costs

On average, insert, delete, and search take O(1) time. However, in the worst case (if all keys hash to the same bucket), operations degrade to O(N).

The space complexity is O(N) to store the N key-value pairs, plus some overhead for empty buckets to maintain a healthy load factor.

Time: O(1) average, O(N) worst case
Space: O(N)
Rehashing introduces an occasional O(N) time penalty

Common mistakes

A major pitfall is using mutable objects (like lists or arrays) as keys. If the object changes after being inserted, its hash value changes, and it becomes unfindable in the table.

Another mistake is assuming hash tables keep items in a sorted order. Most hash maps (like Python's dict before 3.7 or Java's HashMap) offer no guaranteed order.

Using mutable objects as keys
Relying on insertion or sorted order
Ignoring worst-case O(N) security vulnerabilities