Hashing

No. 09 · SVG · Pigeonholeshash set · hash map · dict · set · Counter

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.

Step 1 / 1
READY
Hashes
Key checks
Table
Result
Codefrequency
def frequency(nums):               # or: collections.Counter(nums)
    count = {}
    for x in nums:
        count[x] = count.get(x, 0) + 1
    return count

Examples

Hash map · LeetCode 242

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".

O(n) timeO(1) spaceone hash per letter; at most 26 keys for lowercase English
Hash set · LeetCode 128

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.

O(n) timeO(n) spaceeach number starts at most one counted run

Time and space

OperationAverageWorstWhy
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 orderO(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).
SpaceO(n)One entry per distinct key, plus spare empty slots to keep chains short.
Growing the tableO(1) amortizedWhen 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).

What can be a key?

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.

Trigger words: when the problem wants a hash map or set

Hash set

  • unique
  • duplicate
  • seen before

You only need to know whether something is present.

Hash map

  • count
  • frequency
  • anagram
  • pair that sums to target

You need something stored next to each key: a count, an index, a group.

Template

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