Hashmaps

A filing system that does math on the key to figure out where the value lives, so lookups cost the same whether it holds ten entries or ten million.

Definition

Arrays gave us instant access, but only when you know the position number. Ask an array whether it contains the value 42 and it checks slot after slot, and a linked list is no better. Finding things by value seemed doomed to cost O(n). So here's the question this page answers: what if the data itself could tell you where it lives?

That's exactly what a hashmap does. It's a smart filing system built on an array, storing data as key-value pairs, where each key is the unique address for its value. A hash function maps each pair to a specific spot in the array, so you can look up any value by its key without searching the entire dataset.

Operations

Here's a hashmap's core trick in action. Store the pair cat: meow in a table with 8 slots. The hash function crunches the key cat into the number 5, so the pair goes into slot 5. To look it up later, hash cat again, get 5 again, and jump straight there. There's no scan and no comparison against other keys, and the size of the table never enters the math.

You might conclude that hashmaps are always O(1). Look at the asterisks in the table below: every fast operation says average O(1), worst case O(n). The villain is the collision, two keys landing in the same slot, and much of this page is about what happens when one strikes. There's one more honest cost up front: hashmaps are unordered, so they don't work well when you need sorted data:

Operations	Time	Space	Notes
Search	O(1)*	O(1)	Average O(1), worst case O(n) with collisions. Uses hash function to find bucket
Access	O(1)*	O(1)	Average O(1), worst case O(n) with collisions. Retrieves value using key's hash
Insert	O(1)*	O(1)	Average O(1), worst case O(n). May trigger resize if load factor exceeded
Delete	O(1)*	O(1)	Average O(1), worst case O(n). Must handle collision chain if present
Resize	O(n)	O(n)	Triggered when load factor exceeds threshold. Rehashes all elements
Get Keys	O(n)	O(n)	Returns all keys in the hashmap. Must traverse all buckets
Get Values	O(n)	O(n)	Returns all values in the hashmap. Must traverse all buckets

Key-Value Pairs

Key-value pairs are the building blocks of a hashmap. A key is a unique label that points to a value. Think of a contact list: a person's name (the key) maps to their phone number (the value). Keys are always unique, but values can repeat. The analogy leaks in one spot, though: a contact list is alphabetized, while a hashmap keeps no useful order at all. The hash function uses keys to figure out where each value lives, and it scatters them on purpose.

Hash Function

Hashmaps rely on hash functions to do their work. A hash function takes any input and converts it into an integer called a hash code. That integer is used as the index where the value gets stored. Because hashing gives you the index directly, the hashmap can jump straight to the data instead of scanning every entry.

The hash function above shows how to turn a key (a number or a string) into an index for storing or looking up data. Run cat through the Python version with a table size of 8: the weighted character codes sum to 641, the prime multiplier turns that into 1,326,229, and the modulo operator against the hashmap's size reduces it to 1326229 % 8 = 5. That's the slot 5 from earlier, found by pure arithmetic, and the same arithmetic finds it again on every lookup. A good hash function spreads keys evenly across the table, so fewer collisions happen, which is what keeps hashmaps fast. Which raises a question: with 8 slots and an endless supply of possible strings, can a clever enough hash function keep every key in its own slot?

Hashmap Collisions

No hash function, however clever, can keep every key in its own slot. Once there are more possible keys than slots, some keys have to share. Collisions happen when different keys hash to the same index. Imagine two students accidentally assigned the same seat in a classroom. That's a collision in a hashmap. To handle them without losing data, hashmaps use strategies like chaining, which adds more chairs at the contested seat, or open addressing, which walks the second student to the next empty seat. Both make sure every value stays reachable, even when multiple keys land in the same slot.

Resize and Rehash

Collisions are also why a hashmap can't stay small forever. Picture a table with 8 buckets absorbing 100 entries: nothing breaks, but the average bucket now holds 12 or 13 items, and every lookup decays into a little scan. So before things get crowded, the hashmap has to resize and rehash. Think of it like moving to a bigger house when your family outgrows the old one, with one twist the analogy misses: nobody keeps their old room. Once the load factor crosses a threshold (typically 0.75), the hashmap allocates a larger array and redistributes its elements. It walks every key-value pair and recomputes its hash, because hash % size changes the moment size does. The operation is expensive when it runs, but it's the same bargain dynamic arrays make: a rare O(n) copy is what keeps the hashmap fast as it grows:

Separate Chaining

