If arrays are “index in, value out”, hash tables are ”anything in, value out, still fast.” That trick — turning an arbitrary key into an array index — is what makes dictdict and setset the single most-used tools in interview Python.

What you’ll learn

• What hashing actually does: key → hash → bucket index.
• Collisions, and the two standard fixes: chaining and open addressing.
• Why dictdict/setset give $O(1)$ average lookup, and the worst case.
• Core idioms: getget, setdefaultsetdefault, defaultdictdefaultdict, CounterCounter.
• The frequency-table and seen-set patterns, runnable.
• LeetCode-style problems to drill the pattern.

Hashing: key to bucket, in O(1)

A hash table is really just an array (buckets) plus a hash function that turns any key into an index into that array. Insert and lookup both start the same way: hash the key, jump straight to that bucket — no scanning required.

# Python exposes the hash function directly via hash()
print(hash("apple"))
print(hash(42))
print(hash((1, 2, 3)))   # tuples are hashable, lists are NOT
 
# a tiny hash table, built by hand, to show the idea
num_buckets = 8
 
def bucket_for(key):
    return hash(key) % num_buckets
 
for key in ["apple", "banana", "cherry", "date"]:
    print(f"{key:<8} -> bucket {bucket_for(key)}")

# Python exposes the hash function directly via hash()
print(hash("apple"))
print(hash(42))
print(hash((1, 2, 3)))   # tuples are hashable, lists are NOT
 
# a tiny hash table, built by hand, to show the idea
num_buckets = 8
 
def bucket_for(key):
    return hash(key) % num_buckets
 
for key in ["apple", "banana", "cherry", "date"]:
    print(f"{key:<8} -> bucket {bucket_for(key)}")

Collisions: two keys, one bucket

With a fixed number of buckets, two different keys will eventually hash to the same index — a collision. There are two classic fixes:

• Chaining — each bucket holds a small list; colliding keys just get appended to that bucket’s list.
• Open addressing — on a collision, probe forward to the next free slot instead of using a list per bucket.

CPython’s dictdict/setset use an open-addressing variant internally, but the concept is the same either way: collisions are handled inside the table, invisibly to you.

  graph TD
    A["Hash keys 'apple' and 'grape' collide -> both hash to bucket 3"] --> B["Chaining"]
    A --> C["Open addressing"]

    B --> B1["Bucket 3 holds a small list: ['apple', 'grape']"]
    C --> C1["'apple' goes in bucket 3; 'grape' probes forward to bucket 4"]

dictdict / setset: O(1) average, in practice

nums = list(range(50_000))
lookup_set = set(nums)
target = 49_999
 
# list membership: O(n) -- must scan, possibly the whole thing
found_in_list = target in nums
 
# set membership: O(1) average -- hash once, check one bucket
found_in_set = target in lookup_set
 
print("found in list:", found_in_list)
print("found in set: ", found_in_set)
print("same answer, wildly different cost per lookup")

nums = list(range(50_000))
lookup_set = set(nums)
target = 49_999
 
# list membership: O(n) -- must scan, possibly the whole thing
found_in_list = target in nums
 
# set membership: O(1) average -- hash once, check one bucket
found_in_set = target in lookup_set
 
print("found in list:", found_in_list)
print("found in set: ", found_in_set)
print("same answer, wildly different cost per lookup")

Core dict idioms

Four small idioms replace almost every “check if key exists first” pattern you’d otherwise write by hand.

from collections import defaultdict, Counter
 
d = {"a": 1, "b": 2}
 
# get: lookup with a default, no KeyError, no "if key in d" needed
print(d.get("a"))          # 1
print(d.get("z"))          # None
print(d.get("z", 0))       # 0
 
# setdefault: get-or-insert in one call
d.setdefault("c", []).append(10)
d.setdefault("c", []).append(20)
print(d)   # {"a": 1, "b": 2, "c": [10, 20]}
 
# defaultdict: every missing key gets a default value automatically
groups = defaultdict(list)
for word in ["cat", "car", "dog", "do"]:
    groups[word[0]].append(word)
print(dict(groups))
 
# Counter: a frequency table in one call
freq = Counter("mississippi")
print(freq)
print(freq.most_common(2))

from collections import defaultdict, Counter
 
d = {"a": 1, "b": 2}
 
# get: lookup with a default, no KeyError, no "if key in d" needed
print(d.get("a"))          # 1
print(d.get("z"))          # None
print(d.get("z", 0))       # 0
 
# setdefault: get-or-insert in one call
d.setdefault("c", []).append(10)
d.setdefault("c", []).append(20)
print(d)   # {"a": 1, "b": 2, "c": [10, 20]}
 
