Hash Table in Data Structures

A Hash Table (also called a Hash Map) is a data structure that implements an associative array — a structure that maps keys to values. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. Hash tables offer O(1) average-case time complexity for search, insertion, and deletion.

Components of a Hash Table

• Keys: Unique identifiers used to store and retrieve values.
• Values: The data associated with a key.
• Hash Function: Maps a key to an index in the array.
• Buckets / Slots: The array where key-value pairs are stored.
• Collision Resolution Strategy: Handles cases where two keys map to the same index.

How a Hash Table Works

1. Insert: Compute the hash of the key → get an index → store the key-value pair at that index (handling collisions if needed).
2. Search: Compute the hash of the key → get an index → retrieve the value at that index (or traverse the chain/list to find the key).
3. Delete: Compute the hash of the key → get an index → remove the key-value pair from that index.

Collision Resolution Strategies

1. Separate Chaining

Each bucket contains a linked list (or another data structure) of entries that hash to the same index.

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

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

    def insert(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 search(self, key):
        idx = self._hash(key)
        for k, v in self.table[idx]:
            if k == key:
                return v
        return None

    def delete(self, key):
        idx = self._hash(key)
        for i, (k, v) in enumerate(self.table[idx]):
            if k == key:
                self.table[idx].pop(i)
                return True
        return False

2. Open Addressing

All entries are stored in the array itself. When a collision occurs, the algorithm probes for the next available slot.

a. Linear Probing

Checks the next slot sequentially: h(key, i) = (h(key) + i) % size.

class HashTableLinearProbing:
    def __init__(self, size=10):
        self.size = size
        self.keys = [None] * size
        self.values = [None] * size

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

    def insert(self, key, value):
        idx = self._hash(key)
        i = 0
        while i < self.size:
            probe = (idx + i) % self.size
            if self.keys[probe] is None or self.keys[probe] == key:
                self.keys[probe] = key
                self.values[probe] = value
                return
            i += 1
        raise Exception("Hash table is full")

    def search(self, key):
        idx = self._hash(key)
        i = 0
        while i < self.size:
            probe = (idx + i) % self.size
            if self.keys[probe] is None:
                return None
            if self.keys[probe] == key:
                return self.values[probe]
            i += 1
        return None

    def delete(self, key):
        idx = self._hash(key)
        i = 0
        while i < self.size:
            probe = (idx + i) % self.size
            if self.keys[probe] is None:
                return False
            if self.keys[probe] == key:
                self.keys[probe] = None
                self.values[probe] = None
                # Note: Use tombstone for better performance in practice
                return True
            i += 1
        return False

b. Quadratic Probing

Uses a quadratic function to find the next slot: h(key, i) = (h(key) + c₁*i + c₂*i²) % size.

c. Double Hashing

Uses a second hash function to determine the step size: h(key, i) = (h₁(key) + i * h₂(key)) % size.

Load Factor and Rehashing

• Load Factor (α): The ratio of the number of entries to the table size: α = n / m where n is the number of entries and m is the table size.
• Rehashing: When the load factor exceeds a threshold (typically 0.75), the table is resized (usually doubled) and all entries are re-inserted. This maintains O(1) performance.

def rehash(self):
    old_keys = self.keys
    old_values = self.values
    self.size *= 2
    self.keys = [None] * self.size
    self.values = [None] * self.size
    for key, value in zip(old_keys, old_values):
        if key is not None:
            self.insert(key, value)

Implementation in Python

Using Built-in dict

# Python dictionary (hash table)
hash_table = {}

# Insert
hash_table["apple"] = 10
hash_table["banana"] = 20
hash_table["orange"] = 30

# Search
print(hash_table.get("banana"))  # 20
print(hash_table.get("grape", "Not found"))  # Not found

# Update
hash_table["apple"] = 15

# Delete
del hash_table["orange"]

# Iterate
for key, value in hash_table.items():
    print(f"{key}: {value}")

# Membership
if "apple" in hash_table:
    print("Apple found!")

Custom Implementation with Chaining

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]
        self.count = 0

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

    def insert(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))
        self.count += 1

        # Rehash if load factor > 0.75
        if self.count / self.size > 0.75:
            self._rehash()

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

    def delete(self, key):
        idx = self._hash(key)
        for i, (k, v) in enumerate(self.table[idx]):
            if k == key:
                self.table[idx].pop(i)
                self.count -= 1
                return True
        return False

    def _rehash(self):
        old_table = self.table
        self.size *= 2
        self.table = [[] for _ in range(self.size)]
        self.count = 0
        for bucket in old_table:
            for key, value in bucket:
                self.insert(key, value)

    def __str__(self):
        result = []
        for i, bucket in enumerate(self.table):
            if bucket:
                result.append(f"{i}: {bucket}")
        return "\n".join(result)

# Example usage
ht = HashTable(5)
ht.insert("apple", 10)
ht.insert("banana", 20)
ht.insert("orange", 30)
ht.insert("grape", 40)
print(ht.search("banana"))  # 20
print(ht)

Implementation in Java

Using Built-in HashMap

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        // HashMap
        HashMap map = new HashMap<>();

        // Insert
        map.put("apple", 10);
        map.put("banana", 20);
        map.put("orange", 30);

        // Search
        System.out.println(map.get("banana"));  // 20
        System.out.println(map.getOrDefault("grape", -1));  // -1

        // Update
        map.put("apple", 15);

        // Delete
        map.remove("orange");

        // Iterate
        for (Map.Entry entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }

        // Membership
        if (map.containsKey("apple")) {
            System.out.println("Apple found!");
        }
    }
}

Custom Implementation

import java.util.LinkedList;

