Hashes

📖 Introduction

Hash tables are the unsung heroes of efficient programming. Every time I use a Python dictionary to store user sessions, cache API responses, or count word frequencies, I'm leveraging one of the most powerful data structures in computer science.

What makes hash tables magical is their ability to provide near-constant time lookups, insertions, and deletions—regardless of how much data you store. Understanding how they achieve this, and their potential pitfalls, has helped me make better design decisions and debug performance issues that seemed mysterious.

🎯 What Is a Hash Table?

A hash table maps keys to values using a hash function to compute an index into an array of buckets.

Core Concept

# Simplified concept
def simple_hash_table():
    # Array of buckets
    buckets = [None] * 10
    
    # Insert: hash key to find bucket
    key = "alice"
    index = hash(key) % len(buckets)
    buckets[index] = ("alice", 42)
    
    # Lookup: hash to find bucket
    index = hash("alice") % len(buckets)
    return buckets[index]  # ("alice", 42)

Time Complexity

Operation

Average

Worst

Insert

O(1)

O(n)

Lookup

O(1)

O(n)

Delete

O(1)

O(n)

*Worst case occurs with many collisions

🔧 Hash Functions

A hash function converts keys into array indices. Good hash functions are:

Deterministic: Same key always produces same hash
Uniform: Distributes keys evenly across buckets
Fast: Computes quickly

Python's Built-in Hash

# Python's hash() function
print(hash("hello"))      # Consistent within session
print(hash(42))           # Same as the number itself
print(hash((1, 2, 3)))    # Tuples are hashable
# print(hash([1, 2, 3]))  # TypeError: lists are unhashable

# Hash randomization (Python 3.3+)
# Different between sessions for security

Implementing Hash Functions

def simple_string_hash(s: str, size: int) -> int:
    """Basic string hash using ASCII values."""
    total = 0
    for char in s:
        total += ord(char)
    return total % size


def polynomial_hash(s: str, size: int, base: int = 31) -> int:
    """
    Polynomial rolling hash.
    h(s) = s[0] + s[1]*base + s[2]*base^2 + ...
    Better distribution than simple sum.
    """
    total = 0
    power = 1
    
    for char in s:
        total += ord(char) * power
        power *= base
    
    return total % size


def djb2_hash(s: str, size: int) -> int:
    """
    DJB2 hash - simple and effective.
    """
    hash_value = 5381
    
    for char in s:
        hash_value = ((hash_value << 5) + hash_value) + ord(char)
    
    return hash_value % size


# Test distribution
def test_hash_distribution():
    words = ["apple", "banana", "cherry", "date", "elderberry",
             "fig", "grape", "honeydew", "kiwi", "lemon"]
    
    size = 7
    
    print("Simple hash distribution:")
    for word in words:
        print(f"  {word}: {simple_string_hash(word, size)}")
    
    print("\nPolynomial hash distribution:")
    for word in words:
        print(f"  {word}: {polynomial_hash(word, size)}")

💥 Collision Resolution

Collisions occur when different keys hash to the same index. Two main strategies handle this.

Strategy 1: Chaining

Each bucket stores a list of (key, value) pairs.

