Hash Tables and Python dict: Hash Functions, Collisions and Why O(1) Is Only Average

By 0xmote · May 25, 2026 · 26 min read · Updated Sep 24, 2026 Intermediate Tutorial

Key takeaways

What makes hash table lookups O(1) on average, how collisions are resolved, practical Python dict/Counter/defaultdict usage, common mistakes, and performance tips for interview problems.

Introduction

What is a Hash Table?

A hash table is a data structure that stores key-value pairs, enabling search/insertion/deletion in average O(1) time complexity. O(1) means nearly constant time regardless of input size.

Other names:

Hash Map
Dictionary (Python)
Associative Array
Map (C++, Java) Why is it fast? Arrays allow O(1) access by index. Hash tables use a hash function (converts key to fixed-length number/slot) to transform keys into indices, enabling array-like fast access.

# Array: access by index
arr = [10, 20, 30, 40, 50]
print(arr[2])  # 30 (O(1))
# Hash table: access by key
hash_table = {"apple": 100, "banana": 200}
print(hash_table["apple"])  # 100 (O(1))
# Internally: hash("apple") % size → index → value

Time Complexity Comparison:

Data Structure	Search	Insert	Delete
Array (unsorted)	O(n)	O(1)	O(n)
Array (sorted)	O(log n)	O(n)	O(n)
Linked List	O(n)	O(1)	O(n)
Hash Table	O(1)	O(1)	O(1)

The hash table row needs an asterisk: those are average costs. In the worst case, when many keys land in the same slot, every operation degrades to O(n), which is worse than a sorted array’s O(log n) search. The average case holds when the hash function spreads keys evenly and the table is resized before it gets too full, and real implementations work hard to guarantee both. The other thing a hash table gives up is order. You cannot ask for “the smallest key” or “all keys between 10 and 20” without scanning everything; if you need that, a balanced tree (std::map, Java’s TreeMap) or a sorted list with binary search is the right tool.

In interviews and in practice, the question “can a hash table turn this O(n²) into O(n)?” is one of the most useful first moves. Whenever a nested loop is searching for “have I seen this value before” or “which earlier element pairs with this one”, storing earlier elements in a dict or set usually removes the inner loop, at the cost of O(n) extra memory.

Hash Function

What is a Hash Function?

A hash function converts arbitrary-size data into a fixed-size value (hash value).

Good Hash Function Properties:

✅ Deterministic: Same input → same output
✅ Fast Computation: O(1)
✅ Uniform Distribution: Hash values evenly distributed
✅ Minimize Collisions: Different inputs → different outputs (ideally)

Simple Hash Function Example

# Method 1: Python built-in hash() + modulo
def simple_hash(key, size):
    return hash(key) % size
print(simple_hash("apple", 10))   # e.g. 8 (varies between runs, see below)
print(simple_hash("banana", 10))  # e.g. 3
print(simple_hash("cherry", 10))  # e.g. 6
# Method 2: String hash (manual implementation)
def string_hash(s, size):
    hash_value = 0
    for char in s:
        hash_value = (hash_value * 31 + ord(char)) % size
    return hash_value
print(string_hash("apple", 10))
# Python built-in hash()
print(hash("apple"))   # -6076896708304529682 (example)
print(hash(42))        # 42 (integers hash to themselves)
print(hash((1, 2)))    # 3713081631934410656 (tuple hash)
# ❌ Mutable objects cannot be hashed
# print(hash([1, 2]))  # TypeError: unhashable type: 'list'

The exact numbers above will not match what you see. Since Python 3.3, string and bytes hashes are randomized per process (controlled by PYTHONHASHSEED) so that attackers cannot precompute thousands of strings that collide and turn a web server’s dict lookups into O(n) each. That kind of “hash flooding” denial-of-service attack was demonstrated against many languages around 2011, and randomization is the standard defense. The practical consequence is that hash() is fine for in-memory tables but must never be stored in a file or database or used to shard data across machines; use a stable function such as hashlib.sha256 or zlib.crc32 for that. Integers are not randomized, and hash(n) == n for small integers, with the curious exception hash(-1) == -2 because -1 is reserved as an error value in CPython’s C API.

The manual string_hash is a polynomial rolling hash, the same idea Java uses for String.hashCode() with the multiplier 31. Each character shifts the previous value and adds itself, so "ab" and "ba" produce different results, which a plain sum of character codes would not. The % size at each step keeps the number small; in languages with fixed-width integers you would normally let it overflow and take the modulus once at the end.

