Hash Tables in Python: Dict and Set for DSA

A hash table stores data as key-value pairs and finds any of them almost instantly, without searching. It runs the key through a hash function to get a number, then uses that number to jump to a spot in an array. Lookups, inserts and deletes are O(1) on average. In Python, the built-in dict and set are hash tables, which is why they are the most useful tools in data structures and algorithms interviews.

This guide shows how a hash table works by building a tiny one, what makes a key valid, and the patterns (counting, two sum, grouping, prefix sums) that appear again and again.

How a hash table works

Imagine a row of numbered boxes. To store something under a key, you do not search for an empty box. You calculate which box it belongs in, from the key itself. That calculation is the hash function: it turns the key into a number, and the number (modulo the number of boxes) picks the box. To find the item later, you do the same calculation and open that one box. No searching, so the time does not depend on how many items are stored.

Two different keys can land in the same box. This is called a collision, and every hash table needs a way to handle it.

Building a tiny hash table

Here is a small hash table with 4 boxes (buckets). Each bucket holds a list of pairs, so colliding keys simply share a list. This method is called chaining:

class MiniHashTable:
    def __init__(self, size=8):
        self.buckets = [[] for _ in range(size)]

    def _index(self, key):
        return hash(key) % len(self.buckets)

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value
                return
        bucket.append([key, value])

    def get(self, key, default=None):
        for k, v in self.buckets[self._index(key)]:
            if k == key:
                return v
        return default

Now put four integer keys in. Integers hash to themselves in Python, so we can predict the buckets: 1, 5 and 9 all leave a remainder of 1 when divided by 4:

table = MiniHashTable(size=4)
for k in [1, 5, 9, 2]:
    table.put(k, f"v{k}")
print(table.get(5), table.get(9), table.get(3, "missing"))
print([[k for k, v in b] for b in table.buckets])

Output (the second line shows which keys sit in which bucket)

v5 v9 missing
[[], [1, 5, 9], [2], []]

Keys 1, 5 and 9 collided and share bucket 1. Looking up 9 means calculating the bucket, then scanning the short list in it. If the table is kept large enough that the lists stay short, a lookup is effectively one step. Real hash tables resize themselves as they fill up to make sure of that.

One honest caveat: this is a teaching version. Python’s real dict does not use chains. It uses open addressing: on a collision, it probes other slots in the same array by a fixed pattern. The idea (hash, jump, resolve collisions, resize) is the same.

What can be a key?

A key must be hashable: it needs a hash that never changes and can be compared for equality. In practice that means immutable objects. Integers, strings, floats and tuples of them work. Lists, sets and dictionaries do not:

for key in [(1, 2), "text", 3.5, [1, 2]]:
    try:
        {key: "ok"}
        print(type(key).__name__, "works as a key")
    except TypeError:
        print(type(key).__name__, "is unhashable")

Output

tuple works as a key
str works as a key
float works as a key
list is unhashable

If a list could be a key and then changed, its hash would change, and Python would look in the wrong box. Equal objects must have equal hashes, which is why hash(1.0) == hash(1):

print(hash(42), hash(True), hash(1.0) == hash(1))
print(hash((1, 2)) == hash((1, 2)))

Output

42 1 True
True

(String hashes are deliberately randomised each time Python starts, for security, so the number you see for hash("abc") differs between runs. That is fine, since only the consistency within one run matters.) More on why some types cannot be keys in Mutable vs Immutable Objects in Python.

Pattern 1: counting

The most common use: count how often each item occurs. A dictionary maps each item to its count. collections.Counter does it in one line and can rank the results:

from collections import Counter

words = "the cat and the dog and the bird".split()
counts = {}
for w in words:
    counts[w] = counts.get(w, 0) + 1
print(counts)
print(Counter(words).most_common(2))

Output

{'the': 3, 'cat': 1, 'and': 2, 'dog': 1, 'bird': 1}
[('the', 3), ('and', 2)]

One pass through the data gives every count, in O(n). It is the first step of many problems, such as finding the first character that does not repeat:

def first_unique(s):
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    for i, ch in enumerate(s):
        if counts[ch] == 1:
            return i
    return -1

print(first_unique("leetcode"), first_unique("aabb"))

Output

0 -1

Pattern 2: remember what you have seen

Instead of searching backwards through the list for a partner, store what you have already passed in a dictionary or set, and check it in O(1). The classic example is two sum. For each number, you need the value target - x. Have we seen it already?

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return seen[need], i
        seen[x] = i
    return None

print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 2, 4], 6))
print(two_sum([1, 2], 10))

Output

(0, 1)
(1, 2)
None

The dictionary maps each number to its index. This solves in one pass what the brute-force version does with two nested loops (compare with the sorted-list version in Two Pointers Technique in Python: this one works on unsorted data, at the price of extra memory). The same idea checks for duplicates:

def contains_duplicate(nums):
    return len(set(nums)) != len(nums)

print(contains_duplicate([1, 2, 3, 1]), contains_duplicate([1, 2, 3]))

Output

True False

