learningto/pass

Hash Tables

EasyData Structures

Hash tables trade space for time, turning O(n) searches into O(1). They appear in almost every interview problem. Master frequency counting, two-sum patterns, and grouping.

AVG TIME
O(1)
SPACE
O(n)
BEST
O(1)
WORST
O(n)

Key Concepts

  • 1collections.Counter and defaultdict are critical Python tools
  • 2Anagram grouping: sort the word as the key
  • 3Subarray sum equals k: prefix sum + hash map
  • 4LRU cache: dict + doubly linked list (or use OrderedDict)
  • 5Collision resolution: chaining vs. open addressing

In Python

Concept to Code- 4 structures for this topic
declare
seen = {}  # or seen = dict()
common ops
seen[key] = val
O(1)
key in seen
O(1)
seen.get(key, default)
O(1)
del seen[key]
O(1)
seen.keys()
O(n)
seen.items()
O(n)
say in interview
"I'll use a hash map for O(1) lookups"
In Python, dict preserves insertion order (since 3.7). In interviews, don't rely on this unless asked.

Math You Need For This

A row of numbered mailboxes. To deliver mail for "Alice", compute hash("Alice") % 100 to get box number 42. To retrieve it later, compute the same thing. No searching needed.

Required concepts
Key math ideas
1 / 3

Constant time - O(1)

No matter how large the input is, this operation always takes the same amount of time. The size of n simply does not matter.

Visual: A perfectly flat horizontal line on a graph. The line never rises no matter how far right you go.

Think of it this way: Looking up a word in a dictionary if you already know the exact page number. It does not matter how thick the dictionary is.

For algorithms: Accessing array[3] is O(1) because the computer calculates the memory address directly: start + 3 * item_size. One calculation, done.

Interactive 3D Visualization

Hash Table
Insert: O(1)*Lookup: O(1)*Space: O(n)
Drag to orbit - Scroll to zoom

Watch It Run

Two Sum - Hash Map Approach
The classic hash map pattern. Store what you've seen, check complements in O(1).
SPEED
1 / 10
Your data
algorithm.py
1>def two_sum(nums, target):
2  seen = {}
3  for i, num in enumerate(nums):
4  complement = target - num
5  if complement in seen:
6  return [seen[complement], i]
7  seen[num] = i
8  return []
array visualization
2[0]
7[1]
11[2]
15[3]
0
1
2
3
i

We're starting the two_sum function. Our inputs are nums=[2, 7, 11, 15] and target=9. The goal: find two numbers that add up to 9.

VariablesStep 1 of 10 (setup)
nums=[271115]
target=9
Spaceplay/pause← →step+ -speed

Interactive Playground

Experiment hands-on before writing a single line in the practice editor. Try different inputs and watch the structure behave.

interactive sandbox

Data Structure Playground

Empty hash table - set some key/value pairs

Python Implementation

example.py
Loading...
Now try it yourself
2 challenges with test cases and AI feedback
Practice Now

Complexity Analysis

1481216n²nlog n1n (input size)
COMMON OPERATIONS
Array
Access:O(1)
Search:O(n)
Insert end:O(1)*
Insert mid:O(n)
Hash Map
Get/Set:O(1)*
Delete:O(1)*
Search value:O(n)
Iterate:O(n)
Linked List
Access:O(n)
Search:O(n)
Insert head:O(1)
Delete known:O(1)
Binary Search
Search:O(log n)
Insert:O(log n)
Balanced BST
Search:O(log n)
Insert:O(log n)
Delete:O(log n)
Heap
Peek min/max:O(1)
Push:O(log n)
Pop:O(log n)
Heapify:O(n)
Graph (BFS/DFS)
Traversal:O(V+E)
Dijkstra (heap):O((V+E) log V)
Merge / Quick Sort
Sort:O(n log n)
Space (merge):O(n)
Space (quick):O(log n)

* amortized average case

READY TO TEST YOURSELF?

Put Hash Tables into practice

The best way to lock in what you've learned is to write code. Solve real interview-style problems right now.

Next: Binary Trees
Hash Tables
Next: Binary Trees