class HashTableChaining:
    """
    Hash table using chaining for collision resolution.
    """
    
    def __init__(self, capacity: int = 16):
        self.capacity = capacity
        self.size = 0
        self.buckets: list[list] = [[] for _ in range(capacity)]
        self.load_factor_threshold = 0.75
    
    def _hash(self, key) -> int:
        return hash(key) % self.capacity
    
    def _resize(self):
        """Double capacity when load factor exceeded."""
        old_buckets = self.buckets
        self.capacity *= 2
        self.buckets = [[] for _ in range(self.capacity)]
        self.size = 0
        
        for bucket in old_buckets:
            for key, value in bucket:
                self.put(key, value)
    
    def put(self, key, value) -> None:
        """Insert or update key-value pair. O(1) average."""
        if self.size / self.capacity >= self.load_factor_threshold:
            self._resize()
        
        index = self._hash(key)
        bucket = self.buckets[index]
        
        # Update if key exists
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        
        # Insert new key
        bucket.append((key, value))
        self.size += 1
    
    def get(self, key, default=None):
        """Get value for key. O(1) average."""
        index = self._hash(key)
        bucket = self.buckets[index]
        
        for k, v in bucket:
            if k == key:
                return v
        
        return default
    
    def remove(self, key) -> bool:
        """Remove key. O(1) average."""
        index = self._hash(key)
        bucket = self.buckets[index]
        
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return True
        
        return False
    
    def __contains__(self, key) -> bool:
        return self.get(key) is not None
    
    def __len__(self) -> int:
        return self.size


# Usage
ht = HashTableChaining()
ht.put("alice", 1)
ht.put("bob", 2)
print(ht.get("alice"))  # 1
print("bob" in ht)      # True

Strategy 2: Open Addressing

All entries stored in the array itself. On collision, probe for next open slot.

class HashTableOpenAddressing:
    """
    Hash table using linear probing.
    """
    
    DELETED = object()  # Tombstone marker
    
    def __init__(self, capacity: int = 16):
        self.capacity = capacity
        self.size = 0
        self.keys = [None] * capacity
        self.values = [None] * capacity
    
    def _hash(self, key) -> int:
        return hash(key) % self.capacity
    
    def _probe(self, key) -> int:
        """Linear probing to find slot."""
        index = self._hash(key)
        
        while self.keys[index] is not None:
            if self.keys[index] == key:
                return index
            if self.keys[index] is self.DELETED:
                break
            index = (index + 1) % self.capacity
        
        return index
    
    def _resize(self):
        old_keys = self.keys
        old_values = self.values
        self.capacity *= 2
        self.keys = [None] * self.capacity
        self.values = [None] * self.capacity
        self.size = 0
        
        for i, key in enumerate(old_keys):
            if key is not None and key is not self.DELETED:
                self.put(key, old_values[i])
    
    def put(self, key, value) -> None:
        """Insert or update. O(1) average."""
        if self.size >= self.capacity * 0.7:
            self._resize()
        
        index = self._probe(key)
        
        if self.keys[index] is None or self.keys[index] is self.DELETED:
            self.size += 1
        
        self.keys[index] = key
        self.values[index] = value
    
    def get(self, key, default=None):
        """Get value. O(1) average."""
        index = self._hash(key)
        
        while self.keys[index] is not None:
            if self.keys[index] == key:
                return self.values[index]
            index = (index + 1) % self.capacity
        
        return default
    
    def remove(self, key) -> bool:
        """Remove using tombstone. O(1) average."""
        index = self._hash(key)
        
        while self.keys[index] is not None:
            if self.keys[index] == key:
                self.keys[index] = self.DELETED
                self.values[index] = None
                self.size -= 1
                return True
            index = (index + 1) % self.capacity
        
        return False

Probing Strategies

def linear_probe(index: int, i: int, capacity: int) -> int:
    """Linear probing: h(k) + i."""
    return (index + i) % capacity


def quadratic_probe(index: int, i: int, capacity: int) -> int:
    """Quadratic probing: h(k) + i²."""
    return (index + i * i) % capacity


def double_hash(key, index: int, i: int, capacity: int) -> int:
    """Double hashing: h1(k) + i * h2(k)."""
    h2 = 7 - (hash(key) % 7)  # Second hash function
    return (index + i * h2) % capacity

🐍 Python Dict Internals

Python's dict is one of the most optimized hash table implementations.

Key Features

# Python 3.7+: dicts maintain insertion order

d = {}
d["first"] = 1
d["second"] = 2
d["third"] = 3

for key in d:
    print(key)  # first, second, third (guaranteed order)


# Key requirements: must be hashable
# Hashable = immutable and has __hash__ method

