Hash Table
A hash table (also called hash map) is a data structure that maps keys to values using a hash function. It provides near-constant-time average performance for insertion, deletion, and lookup by computing an index into an array of buckets from which the desired value can be found.
How it Works
A hash table stores key-value pairs in an array of buckets. When you insert a key, a hash function converts the key into an integer index that determines which bucket the value goes into. To retrieve a value, the same hash function is applied to the key to find the correct bucket instantly.
The hash function is the core of the data structure. A good hash function distributes keys uniformly across all buckets, minimizing the chance of two different keys mapping to the same index. In this visualization we use a simple modular hash: hash(key) = key % numBuckets.
Collision resolution is necessary because multiple keys can hash to the same bucket index. The two most common strategies are:
- Chaining (separate chaining) — Each bucket holds a linked list (or chain) of all entries that hash to that index. On collision, the new entry is simply appended to the chain. This is the approach shown in the visualization below.
- Open addressing — When a collision occurs, the algorithm probes other bucket positions (linear probing, quadratic probing, or double hashing) until an empty slot is found.
Key characteristics of hash tables:
- Average O(1) operations — Insert, search, and delete are all constant time on average, assuming a good hash function and a reasonable load factor.
- Worst case O(n) — If many keys collide into the same bucket, scanning the chain degrades to linear time.
- Load factor — The ratio of stored entries to the number of buckets. When the load factor exceeds a threshold (commonly 0.75), the table is resized (rehashed) to maintain performance.
- Unordered — Hash tables do not maintain insertion order or sorted order of keys. Iteration order is determined by hash values, not logical order.
- Dynamic resizing — To keep operations efficient, hash tables double in size and rehash all entries when the load factor becomes too high.
Hash tables are one of the most widely used data structures in practice. They power dictionaries in Python, objects in JavaScript, HashMaps in Java, and are used internally in databases, caches, symbol tables, and countless other systems.
Interactive Visualization
Experiment with the hash table below. Enter an integer value and click an operation button to see how hashing, insertion, search, and deletion work step by step. Collisions are resolved using chaining (linked lists per bucket).
Code Implementation
Below is a hash table implementation using separate chaining for collision resolution, with insert, search, delete, and display operations in three languages.
class HashTable:
def __init__(self, size=8):
self.size = size
self.buckets = [[] for _ in range(size)]
def _hash(self, key):
"""Compute bucket index from key."""
return key % self.size
def insert(self, key):
"""Insert a key into the hash table. O(1) avg"""
index = self._hash(key)
bucket = self.buckets[index]
# Avoid duplicates
for item in bucket:
if item == key:
return # Already exists
bucket.append(key)
def search(self, key):
"""Search for a key. Returns True/False. O(1) avg"""
index = self._hash(key)
bucket = self.buckets[index]
for item in bucket:
if item == key:
return True
return False
def delete(self, key):
"""Delete a key from the hash table. O(1) avg"""
index = self._hash(key)
bucket = self.buckets[index]
for i, item in enumerate(bucket):
if item == key:
bucket.pop(i)
return True
return False
def display(self):
"""Print the hash table."""
for i, bucket in enumerate(self.buckets):
chain = " -> ".join(str(v) for v in bucket)
print(f"Bucket {i}: {chain if chain else 'empty'}")
# Example usage
ht = HashTable(8)
for val in [15, 42, 8, 23, 7, 31, 50, 19]:
ht.insert(val)
ht.display()
# Bucket 0: 8
# Bucket 1: 42 -> 50
# Bucket 2: ...
print(ht.search(23)) # True
print(ht.search(99)) # False
ht.delete(42)
ht.display()
import java.util.LinkedList;
public class HashTable {
private LinkedList<Integer>[] buckets;
private int size;
@SuppressWarnings("unchecked")
public HashTable(int size) {
this.size = size;
this.buckets = new LinkedList[size];
for (int i = 0; i < size; i++) {
buckets[i] = new LinkedList<>();
}
}
private int hash(int key) {
return ((key % size) + size) % size;
}
/** Insert a key. O(1) average */
public void insert(int key) {
int index = hash(key);
LinkedList<Integer> bucket = buckets[index];
if (!bucket.contains(key)) {
bucket.add(key);
}
}
/** Search for a key. O(1) average */
public boolean search(int key) {
int index = hash(key);
return buckets[index].contains(key);
}
/** Delete a key. O(1) average */
public boolean delete(int key) {
int index = hash(key);
return buckets[index].remove(Integer.valueOf(key));
}
/** Print the hash table. */
public void display() {
for (int i = 0; i < size; i++) {
StringBuilder sb = new StringBuilder();
sb.append("Bucket ").append(i).append(": ");
if (buckets[i].isEmpty()) {
sb.append("empty");
} else {
for (int j = 0; j < buckets[i].size(); j++) {
if (j > 0) sb.append(" -> ");
sb.append(buckets[i].get(j));
}
}
System.out.println(sb.toString());
}
}
public static void main(String[] args) {
HashTable ht = new HashTable(8);
int[] values = {15, 42, 8, 23, 7, 31, 50, 19};
for (int val : values) {
ht.insert(val);
}
ht.display();
System.out.println(ht.search(23)); // true
System.out.println(ht.search(99)); // false
ht.delete(42);
ht.display();
}
}
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
class HashTable {
private:
int size;
vector<list<int>> buckets;
int hash(int key) {
return ((key % size) + size) % size;
}
public:
HashTable(int size = 8) : size(size), buckets(size) {}
// Insert a key. O(1) average
void insert(int key) {
int index = hash(key);
auto& bucket = buckets[index];
if (find(bucket.begin(), bucket.end(), key) == bucket.end()) {
bucket.push_back(key);
}
}
// Search for a key. O(1) average
bool search(int key) {
int index = hash(key);
auto& bucket = buckets[index];
return find(bucket.begin(), bucket.end(), key) != bucket.end();
}
// Delete a key. O(1) average
bool remove(int key) {
int index = hash(key);
auto& bucket = buckets[index];
auto it = find(bucket.begin(), bucket.end(), key);
if (it != bucket.end()) {
bucket.erase(it);
return true;
}
return false;
}
// Print the hash table
void display() {
for (int i = 0; i < size; i++) {
cout << "Bucket " << i << ": ";
if (buckets[i].empty()) {
cout << "empty";
} else {
bool first = true;
for (int val : buckets[i]) {
if (!first) cout << " -> ";
cout << val;
first = false;
}
}
cout << endl;
}
}
};
int main() {
HashTable ht(8);
int values[] = {15, 42, 8, 23, 7, 31, 50, 19};
for (int val : values) {
ht.insert(val);
}
ht.display();
cout << boolalpha;
cout << ht.search(23) << endl; // true
cout << ht.search(99) << endl; // false
ht.remove(42);
ht.display();
return 0;
}
Complexity Analysis
The table below summarizes the time and space complexities for hash table operations with separate chaining.
| Operation | Average Case | Worst Case | Notes |
|---|---|---|---|
| Insert | O(1) | O(n) | Constant time if hash distributes evenly; worst case when all keys collide into one bucket |
| Search | O(1) | O(n) | Hash to the bucket in O(1), then scan the chain; worst case all n keys in one chain |
| Delete | O(1) | O(n) | Same as search: find the element, then remove it from the chain |
| Space | O(n + m) | n entries stored plus m buckets in the underlying array | |
| Resize / Rehash | O(n) | All entries must be rehashed into the new array; amortized O(1) per insert | |
Quiz
Q1. What is the average time complexity of searching for a key in a hash table?
Q2. What happens when two different keys hash to the same bucket index?
Q3. In separate chaining, what data structure is used at each bucket to handle collisions?
Q4. What is the worst-case time complexity of operations on a hash table?
Q5. What is the load factor of a hash table?