# Hash Tables, Trees and Heaps — Time & Space Complexity (Big-O)

Source: https://www.skillbyai.com/en/big-o/d-hash

> Compare the costs of hash tables, balanced search trees and heaps.

## Choosing structure by operation

**Hash tables** (Python `dict` and `set`, Java `HashMap`) give **O(1) average** time for insert, lookup and delete, by hashing keys to buckets. The **worst case** is O(n) if many keys collide, which good hash functions and resizing make rare; Java's HashMap also converts long bucket chains into trees, improving the worst case to O(log n). Hash tables do not keep keys **ordered**. **Balanced binary search trees** (red-black trees, AVL trees, B-trees; Java `TreeMap`, C++ `std::map`) keep keys sorted with **O(log n)** insert, delete and search, plus ordered iteration, minimum and maximum, and range queries. An **unbalanced** BST can degrade to O(n), for example after inserting sorted keys. **Binary heaps** (Python `heapq`, Java `PriorityQueue`) give **O(1)** access to the minimum (or maximum), **O(log n)** insert and remove-min, and build a heap from n items in **O(n)**. Choose by the operations you need most: lookups by key (hash table), order and ranges (balanced tree), or repeatedly taking the smallest (heap).

## Operation costs side by side

Average case unless marked; n is the number of elements.

```text
operation            hash table       balanced BST      binary heap
-------------------  ---------------  ----------------  ----------------
insert               O(1) avg         O(log n)          O(log n)
search by key        O(1) avg         O(log n)          O(n)
delete by key        O(1) avg         O(log n)          O(n) (O(log n) with index)
min / max            O(n)             O(log n)          O(1) peek, O(log n) pop
ordered iteration    not supported    O(n)              not supported
range query          not supported    O(log n + k)      not supported
worst case           O(n) collisions  O(log n)          O(log n)
```

## Lockers, a dictionary and a queue at a clinic

A hash table is a wall of lockers: give the key, open the locker directly. A balanced tree is a printed dictionary: a few page flips to any word and you can read in order. A heap is a clinic triage desk: the most urgent patient is always at the front, but finding a particular patient means asking everyone.

**Quiz:** You need to repeatedly extract the smallest element while inserting new ones. Which structure fits best?

- [ ] Hash table
- [x] Binary heap (priority queue)
- [ ] Unsorted array
- [ ] Linked list

*Answer:* Binary heap (priority queue). Heaps give O(log n) insert and remove-min with O(1) access to the minimum.