class HashTableCustom {
    private class Entry {
        String key;
        int value;
        Entry(String key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private LinkedList[] table;
    private int size;
    private int count;

    @SuppressWarnings("unchecked")
    public HashTableCustom(int size) {
        this.size = size;
        this.count = 0;
        table = new LinkedList[size];
        for (int i = 0; i < size; i++) {
            table[i] = new LinkedList<>();
        }
    }

    private int hash(String key) {
        return Math.abs(key.hashCode()) % size;
    }

    public void insert(String key, int value) {
        int idx = hash(key);
        for (Entry entry : table[idx]) {
            if (entry.key.equals(key)) {
                entry.value = value;
                return;
            }
        }
        table[idx].add(new Entry(key, value));
        count++;
        if ((double) count / size > 0.75) {
            rehash();
        }
    }

    public Integer search(String key) {
        int idx = hash(key);
        for (Entry entry : table[idx]) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
        }
        return null;
    }

    public boolean delete(String key) {
        int idx = hash(key);
        for (Entry entry : table[idx]) {
            if (entry.key.equals(key)) {
                table[idx].remove(entry);
                count--;
                return true;
            }
        }
        return false;
    }

    @SuppressWarnings("unchecked")
    private void rehash() {
        LinkedList[] oldTable = table;
        size *= 2;
        table = new LinkedList[size];
        for (int i = 0; i < size; i++) {
            table[i] = new LinkedList<>();
        }
        count = 0;
        for (LinkedList bucket : oldTable) {
            for (Entry entry : bucket) {
                insert(entry.key, entry.value);
            }
        }
    }
}

Implementation in C++

Using STL unordered_map

#include 
#include 
using namespace std;

int main() {
    unordered_map map;

    // Insert
    map["apple"] = 10;
    map["banana"] = 20;
    map["orange"] = 30;

    // Search
    cout << map["banana"] << endl;  // 20

    // Update
    map["apple"] = 15;

    // Delete
    map.erase("orange");

    // Iterate
    for (auto& pair : map) {
        cout << pair.first << ": " << pair.second << endl;
    }

    // Membership
    if (map.find("apple") != map.end()) {
        cout << "Apple found!" << endl;
    }

    return 0;
}

Custom Implementation

#include 
#include 
#include 
#include 
using namespace std;

class HashTable {
private:
    struct Entry {
        string key;
        int value;
        Entry(string k, int v) : key(k), value(v) {}
    };

    vector> table;
    int size;
    int count;

    int hashFunction(const string& key) {
        int hash = 0;
        for (char c : key) {
            hash = (hash * 31 + c) % size;
        }
        return hash;
    }

    void rehash() {
        vector> oldTable = table;
        size *= 2;
        table.clear();
        table.resize(size);
        count = 0;
        for (auto& bucket : oldTable) {
            for (auto& entry : bucket) {
                insert(entry.key, entry.value);
            }
        }
    }

public:
    HashTable(int s = 10) : size(s), count(0) {
        table.resize(size);
    }

    void insert(const string& key, int value) {
        int idx = hashFunction(key);
        for (auto& entry : table[idx]) {
            if (entry.key == key) {
                entry.value = value;
                return;
            }
        }
        table[idx].push_back(Entry(key, value));
        count++;
        if ((double)count / size > 0.75) {
            rehash();
        }
    }

    int* search(const string& key) {
        int idx = hashFunction(key);
        for (auto& entry : table[idx]) {
            if (entry.key == key) {
                return &entry.value;
            }
        }
        return nullptr;
    }

    bool remove(const string& key) {
        int idx = hashFunction(key);
        for (auto it = table[idx].begin(); it != table[idx].end(); ++it) {
            if (it->key == key) {
                table[idx].erase(it);
                count--;
                return true;
            }
        }
        return false;
    }
};

Complexity Analysis

Note: Worst-case occurs when all keys collide (poor hash function or adversarial input).

Advantages & Disadvantages

Advantages

• Fast Operations: O(1) average-time for search, insert, and delete.
• Flexible Keys: Can use any data type as a key (with proper hashing).
• Dynamic: Can grow/shrink with rehashing.
• Widely Supported: Built into most programming languages.

Disadvantages

• Collisions: Can degrade performance to O(n) in worst case.
• Memory Overhead: May use more memory than other structures.
• Unordered: Does not preserve insertion order (unless using LinkedHashMap).
• Hash Function Quality: Performance depends heavily on the quality of the hash function.

Applications

• Databases: Hash-based indexing for fast lookups.
• Caches: LRU caches, web caches, DNS caching.
• Symbol Tables: Compilers and interpreters store variables.
• Programming Language Implementations: Python dict, Java HashMap, C++ unordered_map.
• Sets: Removing duplicates, membership testing.
• Distributed Systems: Consistent hashing for load balancing.
• Password Storage: Storing hashed passwords.

Common Hash Table Problems

• Two Sum: Find two numbers that sum to target.
• Top K Frequent Elements: Find the k most frequent elements.
• Group Anagrams: Group strings that are anagrams of each other.
• Longest Substring Without Repeating Characters: Use hash map to track character positions.
• Word Pattern: Check if a pattern matches a string.
• LRU Cache: Implement a Least Recently Used cache using a hash map + doubly linked list.

Key Takeaways

• A hash table is a key-value store that provides O(1) average-case operations.
• It uses a hash function to map keys to array indices.
• Collisions are resolved using chaining (linked lists) or open addressing (linear/quadratic probing, double hashing).
• The load factor determines when rehashing is needed to maintain performance.
• Built-in implementations: Python's dict, Java's HashMap, C++'s unordered_map.
• Hash tables are used in databases, caches, compilers, and distributed systems.