Why are lists unhashable? A dict stores each key in the slot chosen by its hash at insertion time. If you could mutate a key afterwards, its hash would change but it would still sit in the old slot, and lookups would never find it again. Python prevents that by making mutable built-ins unhashable. Tuples are hashable only if everything inside them is: hash((1, [2])) also raises TypeError.

Hash Collision

Collision occurs when different keys produce the same hash value.

# Collision example
def bad_hash(key, size):
    return len(key) % size  # Bad hash function
print(bad_hash("apple", 10))   # 5
print(bad_hash("grape", 10))   # 5 (collision!)
print(bad_hash("peach", 10))   # 5 (collision!)

Collisions are not a sign of a broken hash function; they are unavoidable. Mapping an unbounded set of keys into a fixed number of slots guarantees that some keys share a slot (the pigeonhole principle), and even with a perfect random hash, the birthday paradox means collisions show up much earlier than intuition suggests: with 23 keys in 365 slots, the chance of at least one collision is already over 50%. What separates a good hash function from bad_hash is how evenly the collisions spread. len(key) sends every five-letter word to the same slot, so a table of English words would degenerate into a handful of very long chains. The next section shows how tables cope with the collisions that remain.

Python dict Usage

Basic Operations

# Creation
hash_table = {}
hash_table = dict()
# Insert O(1)
hash_table["apple"] = 100
hash_table["banana"] = 200
hash_table["cherry"] = 300
# Search O(1)
print(hash_table["apple"])  # 100
print(hash_table.get("grape", 0))  # 0 (default)
# Update O(1)
hash_table["apple"] = 150
print(hash_table["apple"])  # 150
# Delete O(1)
del hash_table["apple"]
print("apple" in hash_table)  # False
# Existence check O(1)
if "banana" in hash_table:
    print("exists")
# Iteration O(n)
for key in hash_table:
    print(key, hash_table[key])
for key, value in hash_table.items():
    print(f"{key}: {value}")
# Keys/values lists
keys = list(hash_table.keys())
values = list(hash_table.values())

Since Python 3.7, dicts are guaranteed to preserve insertion order, so the loops above visit keys in the order they were added. That guarantee is a language rule, not an accident of the implementation, and code may rely on it. It does not mean dicts are sorted: {"b": 1, "a": 2} iterates b then a. Use sorted(d) or sorted(d.items()) when you need key order.

The difference between d[key] and d.get(key, default) is a design decision, not just style. d[key] raises KeyError for a missing key, which is what you want when absence means a bug. get returns a default, which is what you want when absence is normal. A common interview-code bug is using get(key) without a default, getting None back, and then doing arithmetic on it. Also note that .keys(), .values() and .items() return views, not copies: they reflect later changes to the dict, and list(...) is needed only when you want a snapshot.

Collision Resolution

Method 1: Chaining

Store values with same index in a linked list.

class HashTableChaining:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def insert(self, key, value):
        idx = self._hash(key)
        
        # Update if key exists
        for i, (k, v) in enumerate(self.table[idx]):
            if k == key:
                self.table[idx][i] = (key, value)
                return
        
        # Add if not exists
        self.table[idx].append((key, value))
    
    def get(self, key):
        idx = self._hash(key)
        
        for k, v in self.table[idx]:
            if k == key:
                return v
        
        return None
# Test
ht = HashTableChaining(size=5)
ht.insert("apple", 100)
ht.insert("banana", 200)
print(ht.get("apple"))  # 100

Here each bucket is a Python list rather than a linked list, but the idea is the same: every slot holds a small collection of (key, value) pairs, and a lookup hashes to the slot and then scans only that slot. The cost of a lookup is proportional to the bucket length, and the average bucket length is the load factor α = n / size. With 1000 keys in 5 buckets, each lookup scans about 200 pairs, which is why real tables grow as they fill (see Section 8).

Chaining degrades gracefully: even at α > 1 it still works, just slower, and deletion is easy (remove the pair from its bucket). The costs are an extra allocation per bucket or node and poor cache locality, since following a chain jumps around memory. Java’s HashMap uses chaining and, since Java 8, converts a bucket into a balanced tree once it holds more than eight entries, which caps the worst case at O(log n) instead of O(n). The get here returns None for a missing key, which is ambiguous if None can also be a stored value; raising KeyError like dict does avoids that.

Method 2: Open Addressing

Find another empty slot on collision.

