Hash Table

A Hash Table is a data structure that stores key-value pairs. It uses a hash function to compute an index from the key, enabling O(1) average-case access.

Core Concept

Key -> Hash Function -> Index -> Value
"name" -> hash("name") -> 3 -> "John"

Hash Function

A hash function converts a key into an array index. A good hash must be:
- Consistent: the same input always produces the same result.
- Uniform: distributes keys evenly across all indices.
- Fast: computed in O(1) time.

# Simple hash function
def simple_hash(key, size):
    return hash(key) % size

Collision Resolution

When two keys produce the same hash, a collision occurs.

1. Chaining

Each slot holds a linked list. Collisions are appended to the linked list.

class HashTableChaining:
    def __init__(self, size=16):
        self.size = size
        self.table = [[] for _ in range(size)]

    def _hash(self, key):
        return hash(key) % self.size

    def put(self, key, value):
        idx = self._hash(key)
        for i, (k, v) in enumerate(self.table[idx]):
            if k == key:
                self.table[idx][i] = (key, value)
                return
        self.table[idx].append((key, value))

    def get(self, key):
        idx = self._hash(key)
        for k, v in self.table[idx]:
            if k == key:
                return v
        raise KeyError(key)

    def delete(self, key):
        idx = self._hash(key)
        for i, (k, v) in enumerate(self.table[idx]):
            if k == key:
                del self.table[idx][i]
                return
        raise KeyError(key)

2. Open Addressing

Collisions are resolved by looking for the next slot in the same array.

Load Factor and Rehashing

Load factor = number of elements / table size. When the load factor exceeds a threshold (usually 0.75), rehashing is performed: a larger new table is created and all elements are moved into it.

Python dict and Java HashMap

# Python dict (Hash Table)
person = {"name": "John", "age": 25}
person["city"] = "New York"
print(person["name"])  # John
del person["age"]

// Java HashMap
import java.util.HashMap;

HashMap<String, Integer> map = new HashMap<>();
map.put("name", 1);
map.get("name");      // 1
map.containsKey("x"); // false

Time Complexity

The O(n) worst case happens when all keys collide (rare with a good hash function).

Use Cases

• Database indexing
• Cache (memoization)
• Symbol table in compilers
• Frequency counting
• Anagram grouping

Hash Tables are very fast for key-based access. Now let's study Binary Trees for hierarchical data.