Hash Tables: Hash Functions, Separate Chaining & Open Addressing0%
Hash Map Patterns: Two Sum, Frequency Counters & Subarray Sums

Hash Tables: Hash Functions, Separate Chaining & Open Addressing

Beginner12 min read•Updated: Jul 11, 2026
Study MaterialsCheatsheet

Hash Tables: Hash Functions, Separate Chaining & Open Addressing

The Hash Table (Hash Map) is arguably the single most important data structure in real-world software engineering. By translating arbitrary keys (like strings, objects, or URLs) into array indices using a Hash Function, hash tables achieve average $O(1)$ constant-time insertion, deletion, and lookup.

1. Real-World Analogy: The Coat Check / Valet Parking

Imagine parking your car with a luxury hotel valet:

  • You don't search all 5,000 cars in the garage when you return.
  • You hand the valet your unique numbered ticket (Ticket #342).
  • The ticket number points directly to Locker 342 where your car keys are hanging!
  • The Hash Function is the valet who maps your license plate to ticket number 342.

2. Anatomy of a Hash Table

  1. 1
    Key: The identifier you want to store (e.g. 'username').
  2. 2
    Hash Function: A deterministic algorithm that converts the key into a large integer (hash code), which is then mapped to an array bucket via hash(key) % table_size.
  3. 3
    Bucket Array: The internal array where key-value pairs are stored.

3. The Collision Problem & Resolution Strategies

By the Pigeonhole Principle, because there are infinitely more possible string keys than available array buckets, two different keys will eventually hash to the exact same bucket index. This is called a Collision.

Output
hash("John Smith") % 10 = Bucket 2
hash("Sandra Dee") % 10 = Bucket 2 <-- COLLISION!

Strategy 1: Separate Chaining (Linked Lists / Trees)

Each bucket in the array holds a linked list (or balanced red-black tree in Java 8+). When a collision occurs, the new key-value pair is appended to that bucket's linked list:

Output
Bucket 2: [John Smith: 555-1234] -> [Sandra Dee: 555-8765] -> NULL

Strategy 2: Open Addressing (Linear Probing)

All entries are stored directly in the bucket array itself. If bucket[index] is already occupied:

  • Linear Probing: Step forward sequentially: check index + 1, index + 2, index + 3 until an empty cell is found.
  • Quadratic Probing: Jump by squares: $i + 1^2, i + 2^2, i + 3^2 \dots$
  • Double Hashing: Use a secondary hash function to calculate jump intervals.

4. Multi-Language Implementations: Custom Hash Map with Separate Chaining

Python 3 Implementation:

Visual Architecture & Process Flow

How data and code flow step-by-step

Flowchart
Step 1
def _hash
self, key: str
Step 2
int:

Modern JavaScript / TypeScript:

TypeScript
class EntryNode<K, V> {
key: K;
value: V;
next: EntryNode<K, V> | null = null;
constructor(key: K, value: V) {
this.key = key;
this.value = value;
}
}
 
export class SimpleHashMap<K extends string, V> {
private capacity: number;
private buckets: (EntryNode<K, V> | null)[];
 
constructor(capacity: number = 32) {
this.capacity = capacity;
this.buckets = new Array(capacity).fill(null);
}
 
private hash(key: string): number {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = (hash * 31 + key.charCodeAt(i)) % this.capacity;
}
return hash;
}
 
public set(key: K, value: V): void {
const idx = this.hash(key);
let curr = this.buckets[idx];
 
while (curr) {
if (curr.key === key) {
curr.value = value;
return;
}
curr = curr.next;
}
 
const newNode = new EntryNode(key, value);
newNode.next = this.buckets[idx];
this.buckets[idx] = newNode;
}
 
public get(key: K): V | undefined {
const idx = this.hash(key);
let curr = this.buckets[idx];
while (curr) {
if (curr.key === key) return curr.value;
curr = curr.next;
}
return undefined;
}
}

5. Load Factor & Dynamic Resizing

The Load Factor ($\alpha$) measures how full the hash table is: $$\alpha = \frac{\text{Number of Stored Entries } (n)}{\text{Total Number of Buckets } (k)}$$

  • When $\alpha > 0.75$, the probability of collisions skyrockets.
  • Hash tables automatically rehash and double their bucket capacity, redistributing all elements into the new larger array to maintain average $O(1)$ constant time.
Interactive Quiz

Multiple Choice Questions

Question 1
What is the average time complexity for searching, inserting, and deleting elements in a well-distributed Hash Table?
Question 2
What is a "Hash Collision"?
Question 3
How does the "Separate Chaining" technique handle hash collisions?
Question 4
What happens to the worst-case time complexity of a Hash Table if an atrocious hash function maps every single key into the exact same bucket index 0?
Question 5
What is the standard "Load Factor" threshold at which hash tables (like Java HashMap) trigger a resize and rehash?
Next Lesson

Hash Map Patterns: Two Sum, Frequency Counters & Subarray Sums

Continue learning with hands-on practice, examples, and exercises in the upcoming topic.

Related Lessons

Previous LessonNext Lesson
Queues: FIFO Mechanics, Circular Buffers & Double-Ended Queues (Deque)Hash Map Patterns: Two Sum, Frequency Counters & Subarray Sums

Practice Quiz

Test your understanding of this lesson with 5 questions. Each question has one correct answer.

PreviousNext
PrevNext