class HashTableLinearProbing:
    def __init__(self, size=10):
        self.size = size
        self.keys = [None] * size
        self.values = [None] * size
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def insert(self, key, value):
        idx = self._hash(key)
        
        while self.keys[idx] is not None:
            if self.keys[idx] == key:
                self.values[idx] = value
                return
            idx = (idx + 1) % self.size
        
        self.keys[idx] = key
        self.values[idx] = value
    
    def get(self, key):
        idx = self._hash(key)
        
        while self.keys[idx] is not None:
            if self.keys[idx] == key:
                return self.values[idx]
            idx = (idx + 1) % self.size
        
        return None

Linear probing stores everything in one flat array and, on a collision, tries the next slot, then the next. That layout is very cache-friendly, which is why high-performance tables (Rust’s HashMap, Google’s Swiss tables, and CPython’s dict, which uses a perturbed probing sequence rather than simple +1) all use some form of open addressing. The downside is clustering: occupied slots tend to form runs, and any key that hashes into a run has to walk to its end, so performance falls off sharply as the table fills. Open-addressing tables therefore keep the load factor well below 1, typically between about 0.5 and 0.9 depending on the probing scheme.

This minimal version has two gaps that are worth knowing because they are classic interview follow-ups. First, there is no resizing, so once all slots are full, insert of a new key and get of a missing key both loop forever. Second, there is no delete, and deletion is genuinely tricky: if you set a slot back to None, any key that was placed after it during probing becomes unreachable, because get stops at the first None. The standard fix is a tombstone marker that get skips over but insert may reuse.

Problem Solving

Problem 1: Two Sum

def two_sum(arr, target):
    """
    Find indices of two numbers that sum to target
    [2, 7, 11, 15], target=9 → [0, 1]
    
    Time: O(n), Space: O(n)
    """
    seen = {}  # value: index
    
    for i, num in enumerate(arr):
        complement = target - num
        
        if complement in seen:
            return [seen[complement], i]
        
        seen[num] = i
    
    return []
# Test
arr = [2, 7, 11, 15]
print(two_sum(arr, 9))   # [0, 1]
print(two_sum(arr, 13))  # [0, 2]

The brute-force version checks every pair, O(n²). The hash version flips the question: instead of “which later element pairs with this one?”, it asks “has the partner of this element already appeared?”, and a dict answers that in O(1). Two details matter. The lookup happens before seen[num] = i, so an element is never paired with itself; with target 8 and input [4, 1], checking after inserting would wrongly return [0, 0]. And storing value → index means duplicates overwrite earlier indices, which is fine here because we only need one valid pair, but would be wrong if the problem asked for all pairs.

If the input were already sorted, a two-pointer scan from both ends would solve the same problem in O(n) time and O(1) extra space. The hash table’s advantage is that it works on unsorted input without the O(n log n) sort; its cost is the O(n) memory.

Problem 2: Group Anagrams

def group_anagrams(strs):
    """
    Group anagrams together
    ["eat", "tea", "tan", "ate", "nat", "bat"]
    → [["eat", "tea", "ate"], ["tan", "nat"], [bat]]
    
    Time: O(n * k log k), Space: O(n * k)
    """
    anagrams = {}
    
    for word in strs:
        key = ''.join(sorted(word))
        
        if key not in anagrams:
            anagrams[key] = []
        anagrams[key].append(word)
    
    return list(anagrams.values())
# Test
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(strs))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

The key insight is choosing a canonical form: a value that is identical for every member of a group and different across groups. Sorting the letters is the simplest canonical form for anagrams. The pattern generalizes well beyond this problem. Grouping strings that are rotations of each other, points on the same line through the origin, or words with the same letter pattern ("abb" and "cdd") all come down to “find a hashable canonical key, then group by it”. The if key not in anagrams dance is exactly what defaultdict(list) removes, as Section 5 shows.

Problem 3: Longest Substring Without Repeating Characters

def length_of_longest_substring(s):
    """
    "abcabcbb" → 3 ("abc")
    "bbbbb" → 1 ("b")
    
    Time: O(n), Space: O(min(n, m))
    """
    char_index = {}
    max_length = 0
    start = 0
    
    for i, char in enumerate(s):
        if char in char_index and char_index[char] >= start:
            start = char_index[char] + 1
        
        char_index[char] = i
        max_length = max(max_length, i - start + 1)
    
    return max_length