# defaultdict: every missing key gets a default value automatically
groups = defaultdict(list)
for word in ["cat", "car", "dog", "do"]:
    groups[word[0]].append(word)
print(dict(groups))
 
# Counter: a frequency table in one call
freq = Counter("mississippi")
print(freq)
print(freq.most_common(2))

Pattern: frequency table

Counting occurrences is the single most common warm-up interview problem, and it’s always the same shape.

def char_frequencies(s):
    freq = {}
    for c in s:
        freq[c] = freq.get(c, 0) + 1   # O(1) per character
    return freq
 
 
print(char_frequencies("hello"))

def char_frequencies(s):
    freq = {}
    for c in s:
        freq[c] = freq.get(c, 0) + 1   # O(1) per character
    return freq
 
 
print(char_frequencies("hello"))

Pattern: seen-set (duplicate / pair detection)

Keeping a running setset of “things seen so far” turns an $O(n^2)$ nested scan into a single $O(n)$ pass.

def has_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:      # O(1) average
            return True
        seen.add(x)         # O(1) average
    return False
 
 
def two_sum(nums, target):
    seen = {}   # value -> index
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]
        seen[x] = i
    return []
 
 
print(has_duplicate([4, 5, 6, 4]))
print(has_duplicate([1, 2, 3]))
print(two_sum([2, 7, 11, 15], 9))

def has_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:      # O(1) average
            return True
        seen.add(x)         # O(1) average
    return False
 
 
def two_sum(nums, target):
    seen = {}   # value -> index
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]
        seen[x] = i
    return []
 
 
print(has_duplicate([4, 5, 6, 4]))
print(has_duplicate([1, 2, 3]))
print(two_sum([2, 7, 11, 15], 9))

two_sumtwo_sum finds the answer in one pass: for each number, check if the value that would complete the target has already been seen — no nested loop needed.

Complexity summary

LeetCode problem set

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 1 — Two Sum · Easy

Problem. Given an array numsnums and a targettarget, return the indices of the two numbers that add up to targettarget. Exactly one solution exists, and you may not use the same element twice.

Constraints. 2 <= len(nums) <= 10^42 <= len(nums) <= 10^4, -10^9 <= nums[i], target <= 10^9-10^9 <= nums[i], target <= 10^9. Can you do better than $O(n^2)$?

Examples. [2,7,11,15], target = 9[2,7,11,15], target = 9 gives [0,1][0,1] · [3,2,4], target = 6[3,2,4], target = 6 gives [1,2][1,2] · [3,3], target = 6[3,3], target = 6 gives [0,1][0,1]

LC 217 — Contains Duplicate · Easy

Problem. Return TrueTrue if any value appears at least twice.

Constraints. 1 <= len(nums) <= 10^51 <= len(nums) <= 10^5, -10^9 <= nums[i] <= 10^9-10^9 <= nums[i] <= 10^9.

Examples. [1,2,3,1][1,2,3,1] gives TrueTrue · [1,2,3,4][1,2,3,4] gives FalseFalse

seen = set()
for n in nums:
    if n in seen:
        return True
    seen.add(n)
return False

seen = set()
for n in nums:
    if n in seen:
        return True
    seen.add(n)
return False

LC 383 — Ransom Note · Easy

Problem. Return TrueTrue if ransomNoteransomNote can be built from the letters in magazinemagazine, using each letter at most as many times as it appears there.

Constraints. 1 <= len(ransomNote), len(magazine) <= 10^51 <= len(ransomNote), len(magazine) <= 10^5, lowercase letters.

Examples. ("a", "b")("a", "b") gives FalseFalse · ("aa", "ab")("aa", "ab") gives FalseFalse · ("aa", "aab")("aa", "aab") gives TrueTrue

Recap

• A hash table maps key -> bucket index via hash(key)hash(key), giving O(1)-style access without scanning.
• Collisions are handled internally, via chaining (list per bucket) or open addressing (probe to the next slot) — CPython uses an open-addressing scheme for dictdict/setset.
• dictdict/setset give $O(1)$ average membership, insert, and delete; only hashable (immutable) types can be keys or set elements.
• getget, setdefaultsetdefault, defaultdictdefaultdict, and CounterCounter cover almost every “check existence first” pattern.
• Frequency tables and seen-sets turn $O(n^2)$ nested scans into a single $O(n)$ pass — the single highest-leverage pattern in easy interview problems.

You’ve now covered the core linear data structures. Next up in Phase 3: trees, graphs, and heaps — structures built from these same building blocks.