Tags
Hash TableData Structure
Problem

1. What is a Hash Table?

A hash table (also called hash map) is a data structure that implements an associative array — a collection of key-value pairs. It uses a hash function to compute an index into an array of buckets, where the desired value can be found in O(1) average time.

Think of it like a dictionary: you look up a word (key) and instantly get its definition (value). No need to search through pages!

2. How It Works

Key "apple"  ──►  hash("apple")  ──►  index 3  ──►  bucket[3] = "red fruit"

┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│  0  │  1  │  2  │  3  │  4  │  5  │  6  │  7  │  ← Array indices
├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│     │     │     │ 🍎  │     │     │     │     │  ← Buckets (chains)
│     │     │     │apple│     │     │     │     │
│     │     │     │:red │     │     │     │     │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
              ↑
        Hash function maps "apple" to index 3
KeyThe identifier you want to store (e.g., "apple", "name", "id")
HashA function that transforms the key into a number: index = hash(key) % tableSize
BucketWhere the key-value pair is stored. Multiple entries can share a bucket (chaining)

3. Collision Handling

A collision occurs when two different keys hash to the same index. There are two main ways to handle this:

Chaining (Used in this tool)

bucket[3]: [apple→red] → [avocado→green]

Each bucket stores a linked list of entries. Search is O(n/m) where n=entries, m=buckets.

Open Addressing

If bucket[3] full, try bucket[4], [5]...
Linear probing, quadratic probing, double hashing

Store the entry in the next available slot. Better cache performance.

4. Key Operations

InsertHash the key, find the bucket, add (key, value) pair. If key exists, update value.
Avg: O(1)Worst: O(n)
SearchHash the key, find the bucket, scan chain for matching key.
Avg: O(1)Worst: O(n)
DeleteHash the key, find the bucket, remove entry from chain.
Avg: O(1)Worst: O(n)
RehashWhen load factor > 0.75, double table size and rehash all entries.
Avg: O(n)Worst: O(n)

5. Time Complexity

OperationBestAverageWorst
InsertO(1)O(1)O(n)
SearchO(1)O(1)O(n)
DeleteO(1)O(1)O(n)
RehashO(n)O(n)O(n)

Worst case occurs when all keys collide to the same bucket (poor hash function or malicious input).

6. Real-World Applications

Database IndexingQuick lookup of records by primary key
CachingStore frequently accessed data (Redis, Memcached)
DeduplicationFind duplicate items in large datasets
Language InterpretersJavaScript objects, Python dicts, Go maps
Routing TablesIP routing, symbol tables in compilers
SetsCheck if element exists: O(1) membership test

7. Knowledge Test

1. What is the average time complexity for searching in a hash table?

2. What happens when two different keys hash to the same index?

3. What triggers a rehash operation?

0 / 3 answered