Hash Tables

Overview

A hash table stores key-value pairs and uses a hash function to map each key to a bucket, giving average O(1) lookup, insert, and delete. Worst case is O(n) when many keys collide into the same bucket. Python's dict and set are hash tables; keys must be hashable (immutable) types like strings, numbers, or tuples.

Syntax / Usage

Use a dict for key-value pairs.

ages = {"alice": 30, "bob": 25}

print(ages["alice"])       # O(1) lookup -> 30
ages["carol"] = 27         # O(1) insert
ages["bob"] = 26           # O(1) update

print("dave" in ages)      # O(1) membership -> False
print(ages.get("dave", 0)) # safe lookup with default -> 0

del ages["alice"]          # O(1) delete

Examples

Count word frequencies in a sentence:

text = "red blue red green blue red"
counts = {}
for word in text.split():
    counts[word] = counts.get(word, 0) + 1  # O(1) per word
print(counts)  # {'red': 3, 'blue': 2, 'green': 1}

Use a set to find duplicates in O(n):

def has_duplicates(items):
    seen = set()
    for item in items:
        if item in seen:      # O(1) membership
            return True
        seen.add(item)        # O(1) insert
    return False

print(has_duplicates([1, 2, 3, 2]))  # True

Common Mistakes

• Using a mutable object like a list as a key, raising TypeError
• Accessing a missing key with d[key] instead of d.get(key), causing KeyError
• Assuming lookups are always O(1) — collisions can degrade to O(n)
• Relying on dict order in old Python versions (guaranteed only since 3.7)
• Modifying a dict's keys while iterating over it

See Also

data-structures-arrays data-structures-linked-lists data-structures-trees