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:

1. Key → The identifier (e.g., "username", "email", 42).
2. Hash Function → Converts a key to a numeric index.
3. Bucket/Table → An array that stores the data.

Basic Idea:

index = hash(key)
table[index] = value

This 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") → 4

A 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") → 2

Both 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:

1. Linear Probing

index = hash(key)
if occupied:
    index = index + 1

2. Quadratic Probing

index + 1^2, 2^2, 3^2, ...

3. 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_size

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