Separate chaining is a simple way to handle collisions. When multiple keys land at the same index, chaining stores them together in a linked list at that spot. Each index holds a "chain" (really just a linked list) of all the entries that hashed to it. Multiple items can safely share an index this way. The chains are also where the worst case lives: if every key landed in one bucket, a lookup would mean walking one long list. That's the O(n) the operations table warned you about.

Each operation on a chained hashmap follows the same shape:

Insertion (put): Hash the key with hash_function to get the index, then add the new key-value pair to the end of the linked list at that index.
Retrieval (get): Hash the key with hash_function to get the index, then walk the linked list at that index to find the matching key.
Deletion (remove): Same as retrieval, but remove the node once you find it.

Open Addressing

Open addressing is the other way to handle collisions, and it allocates nothing new. Chaining works, but every chain node costs extra memory and a pointer hop. Unlike chaining, which uses linked lists at each index, open addressing stores only one element per index. When a collision happens, the hashmap looks for the next available slot and puts the new key-value pair there. Overlapping elements get a new home somewhere else in the table:

Open addressing has a few different strategies for finding the next slot:

Linear probing: search the table one slot at a time until you find an empty one.
Quadratic probing: use a quadratic function to decide which slot to check next.
Double hashing: use a second hash function to figure out how far to jump for each probe.

Sets

Once you have the hashing machinery, a neat trick falls out: keep the lookup, drop one half of the pair. Sets, also called hash sets, are data structures that use hashing to store unique elements. While hashmaps store key-value pairs, sets only store the values and reject duplicates. Insertion, deletion, and lookup are all fast, which makes sets the go-to when you need to track what you've already seen or check if something exists.

Operations	Time	Space	Notes
Add	O(1)*	O(1)	Average O(1), worst O(n) with collisions. Maintains uniqueness through hashing
Remove	O(1)*	O(1)	Average O(1), worst O(n). Uses hash function to locate element
Search	O(1)*	O(1)	Average O(1), worst O(n). Checks existence using element's hash
Size	O(1)	O(1)	Returns number of elements. Typically tracked during modifications
Iterate	O(n)	O(1)	Must visit each element in the set sequentially
Clear	O(1)	O(1)	Can be implemented by resetting internal storage structure
Resize	O(n)	O(n)	Triggered when load factor threshold is exceeded. Rehashes all elements
Union	O(n+m)	O(n+m)	Combines two sets. n and m are sizes of input sets
Intersection	O(min(n,m))	O(min(n,m))	Finds common elements between sets. Iterates through smaller set
Difference	O(n)	O(n)	Returns elements in first set that aren't in second set

Sets work on the same principles as hashmaps, so we can build one using chaining with linked lists. The ListNode class holds a unique element and a pointer to the next node, which lets us form chains of distinct values at each index. The HashSet class starts with a fixed number of buckets, and each bucket begins with a dummy ListNode:

Best Practices

Hashmaps and sets show up in basically every optimal solution. If you can spot when to reach for one, a fast solution usually follows. Here are some tips for using them well:

Reach for a set when the only question is whether something has shown up before. Duplicates drop out on their own, and membership checks run in constant time, which covers visited cells, used characters, and anything else you only need to record once.

Algorithms

Two Pointers

→

A technique using two pointers to traverse data structures efficiently.

L →← R

Sliding Window

→

A technique for processing contiguous subarrays or substrings efficiently.

length = 3

Prefix Sums

→

A technique for preprocessing arrays to answer range sum queries in constant time.

↓↓↓↓↓

Sorting

→

Algorithms for arranging elements in a specific order for efficient processing.

Practice Problems

Two questions to check yourself before you start: what has to happen for a hashmap lookup to fall from O(1) to O(n)? And why resize at a 0.75 load factor instead of waiting until the table is completely full? Hashmaps trade space for time, and once you start spotting that tradeoff, you see it everywhere. Work through these classic problems to internalize when a hashmap or set turns an O(n²) brute force into a clean linear scan:

Hashmaps

Completed	Title		Status	Notes	Solution

Hashmaps

A filing system that does math on the key to figure out where the value lives, so lookups cost the same whether it holds ten entries or ten million.

Hashmaps

A filing system that does math on the key to figure out where the value lives, so lookups cost the same whether it holds ten entries or ten million.

Definition

Operations

