A Hash Table (also known as a Hash Map) is a data structure that stores data in key–value pairs, allowing very fast lookup, insertion, and deletion — typically O(1) on average.
It is one of the most important data structures in computer science and is used in databases, compilers, caches, interpreters, browsers, operating systems, and more.
Learn data structures and algorithms online
1. What Is a Hash Table?
A hash table works by converting (or hashing) a key into an index, and storing the corresponding value in an array at that index.
It involves three key concepts:
- Key → The identifier (e.g.,
"username","email",42). - Hash Function → Converts a key to a numeric index.
- Bucket/Table → An array that stores the data.
Basic Idea:
index = hash(key)
table[index] = valueThis allows the value to be found again quickly because the same key will hash to the same index.
2. Why Are Hash Tables so Fast?
Hash tables give O(1) time complexity for:
- 🔍 Search
- ➕ Insert
- ❌ Delete
Because the hash function jumps directly to where data is stored — no linear searching required.
Internally:
- No loops needed
- No scanning the whole structure
- Just compute the hash → access the index
3. Components of a Hash Table
(a) Hash Function
A hash function takes a key and returns a number.
Example pseudo-hashing:
hash("cat") → 9
hash("dog") → 2
hash("cow") → 4A good hash function should:
- Distribute keys evenly
- Avoid clustering
- Be fast to compute
(b) Buckets / Slots
The hash table uses an array underneath.
Example (size = 10):
| Index | Value |
|---|---|
| 0 | NULL |
| 1 | NULL |
| 2 | “dog” |
| 3 | NULL |
| 4 | “cow” |
| 9 | “cat” |
4. The Collision Problem
A collision happens when two keys hash to the same index.
Example:
hash("lion") → 2
hash("dog") → 2Both want to occupy index 2.
Hash tables must handle collisions gracefully.
5. Collision Resolution Techniques
There are two major methods.
A. Chaining (Linked List Method)
Each bucket stores a list of items.
Example:
table[2] → ["dog", "lion", ...]Benefits:
- Simple to implement
- Works well even with many collisions
- Table doesn’t need resizing immediately
Drawback:
- Worst-case lookup becomes O(n) if too many items land in one bucket
B. Open Addressing
If index is occupied, search for the next available slot.
Common strategies:
- Linear Probing
index = hash(key)
if occupied:
index = index + 1- Quadratic Probing
index + 1^2, 2^2, 3^2, ...- Double Hashing
Use a second hash function when the first causes a collision.
6. Load Factor & Resizing
Load Factor (LF)
The ratio:
LF = number_of_elements / table_sizeIf load factor becomes too high (e.g., > 0.7):
- Collisions increase
- Performance drops
Solution: resize (typically double the array size), then rehash all keys.
7. Time Complexity
| Operation | Average Case | Worst Case |
|---|---|---|
| Insert | O(1) | O(n) |
| Search | O(1) | O(n) |
| Delete | O(1) | O(n) |
Worst case occurs when all elements land in one bucket.
But with good hashing and resizing, O(1) dominates.
8. Real-World Applications of Hash Tables
✔ Databases (indexing)
✔ Caches (e.g., LRU Cache uses hash map + linked list)
✔ Compilers (symbol tables)
✔ Password storage (using cryptographic hash)
✔ Routing tables in networks
✔ JSON objects & dictionaries
✔ Language features
- Python:
dict - JavaScript:
Map, object keys - Java:
HashMap - C++:
unordered_map
9. Simple Code Examples
JavaScript Example
let table = {};
table["name"] = "Luke";
table["age"] = 30;
console.log(table["name"]); // Luke
Python Example
table = {}
table["name"] = "Luke"
table["age"] = 30
print(table["age"]) # 30
Java Example
import java.util.HashMap;
HashMap<String, Integer> map = new HashMap<>();
map.put("age", 30);
System.out.println(map.get("age"));
10. Advantages & Disadvantages
Advantages
- Super fast lookup
- Easy to implement
- Flexible key–value storage
- Widely supported
Disadvantages
- Requires good hash function
- Collisions slow performance
- Uses more memory
- Worst-case can degrade to O(n)
Summary
A Hash Table is a data structure that:
- Stores key–value pairs
- Uses a hash function to compute fast array indices
- Offers constant-time operations on average
- Requires collision resolution
- Powers many modern systems and languages
It is one of the foundational concepts every developer must understand.
About the Author
Latest tech news and coding tips.