valid_keys = {
    "string": 1,
    42: 2,
    (1, 2, 3): 3,  # Tuple of hashables
    frozenset({1, 2}): 4,
}

# Invalid: mutable types
# {[1, 2]: "list key"}  # TypeError
# {{1: 2}: "dict key"}  # TypeError

Dict Comprehension and Methods

# Comprehension
squares = {x: x**2 for x in range(10)}

# Common methods
d = {"a": 1, "b": 2, "c": 3}

# Get with default
value = d.get("missing", 0)  # 0

# Set default (returns existing or inserts default)
value = d.setdefault("d", 4)  # Inserts and returns 4

# Pop with default
value = d.pop("e", None)  # Returns None, no KeyError

# Update multiple
d.update({"f": 5, "g": 6})

# Merge (Python 3.9+)
merged = d | {"h": 7}  # New dict
d |= {"i": 8}          # In-place merge


# Iteration
for key in d:
    pass

for key, value in d.items():
    pass

for value in d.values():
    pass

DefaultDict and Counter

from collections import defaultdict, Counter

# DefaultDict: auto-creates missing keys
word_count = defaultdict(int)
for word in ["apple", "banana", "apple"]:
    word_count[word] += 1  # No KeyError

# List of lists
graph = defaultdict(list)
graph["a"].append("b")  # Auto-creates list

# Set of values
unique_chars = defaultdict(set)
unique_chars["words"].add("a")


# Counter: specialized for counting
text = "abracadabra"
counts = Counter(text)
print(counts)  # Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})

# Most common
print(counts.most_common(3))  # [('a', 5), ('b', 2), ('r', 2)]

# Arithmetic
c1 = Counter("aab")
c2 = Counter("abc")
print(c1 + c2)  # Counter({'a': 3, 'b': 2, 'c': 1})
print(c1 - c2)  # Counter({'a': 1})

🔒 Sets

Sets are hash tables without values—just keys.

# Set operations - all O(1) average
s = set()
s.add(1)        # Add element
s.remove(1)     # Remove (raises KeyError if missing)
s.discard(1)    # Remove (no error if missing)
1 in s          # Membership test

# Set from iterable
s = set([1, 2, 2, 3])  # {1, 2, 3}
s = {1, 2, 3}          # Set literal

# Set operations
a = {1, 2, 3}
b = {2, 3, 4}

print(a | b)   # Union: {1, 2, 3, 4}
print(a & b)   # Intersection: {2, 3}
print(a - b)   # Difference: {1}
print(a ^ b)   # Symmetric difference: {1, 4}

# Subset/superset
print({1, 2} <= {1, 2, 3})  # True (subset)
print({1, 2, 3} >= {1, 2})  # True (superset)


# Frozen set: immutable, hashable
fs = frozenset([1, 2, 3])
d = {fs: "value"}  # Can be dict key

📊 Common Hash Table Problems

Two Sum

def two_sum(nums: list[int], target: int) -> list[int]:
    """
    Find indices of two numbers that sum to target.
    Time: O(n), Space: O(n)
    """
    seen = {}  # value -> index
    
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    
    return []


# Example
print(two_sum([2, 7, 11, 15], 9))  # [0, 1]

Group Anagrams

from collections import defaultdict

def group_anagrams(strs: list[str]) -> list[list[str]]:
    """
    Group strings that are anagrams of each other.
    Time: O(n * k log k) where k is max string length
    Space: O(n * k)
    """
    groups = defaultdict(list)
    
    for s in strs:
        # Sorted string as key
        key = tuple(sorted(s))
        groups[key].append(s)
    
    return list(groups.values())


# More efficient: count-based key
def group_anagrams_counting(strs: list[str]) -> list[list[str]]:
    """
    Time: O(n * k) using character counts as key.
    """
    groups = defaultdict(list)
    
    for s in strs:
        # Count characters (26 letters)
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        key = tuple(count)
        groups[key].append(s)
    
    return list(groups.values())


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