Operations	Time	Space	Notes
Search	O(1)*	O(1)	Average O(1), worst case O(n) with collisions. Uses hash function to find bucket
Access	O(1)*	O(1)	Average O(1), worst case O(n) with collisions. Retrieves value using key's hash
Insert	O(1)*	O(1)	Average O(1), worst case O(n). May trigger resize if load factor exceeded
Delete	O(1)*	O(1)	Average O(1), worst case O(n). Must handle collision chain if present
Resize	O(n)	O(n)	Triggered when load factor exceeds threshold. Rehashes all elements
Get Keys	O(n)	O(n)	Returns all keys in the hashmap. Must traverse all buckets
Get Values	O(n)	O(n)	Returns all values in the hashmap. Must traverse all buckets

Key-Value Pairs

Hash Function

hash_function.py

# Hash Function: Converts key (string) into an index
def hash_function(key: str, size: int) -> int:
    hash_value = 0
    for index, char in enumerate(key):
        # Use position-dependent weighting
        hash_value += (index + 1) * ord(char)

    # Apply a prime multiplier for better distribution
    hash_value *= 2069

    # Ensure index is within the size range
    return hash_value % size

Hashmap Collisions

Resize and Rehash

resize_and_rehash.py

def resize(hashmap):
    # Double the size of the current hashmap
    size = len(hashmap) * 2
    # Use the doubled size to create a new hashmap and return it
    new_hashmap = [[] for _ in range(size)]
    return new_hashmap

def rehash(hashmap):
    # Use the "resize" function to generate a larger empty hashmap
    new_hashmap = resize(hashmap)
    for bucket in hashmap:
        for key, value in bucket:
            # Calculate the new index for each key-value pair
            new_index = hash(key) % len(new_hashmap)
            # Add the key-value pair to the corresponding bucket in the new hashmap
            new_hashmap[new_index].append([key, value])
    return new_hashmap

Separate Chaining

chained_hashmap.py

from typing import Optional

# Definition of a singly-linked ListNode
class ListNode:
    def __init__(self, key: int = -1, val: int = -1, next: Optional['ListNode'] = None):
        self.key = key
        self.val = val
        self.next = next

class MyHashMap:
    def __init__(self):
        # Our hashmap is just an array containing "size" number of ListNodes
        self.size = 1000
        self.hashmap = [ListNode() for i in range(self.size)]

    def hash_function(self, key: int) -> int:
        return key % self.size

    def put(self, key: int, value: int) -> None:
        # Hash the key and find the corresponding ListNode
        index = self.hash_function(key)
        cur = self.hashmap[index]
        while cur.next:
            # If we find the key, then rewrite the value
            if cur.next.key == key:
                cur.next.val = value
                return
            cur = cur.next
        # If we don't find the key, then add a new ListNode
        cur.next = ListNode(key, value)

    def get(self, key: int) -> int:
        # Hash the key and find the corresponding ListNode
        index = self.hash_function(key)
        cur = self.hashmap[index]
        while cur.next:
            # If we find the key, then return the value
            if cur.next.key == key:
                return cur.next.val
            cur = cur.next
        # If we don't find the key, then return -1
        return -1

    def remove(self, key: int) -> None:
        # Hash the key and find the corresponding ListNode
        index = self.hash_function(key)
        cur = self.hashmap[index]
        while cur.next:
            # If we find the key, then remove that ListNode
            if cur.next.key == key:
                cur.next = cur.next.next
                return
            cur = cur.next

Each operation on a chained hashmap follows the same shape:

Insertion (put): Hash the key with hash_function to get the index, then add the new key-value pair to the end of the linked list at that index.
Retrieval (get): Hash the key with hash_function to get the index, then walk the linked list at that index to find the matching key.
Deletion (remove): Same as retrieval, but remove the node once you find it.

Open Addressing

open_addressing.py

class MyHashMap:
    def __init__(self):
        # Initialize the hashmap with a fixed size
        self.size = 80_000
        self.hashmap = [None] * self.size

    def hash_function(self, key: int) -> int:
        # Simple hash function to determine the index
        return key % self.size

    def probe(self, index: int) -> int:
        # Linear probing: move to the next index, wrapping around if necessary
        return (index + 1) % self.size

    def put(self, key: int, value: int) -> None:
        # Hash the key to find the initial index
        index = self.hash_function(key)
        while self.hashmap[index] is not None:
            if self.hashmap[index][0] == key:
                # If we find the key, update the value
                self.hashmap[index] = (key, value)
                return
            # Collision occurred, try the next slot
            index = self.probe(index)
        # Empty slot found, insert the new key-value pair
        self.hashmap[index] = (key, value)

    def get(self, key: int) -> int:
        # Hash the key to find the initial index
        index = self.hash_function(key)
        while self.hashmap[index] is not None:
            if self.hashmap[index][0] == key:
                # If we find the key, return the value or try the next slot
                return self.hashmap[index][1]
            index = self.probe(index)
        # Key not found after probing all slots
        return -1

    def remove(self, key: int) -> None:
        # Hash the key to find the initial index
        index = self.hash_function(key)
        while self.hashmap[index] is not None:
            if self.hashmap[index][0] == key:
                # If we find the key, mark the slot as deleted
                self.hashmap[index] = None
                return
            # If we didn't find the key, try the next slot
            index = self.probe(index)

