DSA — Non-Linear DS

Hash Table

Maps keys to values using a hash function. O(1) average insert, delete, and lookup — the fastest structure for key-value access.

— min read

O(1)Search Avg

O(1)Insert Avg

O(n)Worst

HashFunction

ChainingCollision

// HASH TABLE

Interactive visualization

How It Works

Python Code

Complexity

Quiz

Practice

Hash Function

Convert key to array index: index = hash(key) % size.

idx = hash(key) % table_size

Insert

Store value at computed index.

table[hash(key)] = value

Collision

Two keys same index: use chaining (linked list) or open addressing.

Load Factor

α = n/capacity. Rehash when α > 0.7.

python

# Python dict is a hash table
d = {}
d["name"] = "Alice"     # O(1) insert
val = d["name"]         # O(1) lookup
del d["name"]          # O(1) delete

# Custom hash table with chaining
class HashTable:
    def __init__(self, size=10):
        self.table = [[] for _ in range(size)]
    def put(self, key, val):
        idx = hash(key) % len(self.table)
        self.table[idx].append((key, val))

O(1)

Avg Insert/Get

Hash function maps directly

O(n)

Worst Case

All keys collide (rare in practice)

O(n)

Space

n entries stored

0.7

Load Factor

Rehash threshold for performance

What happens when two keys hash to the same index?

Progress 0 / 5 solved

5 problems · 3 PBC · 2 Startup

#001 Two Sum Google, Amazon PBC →

#022 Group Anagrams Amazon, Google PBC →

#070 LRU Cache Design Cogoport STARTUP →

#091 Top K Frequent Elements Google PBC →

#018 Find Duplicates in Array Cogoport STARTUP →

← Trie Graphs →