DSA — Hash Tables

What is a Hash Table?

A data structure that maps keys to values using a hash function.

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def hash_function(self, key):
        return hash(key) % self.size
    
    def insert(self, key, value):
        index = self.hash_function(key)
        for pair in self.table[index]:
            if pair[0] == key:
                pair[1] = value
                return
        self.table[index].append([key, value])
    
    def get(self, key):
        index = self.hash_function(key)
        for pair in self.table[index]:
            if pair[0] == key:
                return pair[1]
        return None
    
    def delete(self, key):
        index = self.hash_function(key)
        for i, pair in enumerate(self.table[index]):
            if pair[0] == key:
                del self.table[index][i]
                return True
        return False

Operations

Operation	Average	Worst Case
Insert	O(1)	O(n)
Search	O(1)	O(n)
Delete	O(1)	O(n)

Collision Handling

Method	Description
Chaining	Linked lists at each slot
Open Addressing	Find next empty slot

Mini Practice

1. Implement a hash table
2. Handle collisions
3. Use hash table for counting
4. Implement a cache

Up Next

Continue with HashMap — HashMap implementation.