Open addressing has a few different strategies for finding the next slot:

Linear probing: search the table one slot at a time until you find an empty one.
Quadratic probing: use a quadratic function to decide which slot to check next.
Double hashing: use a second hash function to figure out how far to jump for each probe.

Sets

Operations	Time	Space	Notes
Add	O(1)*	O(1)	Average O(1), worst O(n) with collisions. Maintains uniqueness through hashing
Remove	O(1)*	O(1)	Average O(1), worst O(n). Uses hash function to locate element
Search	O(1)*	O(1)	Average O(1), worst O(n). Checks existence using element's hash
Size	O(1)	O(1)	Returns number of elements. Typically tracked during modifications
Iterate	O(n)	O(1)	Must visit each element in the set sequentially
Clear	O(1)	O(1)	Can be implemented by resetting internal storage structure
Resize	O(n)	O(n)	Triggered when load factor threshold is exceeded. Rehashes all elements
Union	O(n+m)	O(n+m)	Combines two sets. n and m are sizes of input sets
Intersection	O(min(n,m))	O(min(n,m))	Finds common elements between sets. Iterates through smaller set
Difference	O(n)	O(n)	Returns elements in first set that aren't in second set

hash_set.py

# Definition of a singly-linked ListNode
class ListNode:
    def __init__(self, key: int = -1, next: Optional['ListNode'] = None):
        self.key = key
        self.next = next

class MyHashSet:
    def __init__(self):
        # Our hash set is just an array containing "size" number of ListNodes
        self.size = 1000
        self.hashset = [ListNode() for _ in range(self.size)]

    def hash_function(self, key: int) -> int:
        return key % self.size

    def add(self, key: int) -> None:
        # Hash the key and find the corresponding ListNode
        index = self.hash_function(key)
        cur = self.hashset[index]
        while cur.next:
            # If we find the key, then it's already in the set
            if cur.next.key == key:
                return
            cur = cur.next
        # If we don't find the key, then add a new ListNode
        cur.next = ListNode(key)

    def contains(self, key: int) -> bool:
        # Hash the key and find the corresponding ListNode
        index = self.hash_function(key)
        cur = self.hashset[index]
        while cur.next:
            # If we find the key, then it's in the set
            if cur.next.key == key:
                return True
            cur = cur.next
        # If we don't find the key, then it's not in the set
        return False

    def remove(self, key: int) -> None:
        # Hash the key and find the corresponding ListNode
        index = self.hash_function(key)
        cur = self.hashset[index]
        while cur.next:
            # If we find the key, then remove that ListNode
            if cur.next.key == key:
                cur.next = cur.next.next
                return
            cur = cur.next

Best Practices

Hashmaps and sets show up in basically every optimal solution. If you can spot when to reach for one, a fast solution usually follows. Here are some tips for using them well:

Algorithms

Two Pointers

→

A technique using two pointers to traverse data structures efficiently.

L →← R

Sliding Window

→

A technique for processing contiguous subarrays or substrings efficiently.

length = 3

Prefix Sums

→

A technique for preprocessing arrays to answer range sum queries in constant time.

↓↓↓↓↓

Sorting

→

Algorithms for arranging elements in a specific order for efficient processing.

Practice Problems

Hashmaps

Completed	Title		Status	Notes	Solution

Hashmaps

Definition

Operations

Key-Value Pairs

Hash Function

Hashmap Collisions

Resize and Rehash

Separate Chaining

Open Addressing

Sets

Best Practices

When You Need Uniqueness

Key-Value Mapping

Efficient Data Lookup

Space Complexity Considerations

Collision Handling

Algorithms

Two Pointers

Sliding Window

Prefix Sums

Sorting

Practice Problems

Hashmaps

Hashmaps

Definition

Operations

Key-Value Pairs

Hash Function

Hashmap Collisions

Resize and Rehash

Separate Chaining

Open Addressing

Sets

Best Practices

When You Need Uniqueness

Key-Value Mapping

Efficient Data Lookup

Space Complexity Considerations

Collision Handling

Algorithms

Two Pointers

Sliding Window

Prefix Sums

Sorting

Practice Problems