# Test
print(length_of_longest_substring("abcabcbb"))  # 3
print(length_of_longest_substring("bbbbb"))     # 1
print(length_of_longest_substring("pwwkew"))    # 3

This combines a hash table with a sliding window. start marks the left edge of the current window with no repeats, and char_index remembers where each character was last seen. When the current character already appears inside the window, the left edge jumps just past its previous position. The condition char_index[char] >= start is the part people most often drop: without it, a character seen before the window started (for example the first a in "abba" when you reach the final a) would drag start backwards and produce a window that contains duplicates. Each character is visited once, so the whole scan is O(n). The space bound O(min(n, m)) refers to the alphabet size m: the dict never holds more distinct characters than exist.

Python Collections Module

Counter

from collections import Counter
# Create
counter = Counter([1, 2, 2, 3, 3, 3])
print(counter)  # Counter({3: 3, 2: 2, 1: 1})
# String count
text = "hello world"
counter = Counter(text)
print(counter)  # Counter({'l': 3, 'o': 2, ...})
# most_common(): most frequent elements
print(counter.most_common(3))  # [('l', 3), ('o', 2), ('h', 1)]
# Operations
c1 = Counter(['a', 'b', 'c', 'a'])
c2 = Counter(['a', 'b', 'b'])
print(c1 + c2)  # Counter({'a': 3, 'b': 3, 'c': 1})
print(c1 - c2)  # Counter({'a': 1, 'c': 1})
print(c1 & c2)  # Counter({'a': 1, 'b': 1}) (intersection)
print(c1 | c2)  # Counter({'a': 2, 'b': 2, 'c': 1}) (union)

Counter is a dict subclass whose missing keys read as 0 instead of raising KeyError, which is why counter["z"] returns 0 for a letter that never appeared. Reading a missing key does not insert it, unlike defaultdict. The arithmetic operators treat counters as multisets: + adds counts, - subtracts and drops anything that falls to zero or below, & takes the minimum per key and | the maximum. That makes “can the letters of note be built from magazine?” a one-liner: not (Counter(note) - Counter(magazine)).

most_common(k) uses a heap internally when k is given, so it is O(n log k) rather than a full sort, and ties are returned in the order the elements were first encountered. That ordering is well defined but easy to forget; if an interview problem specifies a tie-breaking rule such as “alphabetical”, sort explicitly instead of relying on it.

defaultdict

from collections import defaultdict
# int default (0)
word_count = defaultdict(int)
for word in ["apple", "banana", "apple"]:
    word_count[word] += 1
print(dict(word_count))  # {'apple': 2, 'banana': 1}
# list default ([])
groups = defaultdict(list)
for name, grade in [("Alice", "A"), ("Bob", "B"), ("Charlie", "A")]:
    groups[grade].append(name)
print(dict(groups))  # {'A': ['Alice', 'Charlie'], 'B': ['Bob']}

defaultdict(factory) calls factory() to create a value the first time a missing key is read, so word_count[word] += 1 works without a prior check. The factory is a callable, not a value: defaultdict(list) is right, defaultdict([]) raises TypeError: first argument must be callable or None. The convenience has a sharp edge I have seen cause real bugs: merely looking up a key inserts it. Code like if groups["Z"]: ... silently adds an empty "Z" entry, so a later len(groups) or a JSON dump contains keys nobody meant to create. Use "Z" in groups or groups.get("Z") for membership checks, and convert with dict(groups) before handing the result to code that does not expect the auto-insert behavior.

LRU Cache Implementation

from collections import OrderedDict
class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity
    
    def get(self, key):
        if key not in self.cache:
            return -1
        
        self.cache.move_to_end(key)
        return self.cache[key]
    
    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        
        self.cache[key] = value
        
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)
# Test
cache = LRUCache(3)
cache.put("a", 1)
cache.put("b", 2)
cache.put("c", 3)
cache.get("a")
cache.put("d", 4)  # Removes 'b'

An LRU cache needs two things at once: O(1) lookup by key and O(1) “which entry was used least recently?”. A plain dict gives the first; an ordering gives the second. OrderedDict combines them (internally a hash table plus a doubly linked list), and move_to_end and popitem(last=False) are both O(1). In the test, get("a") moves a to the most-recent end, so when d pushes the size past 3, the oldest entry is b. In an interview the follow-up is often “implement it without OrderedDict”, and the expected answer is exactly that structure written by hand: a dict mapping keys to nodes of a doubly linked list. For caching function results in real code, functools.lru_cache already implements this.

