Module 5.1 ⏱ 40 min read ⚡ Hash Tables & Data Structures

Hash Functions & Collision Resolution

Explore direct address tables, hash codes, separate chaining, and open addressing strategies like linear and quadratic probing.

1. Direct Address Tables & Hash Codes

A direct address table maps keys directly to array indices. While providing $O(1)$ constant-time insertions, deletions, and lookups, it requires massive amounts of memory when the universe of possible keys is extremely large compared to the actual stored elements.

To overcome this limitation, hash functions compress large or arbitrary keys into valid indices within a fixed-size table. A good hash function distributes keys uniformly across table buckets to minimize overlapping indices.

2. Collision Resolution: Chaining vs. Open Addressing

Because the number of possible keys almost always exceeds table capacity, collisions are inevitable (as dictated by the Pigeonhole Principle). Two primary strategies resolve collisions:

Separate Chaining: Each bucket points to a secondary data structure (such as a linked list or dynamic array) storing all entries that hash to that specific index.

Open Addressing: All elements are stored directly within the hash table array itself. When a collision occurs, probes scan for the next available slot using methods like linear probing (`index = (hash + i) % capacity`) or quadratic probing (`index = (hash + i^2) % capacity`).

// C++ Solution: Mini Hash Map with Chaining
#include <vector>
#include <list>
#include <utility>

class MyHashMap {
private:
    int capacity;
    std::vector<std::list<std::pair<int, int>>> buckets;

    int hash(int key) {
        return key % capacity;
    }

public:
    MyHashMap(int cap = 1009) : capacity(cap), buckets(cap) {}
    
    void put(int key, int value) {
        int idx = hash(key);
        for (auto& pair : buckets[idx]) {
            if (pair.first == key) {
                pair.second = value;
                return;
            }
        }
        buckets[idx].push_back({key, value});
    }
    
    int get(int key) {
        int idx = hash(key);
        for (auto& pair : buckets[idx]) {
            if (pair.first == key) return pair.second;
        }
        return -1;
    }
    
    void remove(int key) {
        int idx = hash(key);
        buckets[idx].remove_if([key](const std::pair<int, int>& p) {
            return p.first == key;
        });
    }
};
            

# Python Solution: Mini Hash Map with Chaining
class MyHashMap:
    def __init__(self, capacity: int = 1009):
        self.capacity = capacity
        self.buckets = [[] for _ in range(capacity)]

    def _hash(self, key: int) -> int:
        return key % self.capacity

    def put(self, key: int, value: int) -> None:
        idx = self._hash(key)
        for pair in self.buckets[idx]:
            if pair[0] == key:
                pair[1] = value
                return
        self.buckets[idx].append([key, value])

    def get(self, key: int) -> int:
        idx = self._hash(key)
        for pair in self.buckets[idx]:
            if pair[0] == key:
                return pair[1]
        return -1

    def remove(self, key: int) -> None:
        idx = self._hash(key)
        self.buckets[idx] = [pair for pair in self.buckets[idx] if pair[0] != key]
            

// Java Solution: Mini Hash Map with Chaining
import java.util.LinkedList;

class MyHashMap {
    private static class Node {
        int key, value;
        Node(int k, int v) { key = k; value = v; }
    }

    private int capacity;
    private LinkedList<Node>[] buckets;

    public MyHashMap() {
        capacity = 1009;
        buckets = new LinkedList[capacity];
        for (int i = 0; i < capacity; i++) {
            buckets[i] = new LinkedList<>();
        }
    }

    private int hash(int key) {
        return key % capacity;
    }

    public void put(int key, int value) {
        int idx = hash(key);
        for (Node node : buckets[idx]) {
            if (node.key == key) {
                node.value = value;
                return;
            }
        }
        buckets[idx].add(new Node(key, value));
    }

    public int get(int key) {
        int idx = hash(key);
        for (Node node : buckets[idx]) {
            if (node.key == key) return node.value;
        }
        return -1;
    }

    public void remove(int key) {
        int idx = hash(key);
        buckets[idx].removeIf(node -> node.key == key);
    }
}
            

3. Homework & Quiz Overview

To lock in your mastery, complete the implementation exercises for building your own mini hash map with custom collision handling mechanisms.

Quick Check: Test Your Intuition

What is the primary drawback of linear probing in open addressing hash tables?