Longest Consecutive Sequence

def longest_consecutive(nums: list[int]) -> int:
    """
    Find length of longest consecutive elements sequence.
    Time: O(n), Space: O(n)
    """
    if not nums:
        return 0
    
    num_set = set(nums)
    longest = 0
    
    for num in num_set:
        # Only start counting from sequence beginning
        if num - 1 not in num_set:
            current = num
            length = 1
            
            while current + 1 in num_set:
                current += 1
                length += 1
            
            longest = max(longest, length)
    
    return longest


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

Subarray Sum Equals K

def subarray_sum(nums: list[int], k: int) -> int:
    """
    Count subarrays with sum equal to k.
    Time: O(n), Space: O(n)
    """
    count = 0
    prefix_sum = 0
    prefix_counts = {0: 1}  # Empty prefix
    
    for num in nums:
        prefix_sum += num
        
        # If (prefix_sum - k) exists, found a subarray
        if prefix_sum - k in prefix_counts:
            count += prefix_counts[prefix_sum - k]
        
        prefix_counts[prefix_sum] = prefix_counts.get(prefix_sum, 0) + 1
    
    return count


print(subarray_sum([1, 1, 1], 2))  # 2 ([1,1] at positions 0-1 and 1-2)

LRU Cache

from collections import OrderedDict

class LRUCache:
    """
    Least Recently Used cache.
    O(1) get and put.
    """
    
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()
    
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        
        # Move to end (most recently used)
        self.cache.move_to_end(key)
        return self.cache[key]
    
    def put(self, key: int, value: int) -> None:
        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)  # Remove oldest


# Manual implementation with dict + doubly linked list
class LRUCacheManual:
    class Node:
        def __init__(self, key=0, val=0):
            self.key = key
            self.val = val
            self.prev = None
            self.next = None
    
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key -> Node
        
        # Dummy head and tail
        self.head = self.Node()
        self.tail = self.Node()
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def _add_to_end(self, node):
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node
    
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        
        node = self.cache[key]
        self._remove(node)
        self._add_to_end(node)
        return node.val
    
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
        
        node = self.Node(key, value)
        self.cache[key] = node
        self._add_to_end(node)
        
        if len(self.cache) > self.capacity:
            lru = self.head.next
            self._remove(lru)
            del self.cache[lru.key]

Valid Sudoku