And a set can turn a “search for the next number” loop into a fast one. To find the longest run of consecutive numbers like 1, 2, 3, 4, only start counting at a number that has no predecessor:

def longest_consecutive(nums):
    values = set(nums)
    best = 0
    for x in values:
        if x - 1 not in values:
            length = 1
            while x + length in values:
                length += 1
            best = max(best, length)
    return best

print(longest_consecutive([100, 4, 200, 1, 3, 2]))

Output

4

Pattern 3: grouping by a key

Compute a signature for every item, and use it as the key. Items with the same signature end up in the same list. Anagrams share the same letters, so the sorted letters are a perfect signature:

def group_anagrams(words):
    groups = {}
    for w in words:
        key = "".join(sorted(w))
        groups.setdefault(key, []).append(w)
    return list(groups.values())

print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

Output

[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

setdefault creates the list the first time a key is seen. The same pattern groups people by city, orders by customer, and so on.

Pattern 4: prefix sums

A more advanced but very common trick: how many subarrays add up to k? Keep a running total, and a dictionary of how many times each running total has occurred. A subarray ending here sums to k exactly when total - k has been seen before:

def count_subarrays(nums, k):
    prefix_counts = {0: 1}
    total = count = 0
    for x in nums:
        total += x
        count += prefix_counts.get(total - k, 0)
        prefix_counts[total] = prefix_counts.get(total, 0) + 1
    return count

print(count_subarrays([1, 1, 1], 2), count_subarrays([1, 2, 3], 3))

Output

2 2

For [1, 1, 1] and k = 2 the answer is 2 (the first two items, and the last two). It runs in O(n), and unlike a sliding window it works when the list contains negative numbers.

Time complexity

The worst case happens only when nearly every key collides in the same place, which Python’s hashing makes very unlikely in practice. The full picture for all built-in types is in Time Complexity of Python Data Structures.

Common mistakes

Mistake 1: reading a key that might not exist

counts[ch] += 1 fails with a KeyError the first time you see a character. Use counts.get(ch, 0) + 1, or a defaultdict that supplies a starting value automatically:

from collections import defaultdict

counts = defaultdict(int)
for ch in "hello":
    counts[ch] += 1
print(dict(counts))
plain = {}
try:
    plain["a"] += 1
except KeyError as e:
    print("KeyError", e)

Output

{'h': 1, 'e': 1, 'l': 2, 'o': 1}
KeyError 'a'

Mistake 2: using a list as a key

Convert it to a tuple first: tuple(items).

Mistake 3: searching a list inside a loop

If you write if x in some_list inside a loop, you have hidden an O(n) search inside an O(n) loop. Build a set once, outside the loop.

Mistake 4: relying on the order of a set

Dictionaries remember insertion order, sets do not. If the order matters, use a list, or sort the set.

Mistake 5: forgetting the memory cost

The speed comes from using extra memory. For huge datasets, a set of a hundred million items may not fit.

Try it yourself

Work out each answer first, then open the solution.

1. Return the first value that appears twice in [2, 1, 3, 5, 3, 2].

def first_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return x
        seen.add(x)
    return None

print(first_duplicate([2, 1, 3, 5, 3, 2]))

3

2. Are "listen" and "silent" anagrams?

from collections import Counter

print(Counter("listen") == Counter("silent"))
print(Counter("abc") == Counter("abd"))

True
False

3. Can the note "aab" be built from the letters of the magazine "baa"? What about "ba"?

from collections import Counter

def can_build(note, magazine):
    need = Counter(note)
    have = Counter(magazine)
    return all(have[c] >= n for c, n in need.items())

print(can_build("aab", "baa"), can_build("aab", "ba"))

True False

4. Why is looking up a key in a dictionary O(1) on average, when a list search is O(n)?

Run these in our free Python compiler.

Frequently asked questions

What is a hash table?

A data structure that stores key-value pairs and finds a value by calculating where it lives from its key, instead of searching. Lookups, inserts and deletes are O(1) on average.

Is a Python dictionary a hash table?

Yes. So is a set, which stores only keys. Python’s dict uses open addressing to handle collisions and, since Python 3.7, remembers insertion order.

What is a hash collision?

When two different keys produce the same bucket. Hash tables handle collisions, for example by chaining items in a list or probing for another slot, so both keys still work.

Why can’t a list be a dictionary key?

Keys need a stable hash. A list is mutable, so its contents (and its would-be hash) could change after it was stored, and Python could no longer find it. Use a tuple instead.

What is the worst-case time complexity of a hash table lookup?

O(n), if all keys collide into the same place. It is extremely rare with a good hash function and resizing, which is why the average O(1) is what people quote.

When should I use a set instead of a dict?

When you only need to know whether something is present (membership, uniqueness, duplicates) and have no value to attach. Use a dict when each key has a value, such as a count or an index.

Related reading

• Python Dictionaries Explained With Examples – the everyday side of dict.
• Time Complexity of Python Data Structures – the cost of every operation.
• Two Pointers Technique in Python – the sorted-array alternative to hashing.
• 10 Coding Interview Patterns in Python – hashing among the key patterns.