Hash Tables, 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.

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.

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

• Hash table
• Binary heap (priority queue)
• Unsorted array
• Linked list