def is_valid_sudoku(board: list[list[str]]) -> bool:
    """
    Check if Sudoku board is valid (partial solution).
    Time: O(81) = O(1), Space: O(81) = O(1)
    """
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    
    for i in range(9):
        for j in range(9):
            num = board[i][j]
            if num == '.':
                continue
            
            box_idx = (i // 3) * 3 + (j // 3)
            
            if num in rows[i] or num in cols[j] or num in boxes[box_idx]:
                return False
            
            rows[i].add(num)
            cols[j].add(num)
            boxes[box_idx].add(num)
    
    return True

📝 Practice Exercises

Exercise 1: First Unique Character

def first_uniq_char(s: str) -> int:
    """
    Find index of first non-repeating character.
    Return -1 if none exists.
    """
    pass

Solution

from collections import Counter

def first_uniq_char(s: str) -> int:
    count = Counter(s)
    
    for i, char in enumerate(s):
        if count[char] == 1:
            return i
    
    return -1

Exercise 2: Isomorphic Strings

def is_isomorphic(s: str, t: str) -> bool:
    """
    Check if characters in s can be replaced to get t.
    Each character must map to exactly one other character.
    "egg" and "add" -> True
    "foo" and "bar" -> False
    """
    pass

Solution

def is_isomorphic(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    
    s_to_t = {}
    t_to_s = {}
    
    for c1, c2 in zip(s, t):
        if c1 in s_to_t:
            if s_to_t[c1] != c2:
                return False
        else:
            s_to_t[c1] = c2
        
        if c2 in t_to_s:
            if t_to_s[c2] != c1:
                return False
        else:
            t_to_s[c2] = c1
    
    return True

Exercise 3: Design HashMap

class MyHashMap:
    """
    Design a HashMap without using built-in hash table libraries.
    """
    
    def __init__(self):
        pass
    
    def put(self, key: int, value: int) -> None:
        pass
    
    def get(self, key: int) -> int:
        """Return -1 if key not found."""
        pass
    
    def remove(self, key: int) -> None:
        pass

Solution

class MyHashMap:
    def __init__(self):
        self.size = 1000
        self.buckets = [[] for _ in range(self.size)]
    
    def _hash(self, key: int) -> int:
        return key % self.size
    
    def put(self, key: int, value: int) -> None:
        idx = self._hash(key)
        bucket = self.buckets[idx]
        
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        
        bucket.append((key, value))
    
    def get(self, key: int) -> int:
        idx = self._hash(key)
        bucket = self.buckets[idx]
        
        for k, v in bucket:
            if k == key:
                return v
        
        return -1
    
    def remove(self, key: int) -> None:
        idx = self._hash(key)
        bucket = self.buckets[idx]
        
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                return

🔑 Key Takeaways

Hash tables provide O(1) average case for insert/lookup/delete
Collisions are inevitable—handle with chaining or open addressing
Load factor affects performance—resize when threshold exceeded
Python dicts are highly optimized and maintain insertion order
Sets are hash tables with only keys—great for membership testing
Counter and defaultdict simplify common patterns

🚀 What's Next?

In the next article, we'll explore trees:

Binary trees and BSTs
Tree traversals (DFS and BFS)
Balanced trees
Common tree problems

Next: Article 8 - Trees

📚 References

Python dict implementation details (CPython source)
CLRS Chapter 11: Hash Tables
"Designing Data-Intensive Applications" - Hash indexes

PreviousStacks and Queues NextTrees and Binary Search Trees

Last updated 1 month ago

hashtag📖 Introduction

hashtag🎯 What Is a Hash Table?

hashtagCore Concept

hashtagTime Complexity

hashtag🔧 Hash Functions

hashtagPython's Built-in Hash

hashtagImplementing Hash Functions

hashtag💥 Collision Resolution

hashtagStrategy 1: Chaining

hashtagStrategy 2: Open Addressing

hashtagProbing Strategies

hashtag🐍 Python Dict Internals

hashtagKey Features

hashtagDict Comprehension and Methods

hashtagDefaultDict and Counter

hashtag🔒 Sets

hashtag📊 Common Hash Table Problems

hashtagTwo Sum

hashtagGroup Anagrams

hashtagLongest Consecutive Sequence

hashtagSubarray Sum Equals K

hashtagLRU Cache

hashtagValid Sudoku

hashtag📝 Practice Exercises

hashtagExercise 1: First Unique Character

hashtagExercise 2: Isomorphic Strings

hashtagExercise 3: Design HashMap

hashtag🔑 Key Takeaways

hashtag🚀 What's Next?

hashtag📚 References

📖 Introduction

🎯 What Is a Hash Table?

Core Concept

Time Complexity

🔧 Hash Functions

Python's Built-in Hash

Implementing Hash Functions

💥 Collision Resolution

Strategy 1: Chaining

Strategy 2: Open Addressing

Probing Strategies

🐍 Python Dict Internals

Key Features

Dict Comprehension and Methods

DefaultDict and Counter

🔒 Sets

📊 Common Hash Table Problems

Two Sum

Group Anagrams

Longest Consecutive Sequence

Subarray Sum Equals K

LRU Cache

Valid Sudoku

📝 Practice Exercises

Exercise 1: First Unique Character

Exercise 2: Isomorphic Strings

Exercise 3: Design HashMap

🔑 Key Takeaways

🚀 What's Next?

📚 References