Usage Patterns

Pattern 1: Frequency Counting

def char_frequency(s):
    freq = {}
    for char in s:
        freq[char] = freq.get(char, 0) + 1
    return freq
print(char_frequency("hello"))  # {'h': 1, 'e': 1, 'l': 2, 'o': 1}
# Using Counter
from collections import Counter
print(dict(Counter("hello")))

Pattern 2: Grouping

from collections import defaultdict
words = ["apple", "pie", "banana", "cat", "dog", "cherry"]
groups = defaultdict(list)
for word in words:
    groups[len(word)].append(word)
print(dict(groups))
# {5: ['apple'], 3: ['pie', 'cat', 'dog'], 6: ['banana', 'cherry']}

Pattern 3: Caching (Memoization)

# Fibonacci with caching
def fib_fast(n, cache={}):
    if n in cache:
        return cache[n]
    
    if n <= 1:
        return n
    
    cache[n] = fib_fast(n-1, cache) + fib_fast(n-2, cache)
    return cache[n]
print(fib_fast(30))  # 832040 (fast)
# Using functools.lru_cache (recommended)
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)
print(fib(30))  # 832040 (very fast)

fib_fast uses a mutable default argument as its cache. Python evaluates default values once, when the function is defined, so every call shares the same dict. For Fibonacci that is harmless and even helpful, but it is the same mechanism behind the well-known bug where def add(item, items=[]) keeps growing across calls. When the cached result depends on anything besides the arguments (a global list, a config), a shared default cache returns stale answers. lru_cache is the safer choice: it keys on the arguments, exposes cache_info() and cache_clear(), and bounds memory when you pass a maxsize. Both approaches still recurse, so fib(5000) on a cold cache hits RecursionError; for deep inputs an iterative loop is simpler.

Pattern 4: Index Mapping

def find_indices(arr, target):
    """Find all indices of target value"""
    index_map = {}
    
    for i, num in enumerate(arr):
        if num not in index_map:
            index_map[num] = []
        index_map[num].append(i)
    
    return index_map.get(target, [])
arr = [1, 2, 3, 2, 4, 2, 5]
print(find_indices(arr, 2))  # [1, 3, 5]

For a single query, building the whole index map is wasted work; [i for i, x in enumerate(arr) if x == target] is simpler and just as fast. The index map pays off when you answer many queries against the same array: build it once in O(n), then each query is O(1) plus the size of its answer. That “precompute a dict, then answer queries in O(1)” trade is the general lesson of this section, and it is worth recognizing when a problem says “you will be asked Q questions about the same input”.

Common Mistakes

Mistake 1: Using Mutable Objects as Keys

# ❌ Wrong
# hash_table = {[1, 2]: "value"}  # TypeError: unhashable type: 'list'
# ✅ Correct
hash_table = {(1, 2): "value"}  # Use tuple
print(hash_table[(1, 2)])  # value

The same rule applies to your own classes, with a twist. A user-defined class is hashable by default using object identity, so two instances with the same fields are different keys. If you define __eq__ to compare fields, Python sets __hash__ to None and the class becomes unhashable, because equal objects must have equal hashes. The clean fix is @dataclass(frozen=True), which generates matching __eq__ and __hash__ from the fields and prevents mutation. The failure mode to avoid is defining __hash__ over fields that can change: mutate the object after inserting it into a dict and the dict can no longer find it.

Mistake 2: Missing KeyError Handling

# ❌ Wrong
hash_table = {"a": 1}
# print(hash_table["b"])  # KeyError: 'b'
# ✅ Correct 1: Use get()
value = hash_table.get("b", 0)
print(value)  # 0
# ✅ Correct 2: Check with in
if "b" in hash_table:
    print(hash_table["b"])
else:
    print("Key not found")

Mistake 3: Modifying During Iteration

# ❌ Wrong
hash_table = {"a": 1, "b": 2, "c": 3}
# for key in hash_table:
#     if hash_table[key] == 2:
#         del hash_table[key]  # RuntimeError
# ✅ Correct 1: Convert to list
hash_table = {"a": 1, "b": 2, "c": 3}
for key in list(hash_table.keys()):
    if hash_table[key] == 2:
        del hash_table[key]
# ✅ Correct 2: Dictionary comprehension
hash_table = {"a": 1, "b": 2, "c": 3}
hash_table = {k: v for k, v in hash_table.items() if v != 2}

