Drag across the pigeonholes. Click it, then use ← → to step and Space to play.
A hash function turns each key into a slot number, so a lookup jumps straight to one pigeonhole instead of searching. A set stores keys only; a map (Python's dict) stores key-value pairs. Keys are unique, and they are not kept in any order. When two keys land in the same slot (a collision), they share it; as long as the table stays roomy, every slot holds only a few keys, so insert, remove and search are O(1) on average.
FIG. 9 · Keys drop from the row at the top through the hash function, and the red needle shows the slot it picks: hash(key) % 8. Each pigeonhole holds a short chain of keys. Callouts: A keys, B hash function, C slots, D a collision. For small integers Python's hash(x) is just x, so these are the real numbers; Python's dict resolves collisions by probing for another free slot rather than chaining, but the cost works out the same.
def frequency(nums): # or: collections.Counter(nums)
count = {}
for x in nums:
count[x] = count.get(x, 0) + 1
return count
def has_duplicate(nums): # Contains Duplicate
seen = set()
for x in nums:
if x in seen:
return True
seen.add(x)
return False
def two_sum(nums, target): # store value -> index
idx = {}
for i, x in enumerate(nums):
if target - x in idx:
return [idx[target - x], i]
idx[x] = i
def isAnagram(s, t): # LeetCode 242
if len(s) != len(t):
return False
count = {}
for c in s:
count[c] = count.get(c, 0) + 1 # count up
for c in t:
if count.get(c, 0) == 0:
return False # t has an extra c
count[c] -= 1 # count down
return True
def longestConsecutive(nums): # LeetCode 128
seen = set(nums) # O(n) to build
best = 0
for x in seen:
if x - 1 not in seen: # x starts a run
y = x
while y + 1 in seen:
y += 1
best = max(best, y - x + 1)
return best
s = "anagram", t = "nagaram". Count every letter of s up, then every letter of t down; if a count would drop below zero, t has a letter s doesn't. No sorting needed. Trigger: "anagram", "same characters".
nums = [100, 4, 200, 1, 3, 2]. Sorting would cost O(n log n); a set does it in O(n): only start counting at x when x − 1 is missing, then step x + 1, x + 2, … with O(1) lookups. Answer: 4 (1, 2, 3, 4). Note the collision: 100 and 4 both land in slot 4.
| Operation | Average | Worst | Why |
|---|---|---|---|
| Insert, remove, search (in) | O(1) | O(n) | One hash picks the slot; the chain there is short because the table grows (and re-hashes everything) before it gets crowded. If every key collided into one slot, it would be a list scan. |
| Iterate keys in sorted order | O(n log n) | Hashing scatters keys on purpose, so there is no order to read off. sorted(d) has to sort them. Need order and fast updates together? That is a TreeMap (page 6). | |
| Space | O(n) | One entry per distinct key, plus spare empty slots to keep chains short. | |
| Growing the table | O(1) amortized | When it fills past a threshold, a bigger table is allocated and every key re-hashed: O(n) once in a while, like a dynamic array doubling (page 1). | |
Only things whose hash never changes: numbers, strings, tuples. A list can't be a dict key or set member, because changing it would change its hash and it would be lost in the wrong slot. To key on a list, convert it: tuple(lst), or "".join(sorted(word)) for anagram groups.
You only need to know whether something is present.
You need something stored next to each key: a count, an index, a group.
def frequency(nums): # or: collections.Counter(nums)
count = {}
for x in nums:
count[x] = count.get(x, 0) + 1
return count
def has_duplicate(nums): # Contains Duplicate
seen = set()
for x in nums:
if x in seen:
return True
seen.add(x)
return False
def two_sum(nums, target): # store value -> index
idx = {}
for i, x in enumerate(nums):
if target - x in idx:
return [idx[target - x], i]
idx[x] = i