The error is RuntimeError: dictionary changed size during iteration. Python raises it because adding or removing keys can trigger a resize that rearranges the underlying table, which would leave the iterator pointing at the wrong place. Changing the value of an existing key during iteration is allowed, since the size and layout do not change. The two fixes differ subtly: list(hash_table.keys()) mutates the original dict in place, so any other reference to it sees the change, while the comprehension builds a new dict and rebinds the name, leaving other references to the old dict untouched. Pick based on whether other code holds the same dict.

Performance Optimization

Load Factor Management

class DynamicHashTable:
    def __init__(self, initial_size=8):
        self.size = initial_size
        self.count = 0
        self.table = [[] for _ in range(self.size)]
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def _load_factor(self):
        return self.count / self.size
    
    def _resize(self):
        """Double size when load factor > 0.7"""
        old_table = self.table
        self.size *= 2
        self.table = [[] for _ in range(self.size)]
        self.count = 0
        
        for bucket in old_table:
            for key, value in bucket:
                self.insert(key, value)
    
    def insert(self, key, value):
        if self._load_factor() > 0.7:
            self._resize()
        
        idx = self._hash(key)
        
        for i, (k, v) in enumerate(self.table[idx]):
            if k == key:
                self.table[idx][i] = (key, value)
                return
        
        self.table[idx].append((key, value))
        self.count += 1

(The earlier version of this class called self._hash without defining it, which raised AttributeError on the first insert; the method is added above.)

Resizing is what makes the O(1) average real. When the load factor passes a threshold, the table allocates twice as many buckets and re-inserts every key, because each key’s slot depends on hash(key) % size and size just changed. A single resize is O(n), but since the table doubles each time, the total resize work over n insertions is about 2n, so each insertion is still O(1) amortized. The same argument explains list.append and C++‘s vector::push_back. The practical consequence is latency spikes: most inserts are instant, and one occasionally takes a long pause. Real-time systems sometimes pre-size tables or use incremental rehashing (Redis does this) to avoid that pause.

The threshold is a trade-off. A low load factor wastes memory on empty buckets; a high one lengthens chains or probe sequences. Chaining tolerates values near or above 1 (Java’s default is 0.75), while open addressing needs more headroom. CPython’s dict resizes when it is about two-thirds full. Note that _resize calls insert, which re-checks the load factor; that is safe here only because the doubled table is guaranteed to be under the threshold during the rehash.

Key Points

Hash Table: Key-value storage, average O(1) search/insert/delete
Hash Function: Convert key to index, uniform distribution important
Collision Resolution:
- Chaining: Store in linked list
- Open Addressing: Find another empty slot
Python Tools:
- dict: Basic hash table
- Counter: Frequency counting
- defaultdict: Auto-create default values
- OrderedDict: Maintain order + extra features

When to Use

Situation	Data Structure	Time Complexity
Fast search	Hash Table	O(1)
Frequency count	Counter	O(n)
Duplicate check	set	O(n)
Grouping	defaultdict	O(n)
Caching	dict / LRU Cache	O(1)

Time Complexity Improvement Pattern

# Before: O(n²) - nested loops
def has_duplicate_slow(arr):
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False
# After: O(n) - hash table
def has_duplicate_fast(arr):
    seen = set()
    for num in arr:
        if num in seen:
            return True
        seen.add(num)
    return False
# Or simpler
def has_duplicate(arr):
    return len(arr) != len(set(arr))

The one-liner is the most readable, but it always processes the entire input, while has_duplicate_fast stops at the first duplicate. On a large input where a duplicate appears early, the explicit loop can finish almost immediately. Both need the elements to be hashable. If they are not (lists of lists, for example), converting each element to a tuple works, and if memory is tight, sorting a copy and comparing neighbours gives O(n log n) time with less extra space. When I review interview solutions, the most common hash-table mistake is not choosing the wrong structure but forgetting that the O(1) claim assumes cheap hashing: using long strings or large tuples as keys makes every hash computation O(k), and the “O(n)” solution quietly becomes O(n·k).

Frequently Asked Questions (FAQ)

Q. In Group Anagrams, why use a sorted string or a count tuple as the dictionary key?

A. Dictionary keys must be hashable, so a list of letters or a count list cannot be used directly. ''.join(sorted(word)) gives a hashable key at O(k log k) per word, while a tuple of 26 letter counts costs O(k) and is faster for long words. Both produce the same key for every anagram, which is exactly what the grouping needs.