Build a Hash Map From Scratch

Build a hash map from scratch in Python and solve Two Sum and Group Anagrams.

Introduction

30 Second Summary

Every time you search for a contact on your phone, autocomplete a username, or look up a product by ID, a hash map is doing the work behind the scenes. It is the single most-tested data structure in coding interviews.

In this project, you will build a hash map from scratch in Python, then use it to solve Two Sum and Group Anagrams. These are two of the most common interview problems at companies like Amazon, Google, and Meta.

What You'll Build

A Python file containing a complete hash map data structure built from scratch, plus solutions to two classic interview problems that use hash map patterns.

By the end of this project, you'll have:

  • A working HashMap class with put, get, remove, and collision handling via separate chaining.
  • A solved Two Sum problem using the complement-lookup pattern that turns O(n²) brute force into O(n).
  • A solved Group Anagrams problem using the canonical-key pattern for grouping items by shared properties.
  • Secret Mission: Add dynamic resizing so your hash map scales automatically when it gets full.

Are there any prerequisites?

You need basic Python knowledge (variables, loops, lists, and functions). No prior data structures or algorithms experience is required.

Set Up Your Project

You are about to build the single most-tested data structure in coding interviews from scratch.

Before writing any code, you need a clean project folder and confirmation that Python runs on your machine.

In this step, get ready to:
  • Verify Python 3 is installed and running.
  • Create your project folder and file.
  • Run a test script to confirm your setup.
Verify Python is installed

Your hash map implementation needs Python 3 to run. A quick version check confirms everything is in place.

  • Press Cmd+Space (macOS) or the Windows key (Windows) to open your search bar.
  • Type Terminal (macOS) or PowerShell (Windows) and press Enter to open it.
  • Check your Python version by running this command:
python3 --version

You should see a version number starting with Python 3 (for example, Python 3.14.6). On Windows, use python --version instead.

Command not found?

If you see an error like "command not found" or "not recognized", Python may not be installed or may not be in your system PATH.

Download and install it from python.org/downloads. During installation on Windows, check the box that says "Add Python to PATH".

Help me troubleshoot my Python installation

Create your project folder and file

All your code will live in a single folder on your Desktop. This keeps things easy to find.

  • Move to your Desktop by running this command:
cd ~/Desktop
  • Create your project folder and move into it by running these commands:
mkdir hashmap-project
cd hashmap-project
  • Confirm the folder exists by running:
ls

You should see an empty output because the folder is brand new.

  • Open your code editor.
  • Open the hashmap-project folder from your Desktop using your editor's File > Open Folder menu.
  • Create a new file called hashmap.py inside the hashmap-project folder.

Creating a file in VS Code

In VS Code, right-click in the Explorer sidebar and select New File. Type hashmap.py and press Enter. Other editors have similar options in their file menus.

Test your setup

A quick test confirms Python can find and run your file.

  • In hashmap.py, add the following code:
print("Setup working!")

What does this code do?

The print() function outputs text to your terminal. If you see the message, it proves Python found your file and ran it successfully.

  • Save hashmap.py.
  • Switch back to your terminal and run the file with this command:
python3 hashmap.py

You should see Setup working! printed in your terminal. On Windows, use python hashmap.py instead.

Seeing 'No such file or directory'?

This means your terminal is not in the hashmap-project folder. Run cd ~/Desktop/hashmap-project and try again.

Also check that the file is named exactly hashmap.py (no extra spaces or capital letters).

Help me figure out why Python can't find my file

✔️ Awesome, I've got everything!

Great. Make sure you have saved hashmap.py before moving on.

ⓧ I'd like to double check the full code

Here is the complete hashmap.py file at this point:

print("Setup working!")

Your workspace is ready. Next up, you'll build the HashMap class itself with a hash function and collision-handling buckets.

Build Your Hash Map

In the previous step, you set up your project and confirmed Python runs correctly. Now it's time to build the core data structure itself.

A hash map needs three things: a way to convert keys into array positions (the hash function), storage for key-value pairs (buckets), and a strategy for handling collisions (when two keys land in the same position). You'll implement all of this piece by piece.

In this step, get ready to:
  • Create the HashMap class with a hash function that maps keys to bucket indices.
  • Implement put and get methods for storing and retrieving data.
  • Implement remove and display methods to complete your hash map.
Create the HashMap class with the hash function

The foundation of any hash map is a fixed-size array of "buckets" and a function that converts a key into an index pointing to one of those buckets. Python's built-in hash() function handles the heavy lifting of producing an integer from any key.

  • In hashmap.py, delete the print("Setup working!") line.
  • Replace it with the following class definition:
class HashMap:
    def __init__(self, size=10):
        """Initialize the hash map with a fixed number of buckets."""
        self.size = size
        self.buckets = [[] for _ in range(size)]
        self.count = 0

    def _hash(self, key):
        """Compute the bucket index for a given key."""
        return hash(key) % self.size

What does this code do?

self.size sets how many buckets your hash map has. More buckets means fewer collisions, but uses more memory.

self.buckets = [[] for _ in range(size)] creates a list of empty lists. Each inner list is a "bucket" that will hold key-value pairs. Using a list comprehension ensures each bucket is an independent list.

self.count tracks how many items are stored. The _hash method uses hash(key) % self.size to convert any key into a valid index between 0 and size-1.

  • Save hashmap.py.
  • Run your file to confirm there are no syntax errors:
python3 hashmap.py
  • You should see no output and no error messages. This means your class definition is syntactically valid.

Seeing a syntax error?

  • Check that the indentation uses consistent spaces (4 spaces per level). Mixing tabs and spaces causes IndentationError.
  • Make sure the triple-quoted docstrings have matching """ on both sides.
  • Confirm you deleted the old print("Setup working!") line entirely. Leftover code outside the class causes errors.

Help me fix a syntax error in my HashMap class definition.

Implement put and get

With the structure in place, your hash map needs methods to actually store and retrieve data. The put method handles insertions and updates, while get handles lookups.

  • In hashmap.py, add the following put method inside the HashMap class, below the _hash method:
    def put(self, key, value):
        """Insert a key-value pair, or update the value if the key exists."""
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.count += 1

What does this code do?

The put method first hashes the key to find the correct bucket. Then it scans that bucket to check if the key already exists.

If the key is found, it updates the value in place. If not, it appends a new (key, value) tuple to the bucket. This scanning step is how separate chaining handles collisions. Multiple keys can live in the same bucket as separate tuples.

  • Save hashmap.py and run python3 hashmap.py to confirm no errors.
  • You should see no output. The method is defined but not called yet.

Getting an IndentationError?

  • The def put line must be indented exactly one level (4 spaces) inside the class, matching def _hash above it.
  • The body of put (everything after the def line) must be indented two levels (8 spaces) from the left margin.

Help me fix an indentation error in my put method.

  • Now add the get method directly below put:
    def get(self, key):
        """Retrieve the value for a given key, or None if not found."""
        index = self._hash(key)
        bucket = self.buckets[index]
        for k, v in bucket:
            if k == key:
                return v
        return None

What does this code do?

The get method hashes the key to find the right bucket, then scans through the tuples in that bucket looking for a matching key.

If it finds a match, it returns the value. If it reaches the end of the bucket without finding the key, it returns None. This is O(1) on average because most buckets contain very few items.

  • Save hashmap.py and run python3 hashmap.py to confirm no errors.
  • You should still see no output and no error messages.

Seeing a NameError?

  • Make sure get is inside the class (indented one level) and not accidentally at the top level of the file.
  • Verify you have self as the first parameter in def get(self, key).

Help me debug a NameError in my get method.

Implement remove and display

Your hash map can store and retrieve data, but it also needs to delete items and let you inspect its internal state. The remove method handles deletion, and display lets you see exactly how items are distributed across buckets.

  • Add the remove method below get in your HashMap class:
    def remove(self, key):
        """Remove a key-value pair. Returns True if found, False otherwise."""
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.count -= 1
                return True
        return False

What does this code do?

The remove method follows the same pattern: hash the key, find the bucket, scan for the match. When it finds the key, it uses bucket.pop(i) to remove the tuple at that index and decrements the count.

Returning True or False lets callers know whether the key existed. This is the same approach Python's built-in data structures use.

  • Save hashmap.py and run python3 hashmap.py to confirm no errors.
  • You won't see output yet. The next chunk adds display so you can visualize your hash map's internals.
  • Add the display method below remove:
    def display(self):
        """Display the hash map's internal structure."""
        print(f"HashMap (size={self.size}, items={self.count})")
        for i, bucket in enumerate(self.buckets):
            if bucket:
                print(f"  Bucket {i}: {bucket}")
            else:
                print(f"  Bucket {i}: (empty)")

What does this code do?

The display method prints every bucket in your hash map, showing which ones hold data and which are empty. This is how you'll visualize collisions in the next step.

This pattern is called separate chaining. Each bucket is a "chain" (list) of items that hashed to the same index. When you call display(), you'll see exactly which keys share a bucket.

  • Save hashmap.py.
  • Verify your complete class works by running this test command:
python3 -c "from hashmap import HashMap; m = HashMap(5); m.put('hello', 1); print(m.get('hello')); m.remove('hello'); print(m.get('hello'))"
  • You should see 1 on the first line (the value you stored) and None on the second line (the key was removed).

Seeing an ImportError or unexpected output?

  • Make sure your terminal is in the hashmap-project folder. Run ls and confirm you see hashmap.py listed.
  • Check that hashmap.py does not contain the old print("Setup working!") line. Any top-level print statement will add unexpected output.
  • If you see None for both lines, your put method may not be appending correctly. Double check that bucket.append((key, value)) is outside the for loop (indented at the same level as the loop, not inside it).

Help me debug my HashMap class. The test command isn't producing the expected output.

✔️ Awesome, I've got everything!

Great. Double check you've saved hashmap.py and you're ready to move on.

ⓧ I'd like to double check the full code

Here's the complete hashmap.py file at this point:

class HashMap:
    def __init__(self, size=10):
        """Initialize the hash map with a fixed number of buckets."""
        self.size = size
        self.buckets = [[] for _ in range(size)]
        self.count = 0

    def _hash(self, key):
        """Compute the bucket index for a given key."""
        return hash(key) % self.size

    def put(self, key, value):
        """Insert a key-value pair, or update the value if the key exists."""
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.count += 1

    def get(self, key):
        """Retrieve the value for a given key, or None if not found."""
        index = self._hash(key)
        bucket = self.buckets[index]
        for k, v in bucket:
            if k == key:
                return v
        return None

    def remove(self, key):
        """Remove a key-value pair. Returns True if found, False otherwise."""
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.count -= 1
                return True
        return False

    def display(self):
        """Display the hash map's internal structure."""
        print(f"HashMap (size={self.size}, items={self.count})")
        for i, bucket in enumerate(self.buckets):
            if bucket:
                print(f"  Bucket {i}: {bucket}")
            else:
                print(f"  Bucket {i}: (empty)")

Your hash map is fully functional. Next up, you'll force collisions to happen and see exactly how your separate chaining handles them.

See Collisions in Action

You've built a complete hash map with put, get, remove, and display methods. Now it's time to run it and see what happens when multiple keys land in the same bucket.

How do you know your hash map actually handles collisions correctly? In this step, you'll force collisions by cramming 6 items into only 3 buckets and watch your separate chaining work in real time.

In this step, get ready to:
  • Test your hash map with inserts, lookups, updates, and removals.
  • Force collisions by creating a hash map with only 3 buckets and 6 items.
  • Summarize Big-O time complexity for interview reference.
Test your hash map with basic operations

Before exploring collisions, you need to confirm that every method works as expected. You'll create a HashMap, insert items, retrieve them, update one, and remove one.

  • In hashmap.py, scroll to the bottom of the file (below the display method) and add this test block:
# === Test the Hash Map ===
print("=== Building and Testing Your Hash Map ===\n")

my_map = HashMap(size=5)

my_map.put("apple", 3)
my_map.put("banana", 5)
my_map.put("cherry", 7)
my_map.put("date", 2)
my_map.put("elderberry", 9)

print("After inserting 5 items:")
my_map.display()

print(f"\nGet 'apple': {my_map.get('apple')}")
print(f"Get 'banana': {my_map.get('banana')}")
print(f"Get 'grape' (not in map): {my_map.get('grape')}")

my_map.put("apple", 10)
print(f"\nAfter updating 'apple' to 10: {my_map.get('apple')}")

my_map.remove("banana")
print(f"After removing 'banana': {my_map.get('banana')}")

What does this code do?

  • HashMap(size=5) creates a hash map with 5 buckets. Five items across 5 buckets gives collisions a decent chance of happening.
  • put inserts key-value pairs. Calling put("apple", 10) a second time updates the existing value instead of creating a duplicate.
  • get("grape") returns None because "grape" was never inserted. This confirms your lookup handles missing keys gracefully.
  • remove("banana") deletes the pair, so the following get returns None.
  • Save hashmap.py.
  • Run the file by running this command:
python3 hashmap.py

You should see output showing all 5 items distributed across buckets, correct values for get calls, the updated value of 10 for "apple", and None after removing "banana".

Your bucket numbers may differ

Python randomizes hash values each time you start a new process. Your items may land in different bucket numbers than someone else's. This is normal and expected. What matters is that the values come back correctly.

Seeing a NameError or empty output?

  • Make sure your test code is OUTSIDE the class (not indented under it). It should sit at the far left of the file, below the class definition.
  • Check that there is a blank line between the last method of the class and your # === Test the Hash Map === comment.
  • If you see NameError: name 'HashMap' is not defined, your test code may be above the class definition instead of below it.

Help me debug my HashMap test output.

Force collisions and observe them

A collision happens when two different keys hash to the same bucket index. With 5 buckets you might see a collision or two, but to guarantee them you need to shrink the bucket count below the number of items.

  • At the bottom of hashmap.py (below your test block), add this collision demonstration:
# === Demonstrating Collisions ===
print("\n=== Demonstrating Collisions ===\n")

small_map = HashMap(size=3)
words = ["cat", "dog", "bird", "fish", "ant", "bee"]
for word in words:
    small_map.put(word, len(word))
    print(f"  Inserted '{word}' -> bucket {small_map._hash(word)}")

print("\nFinal state (notice multiple items in same bucket = collision!):")
small_map.display()

What does this code do?

  • HashMap(size=3) creates only 3 buckets for 6 items. Collisions are mathematically guaranteed.
  • Each word's value is its length (len(word)), giving you a quick way to verify the right value comes back.
  • The print inside the loop shows exactly which bucket each key lands in. You'll see multiple keys mapping to the same bucket number.
  • display() reveals the internal structure. Buckets with multiple tuples are your collisions, handled by separate chaining.

What is separate chaining?

Separate chaining is a collision-handling strategy where each bucket stores a list (chain) of all items that hash to the same index. When you call get, the hash map jumps to the correct bucket in O(1), then scans the chain to find the matching key.

Your display() output shows this directly. A bucket with [("cat", 3), ("fish", 4)] means both keys collided and live as separate tuples in the same chain.

  • Save hashmap.py and run it again:
python3 hashmap.py

In the collision demo section, you should see multiple keys mapping to the same bucket number. The final display() output shows at least one bucket containing two or more tuples.

Every bucket only has one item?

  • Double-check that you passed size=3 when creating small_map. Using size=10 (the default) spreads 6 items too thin to collide reliably.
  • Confirm you have all 6 words in the list: "cat", "dog", "bird", "fish", "ant", "bee".

Help me debug my collision demonstration.

Understand Big-O and add a reference comment

Interviewers don't just want you to use a hash map. They want you to explain its time complexity trade-offs. The collision demo you just ran is the key to understanding this.

What is Big-O for a hash map?

Big-O describes how performance scales as input grows. For a hash map with separate chaining:

  • Average case: O(1) for put, get, and remove. The hash function distributes keys evenly across buckets, so each bucket has roughly one item to scan.
  • Worst case: O(n) if ALL keys collide into one bucket. The single chain becomes a list of n items you must scan linearly.
  • Load factor = items / buckets. When this ratio gets high, collisions multiply and performance degrades toward O(n).
  • At the bottom of hashmap.py, add this comment block as a quick-reference for interviews:
# Big-O Summary:
# Average case: O(1) for put, get, remove (hash distributes keys evenly)
# Worst case: O(n) if all keys collide into one bucket
# Load factor = items / buckets. High load factor = more collisions = slower.

Why keep this as a comment?

These three facts (average O(1), worst O(n), load factor) are the exact talking points interviewers expect when they ask "what's the time complexity of a hash map?" Keeping them in your file gives you a quick refresher before interviews.

  • Save hashmap.py.

Extra for Experts: Why does the worst case matter?

If an attacker can predict your hash function, they can craft inputs that all collide into one bucket. This is called a hash-collision denial-of-service attack. Python protects against this by randomizing hash values per process (which is also why your bucket numbers change between runs).

✔️ Awesome, I've got everything!

Great. Double check you've saved your file.

ⓧ I'd like to double check the full code

Here is the complete hashmap.py as it should look at the end of this step:

class HashMap:
    def __init__(self, size=10):
        """Initialize the hash map with a fixed number of buckets."""
        self.size = size
        self.buckets = [[] for _ in range(size)]
        self.count = 0

    def _hash(self, key):
        """Compute the bucket index for a given key."""
        return hash(key) % self.size

    def put(self, key, value):
        """Insert a key-value pair, or update the value if the key exists."""
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.count += 1

    def get(self, key):
        """Retrieve the value for a given key, or None if not found."""
        index = self._hash(key)
        bucket = self.buckets[index]
        for k, v in bucket:
            if k == key:
                return v
        return None

    def remove(self, key):
        """Remove a key-value pair. Returns True if found, False otherwise."""
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.count -= 1
                return True
        return False

    def display(self):
        """Display the hash map's internal structure."""
        print(f"HashMap (size={self.size}, items={self.count})")
        for i, bucket in enumerate(self.buckets):
            if bucket:
                print(f"  Bucket {i}: {bucket}")
            else:
                print(f"  Bucket {i}: (empty)")


# === Test the Hash Map ===
print("=== Building and Testing Your Hash Map ===\n")

my_map = HashMap(size=5)

my_map.put("apple", 3)
my_map.put("banana", 5)
my_map.put("cherry", 7)
my_map.put("date", 2)
my_map.put("elderberry", 9)

print("After inserting 5 items:")
my_map.display()

print(f"\nGet 'apple': {my_map.get('apple')}")
print(f"Get 'banana': {my_map.get('banana')}")
print(f"Get 'grape' (not in map): {my_map.get('grape')}")

my_map.put("apple", 10)
print(f"\nAfter updating 'apple' to 10: {my_map.get('apple')}")

my_map.remove("banana")
print(f"After removing 'banana': {my_map.get('banana')}")


# === Demonstrating Collisions ===
print("\n=== Demonstrating Collisions ===\n")

small_map = HashMap(size=3)
words = ["cat", "dog", "bird", "fish", "ant", "bee"]
for word in words:
    small_map.put(word, len(word))
    print(f"  Inserted '{word}' -> bucket {small_map._hash(word)}")

print("\nFinal state (notice multiple items in same bucket = collision!):")
small_map.display()

# Big-O Summary:
# Average case: O(1) for put, get, remove (hash distributes keys evenly)
# Worst case: O(n) if all keys collide into one bucket
# Load factor = items / buckets. High load factor = more collisions = slower.

Your hash map is tested, proven to handle collisions, and you understand its performance profile. Next up, you'll use it to solve Two Sum, the most-asked coding interview question at Amazon, Google, and Meta.

Solve Two Sum

You now have a working hash map that handles collisions gracefully. Time to put it to work on the most-asked coding interview question of all time.

Two Sum is the classic problem that shows up at Amazon, Google, and Meta. The brute force solution checks every pair of numbers, which is O(n²). Your hash map can solve it in O(n) with a single pass through the array.

In this step, get ready to:
  • Understand the complement-lookup pattern that turns O(n²) into O(n).
  • Implement a two_sum function using your custom HashMap.
  • Test with multiple cases and verify the results.
Understand the Two Sum problem and the complement-lookup pattern

The Two Sum problem asks: given an array of numbers and a target, find two numbers that add up to the target and return their indices.

The brute force approach checks every possible pair. That means two nested loops and O(n²) time. A hash map solves this in a single pass.

What is the complement-lookup pattern?

For each number in the array, you compute its complement: target - number. Then you check if that complement already exists in your hash map.

If the complement is in the map, you found your pair. If not, store the current number and move on. Each lookup is O(1), and you only walk the array once. That gives you O(n) total.

Implement the two_sum function
  • In hashmap.py, scroll to the bottom of the file (below the Big-O comment block).
  • Add the Two Sum section header and function by copying this code at the bottom:

# === Solve Two Sum ===
print("\n=== Solving Two Sum ===\n")


def two_sum(nums, target):
    """
    Find two numbers that add up to target. Return their indices.

    Pattern: Complement lookup
    For each number, check if (target - number) already exists in our map.
    Time: O(n) - one pass through the array
    Space: O(n) - storing up to n items in the map
    """
    seen = HashMap(size=len(nums))

    for i, num in enumerate(nums):
        complement = target - num
        if seen.get(complement) is not None:
            return [seen.get(complement), i]
        seen.put(num, i)

    return None

What does this code do?

  • seen = HashMap(size=len(nums)) creates a hash map sized to fit all the numbers. Keys will be numbers you have already visited, and values will be their indices.
  • complement = target - num computes what other number you would need to hit the target.
  • seen.get(complement) checks if you have already seen that complement earlier in the array. If yes, you return both indices immediately.
  • seen.put(num, i) stores the current number and its index so future iterations can find it as a complement.
  • Save hashmap.py.

You will not see a change yet. The function is defined but not called. The next chunk adds test code that runs it.

Test with multiple cases and trace through the logic

Now you will call two_sum with two different inputs and print the results to confirm your function works correctly.

  • Add this test code directly below your two_sum function:

nums = [2, 7, 11, 15]
target = 9
result = two_sum(nums, target)
print(f"nums = {nums}, target = {target}")
print(f"Result: indices {result}")
print(f"Verification: {nums[result[0]]} + {nums[result[1]]} = {nums[result[0]] + nums[result[1]]}")

nums2 = [3, 2, 4]
target2 = 6
result2 = two_sum(nums2, target2)
print(f"\nnums = {nums2}, target = {target2}")
print(f"Result: indices {result2}")
print(f"Verification: {nums2[result2[0]]} + {nums2[result2[1]]} = {nums2[result2[0]] + nums2[result2[1]]}")

What does this test code do?

  • The first test uses [2, 7, 11, 15] with target 9. Since 2 + 7 = 9, the function should return [0, 1] (the indices of 2 and 7).
  • The second test uses [3, 2, 4] with target 6. Since 2 + 4 = 6, the function should return [1, 2] (the indices of 2 and 4).
  • The verification line proves the result by adding the numbers at those indices and showing they equal the target.
  • Save hashmap.py.
  • Run your script in the terminal by running:
python3 hashmap.py
  • Scroll down to the "Solving Two Sum" section of the output. You should see Result: indices [0, 1] for the first test and Result: indices [1, 2] for the second test.

Seeing None or incorrect indices?

  • Make sure your two_sum function checks the complement BEFORE calling seen.put(num, i). If you store first and check second, a number might match itself.
  • Verify the function is placed after your HashMap class definition. Python needs the class to exist before two_sum can use it.
  • Check that you are using seen.get(complement) is not None rather than just seen.get(complement). The value stored could be index 0, which is falsy in Python.

Why is my two_sum function returning None or wrong indices?

Why is this O(n) instead of O(n²)?

The brute force approach uses two nested loops to check every pair. That means for each of the n elements, you check n-1 others.

With a hash map, you walk the array exactly once. At each step, you do one O(1) lookup and one O(1) insert. One pass through n elements with constant-time work at each step gives you O(n) total.

✔️ Awesome, I've got everything!

Great. Double check you have saved hashmap.py and that both test cases print the correct indices.

ⓧ I'd like to double check the full code

Here is the complete hashmap.py file up to this point:

class HashMap:
    def __init__(self, size=10):
        """Initialize the hash map with a fixed number of buckets."""
        self.size = size
        self.buckets = [[] for _ in range(size)]
        self.count = 0

    def _hash(self, key):
        """Compute the bucket index for a given key."""
        return hash(key) % self.size

    def put(self, key, value):
        """Insert a key-value pair, or update the value if the key exists."""
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.count += 1

    def get(self, key):
        """Retrieve the value for a given key, or None if not found."""
        index = self._hash(key)
        bucket = self.buckets[index]
        for k, v in bucket:
            if k == key:
                return v
        return None

    def remove(self, key):
        """Remove a key-value pair. Returns True if found, False otherwise."""
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.count -= 1
                return True
        return False

    def display(self):
        """Display the hash map's internal structure."""
        print(f"HashMap (size={self.size}, items={self.count})")
        for i, bucket in enumerate(self.buckets):
            if bucket:
                print(f"  Bucket {i}: {bucket}")
            else:
                print(f"  Bucket {i}: (empty)")


# === Test the Hash Map ===
print("=== Building and Testing Your Hash Map ===\n")

my_map = HashMap(size=5)

my_map.put("apple", 3)
my_map.put("banana", 5)
my_map.put("cherry", 7)
my_map.put("date", 2)
my_map.put("elderberry", 9)

print("After inserting 5 items:")
my_map.display()

print(f"\nGet 'apple': {my_map.get('apple')}")
print(f"Get 'banana': {my_map.get('banana')}")
print(f"Get 'grape' (not in map): {my_map.get('grape')}")

my_map.put("apple", 10)
print(f"\nAfter updating 'apple' to 10: {my_map.get('apple')}")

my_map.remove("banana")
print(f"After removing 'banana': {my_map.get('banana')}")


# === Demonstrating Collisions ===
print("\n=== Demonstrating Collisions ===\n")

small_map = HashMap(size=3)
words = ["cat", "dog", "bird", "fish", "ant", "bee"]
for word in words:
    small_map.put(word, len(word))
    print(f"  Inserted '{word}' -> bucket {small_map._hash(word)}")

print("\nFinal state (notice multiple items in same bucket = collision!):")
small_map.display()

# Big-O Summary:
# Average case: O(1) for put, get, remove (hash distributes keys evenly)
# Worst case: O(n) if all keys collide into one bucket
# Load factor = items / buckets. High load factor = more collisions = slower.


# === Solve Two Sum ===
print("\n=== Solving Two Sum ===\n")


def two_sum(nums, target):
    """
    Find two numbers that add up to target. Return their indices.

    Pattern: Complement lookup
    For each number, check if (target - number) already exists in our map.
    Time: O(n) - one pass through the array
    Space: O(n) - storing up to n items in the map
    """
    seen = HashMap(size=len(nums))

    for i, num in enumerate(nums):
        complement = target - num
        if seen.get(complement) is not None:
            return [seen.get(complement), i]
        seen.put(num, i)

    return None


nums = [2, 7, 11, 15]
target = 9
result = two_sum(nums, target)
print(f"nums = {nums}, target = {target}")
print(f"Result: indices {result}")
print(f"Verification: {nums[result[0]]} + {nums[result[1]]} = {nums[result[0]] + nums[result[1]]}")

nums2 = [3, 2, 4]
target2 = 6
result2 = two_sum(nums2, target2)
print(f"\nnums = {nums2}, target = {target2}")
print(f"Result: indices {result2}")
print(f"Verification: {nums2[result2[0]]} + {nums2[result2[1]]} = {nums2[result2[0]] + nums2[result2[1]]}")

You just solved the most-asked interview question using your own hash map. Next up, you will tackle Group Anagrams using a different hash map pattern: grouping items by a canonical key.

Solve Group Anagrams

In the last step, you solved Two Sum using the complement-lookup pattern. That pattern finds a single pair by checking what you have already seen.

Group Anagrams is a different style of problem. Instead of finding one answer, you need to organize an entire list into groups. The pattern you will learn here (grouping by canonical key) appears in roughly 30% of hash map interview questions.

In this step, get ready to:
  • Understand the canonical-key grouping pattern.
  • Implement a group_anagrams function using Python's built-in dict.
  • Test with multiple word lists and analyze time complexity.
Understand the problem and pattern

The Group Anagrams problem gives you a list of words and asks you to group words that are anagrams of each other. Anagrams are words with the same letters in a different order.

For example, "eat", "tea", and "ate" are all anagrams because they contain the same letters: a, e, and t.

What is the canonical-key pattern?

The trick is to find something that all anagrams share. If you sort the letters of any anagram, you get the same result: sorted("eat"), sorted("tea"), and sorted("ate") all produce ['a', 'e', 't'].

This sorted form is the "canonical key." You use it as the hash map key, and group all words that share the same key together. This is the grouping/bucketing pattern: transform each item into a canonical key, then group items that share the same key.

Implement group_anagrams using Python's built-in dict
  • In hashmap.py, scroll to the bottom of your file (below the Two Sum test code).
  • Add the Group Anagrams section header and function by copying this code:
# === Solve Group Anagrams ===
print("\n=== Solving Group Anagrams ===\n")


def group_anagrams(words):
    """
    Group words that are anagrams of each other.

    Pattern: Grouping by canonical key
    Anagrams share the same sorted letters: sorted("eat") == sorted("tea") == ['a','e','t']
    Use the sorted form as the key, group words sharing that key.
    Time: O(n * k log k) where n = number of words, k = max word length
    Space: O(n) - storing all words in the map
    """
    groups = {}

    for word in words:
        key = "".join(sorted(word))
        if key not in groups:
            groups[key] = []
        groups[key].append(word)

    return list(groups.values())

What does this code do?

This function takes a list of words and groups anagrams together.

  • groups = {} creates an empty Python dictionary to store groups.
  • key = "".join(sorted(word)) sorts the letters of each word and joins them back into a string. This is the canonical key.
  • If the key does not exist yet, we create a new empty list. Then we append the word to that key's list.
  • list(groups.values()) returns all the grouped lists.

Why use Python's built-in dict here?

In real interviews, you use Python's built-in dict for solutions (not a custom HashMap). Your custom implementation taught you how hash maps work under the hood.

Now that you understand collisions, chaining, and hashing, you can use dict with confidence because you know exactly what it does internally.

You will not see new output yet. The next chunk adds test code that calls this function.

Test and explain the time complexity
  • Add the test code below your group_anagrams function by copying this code:

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
result = group_anagrams(words)
print(f"Input: {words}")
print(f"Grouped anagrams:")
for group in result:
    print(f"  {group}")

words2 = ["listen", "silent", "hello", "world", "enlist"]
result2 = group_anagrams(words2)
print(f"\nInput: {words2}")
print(f"Grouped anagrams:")
for group in result2:
    print(f"  {group}")

What does this test code do?

  • The first test uses ["eat", "tea", "tan", "ate", "nat", "bat"]. Words like "eat", "tea", and "ate" should end up in the same group because they all sort to "aet".
  • The second test uses ["listen", "silent", "hello", "world", "enlist"]. "listen", "silent", and "enlist" are all anagrams of each other.
  • Words with no anagram partner (like "hello" and "world") each form their own group of one.
  • Save hashmap.py.
  • Run your file by running this command:
python3 hashmap.py
  • Scroll to the bottom of the output. You should see the "Solving Group Anagrams" section with words grouped by their anagram family.

What is the time complexity?

The time complexity is O(n * k log k), where n is the number of words and k is the maximum word length. Sorting each word takes O(k log k), and you do it n times.

An alternative approach uses a tuple of character counts as the key instead of the sorted string. This avoids the sort and brings complexity to O(n * k). In interviews, mentioning this alternative shows deeper understanding even if you implement the sorted version.

Not seeing grouped output?

  • Make sure the test code is outside and below the group_anagrams function (not indented inside it).
  • Check that you are using groups = {} (curly braces for a dict), not groups = [] (square brackets for a list).
  • Verify key = "".join(sorted(word)) uses an empty string "" with no space between the quotes.

Why aren't my anagrams grouping correctly?

✔️ Awesome, I've got everything!

Great. Make sure you have saved hashmap.py.

ⓧ I'd like to double check the full code

Here is the complete hashmap.py file at this point.

class HashMap:
    def __init__(self, size=10):
        """Initialize the hash map with a fixed number of buckets."""
        self.size = size
        self.buckets = [[] for _ in range(size)]
        self.count = 0

    def _hash(self, key):
        """Compute the bucket index for a given key."""
        return hash(key) % self.size

    def put(self, key, value):
        """Insert a key-value pair, or update the value if the key exists."""
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.count += 1

    def get(self, key):
        """Retrieve the value for a given key, or None if not found."""
        index = self._hash(key)
        bucket = self.buckets[index]
        for k, v in bucket:
            if k == key:
                return v
        return None

    def remove(self, key):
        """Remove a key-value pair. Returns True if found, False otherwise."""
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.count -= 1
                return True
        return False

    def display(self):
        """Display the hash map's internal structure."""
        print(f"HashMap (size={self.size}, items={self.count})")
        for i, bucket in enumerate(self.buckets):
            if bucket:
                print(f"  Bucket {i}: {bucket}")
            else:
                print(f"  Bucket {i}: (empty)")


# === Test the Hash Map ===
print("=== Building and Testing Your Hash Map ===\n")

my_map = HashMap(size=5)

my_map.put("apple", 3)
my_map.put("banana", 5)
my_map.put("cherry", 7)
my_map.put("date", 2)
my_map.put("elderberry", 9)

print("After inserting 5 items:")
my_map.display()

print(f"\nGet 'apple': {my_map.get('apple')}")
print(f"Get 'banana': {my_map.get('banana')}")
print(f"Get 'grape' (not in map): {my_map.get('grape')}")

my_map.put("apple", 10)
print(f"\nAfter updating 'apple' to 10: {my_map.get('apple')}")

my_map.remove("banana")
print(f"After removing 'banana': {my_map.get('banana')}")


# === Demonstrating Collisions ===
print("\n=== Demonstrating Collisions ===\n")

small_map = HashMap(size=3)
words = ["cat", "dog", "bird", "fish", "ant", "bee"]
for word in words:
    small_map.put(word, len(word))
    print(f"  Inserted '{word}' -> bucket {small_map._hash(word)}")

print("\nFinal state (notice multiple items in same bucket = collision!):")
small_map.display()

# Big-O Summary:
# Average case: O(1) for put, get, remove (hash distributes keys evenly)
# Worst case: O(n) if all keys collide into one bucket
# Load factor = items / buckets. High load factor = more collisions = slower.


# === Solve Two Sum ===
print("\n=== Solving Two Sum ===\n")


def two_sum(nums, target):
    """
    Find two numbers that add up to target. Return their indices.

    Pattern: Complement lookup
    For each number, check if (target - number) already exists in our map.
    Time: O(n) - one pass through the array
    Space: O(n) - storing up to n items in the map
    """
    seen = HashMap(size=len(nums))

    for i, num in enumerate(nums):
        complement = target - num
        if seen.get(complement) is not None:
            return [seen.get(complement), i]
        seen.put(num, i)

    return None


nums = [2, 7, 11, 15]
target = 9
result = two_sum(nums, target)
print(f"nums = {nums}, target = {target}")
print(f"Result: indices {result}")
print(f"Verification: {nums[result[0]]} + {nums[result[1]]} = {nums[result[0]] + nums[result[1]]}")

nums2 = [3, 2, 4]
target2 = 6
result2 = two_sum(nums2, target2)
print(f"\nnums = {nums2}, target = {target2}")
print(f"Result: indices {result2}")
print(f"Verification: {nums2[result2[0]]} + {nums2[result2[1]]} = {nums2[result2[0]] + nums2[result2[1]]}")


# === Solve Group Anagrams ===
print("\n=== Solving Group Anagrams ===\n")


def group_anagrams(words):
    """
    Group words that are anagrams of each other.

    Pattern: Grouping by canonical key
    Anagrams share the same sorted letters: sorted("eat") == sorted("tea") == ['a','e','t']
    Use the sorted form as the key, group words sharing that key.
    Time: O(n * k log k) where n = number of words, k = max word length
    Space: O(n) - storing all words in the map
    """
    groups = {}

    for word in words:
        key = "".join(sorted(word))
        if key not in groups:
            groups[key] = []
        groups[key].append(word)

    return list(groups.values())


words = ["eat", "tea", "tan", "ate", "nat", "bat"]
result = group_anagrams(words)
print(f"Input: {words}")
print(f"Grouped anagrams:")
for group in result:
    print(f"  {group}")

words2 = ["listen", "silent", "hello", "world", "enlist"]
result2 = group_anagrams(words2)
print(f"\nInput: {words2}")
print(f"Grouped anagrams:")
for group in result2:
    print(f"  {group}")

Secret mission

Add Dynamic Resizing

Your hash map has a fixed number of buckets. What happens when it fills up? Collisions pile up, performance degrades, and O(1) becomes a lie. In this mission, you'll add automatic resizing so your hash map scales itself.

Clean Up Your Resources

Clean Up Your Resources

This project runs entirely locally, so there are no ongoing costs. Your project files live on your machine and nothing is running in the background.

Decide whether to keep your files for future reference, or delete them entirely.

Resources you used:

  • Local folder hashmap-project containing hashmap.py.

Keep everything running

No action needed. Choose this if you want to keep your hash map implementation for reference or plan to extend it further.

  • Your hashmap-project folder stays on your Desktop with all your code intact.
  • You can re-run python3 hashmap.py any time to see your hash map in action.

Pause - I'll come back to this later

Nothing to pause. Since this project is entirely local with no running processes, your files simply sit on disk until you return.

  • Your hashmap-project folder remains on your Desktop.
  • No background processes are running.

Delete - I don't want to use this again

Remove all project files from your machine.

  • Delete the project folder by running this command in your terminal:

macOS

rm -rf ~/Desktop/hashmap-project

Windows

rmdir /s /q %USERPROFILE%\Desktop\hashmap-project
  • Confirm deletion by running:
ls ~/Desktop
  • You should no longer see hashmap-project in the output.

Nice Work!

Nice Work!

Nice work! You just built the single most important data structure in coding interviews from the ground up, and used it to solve two of the most common interview patterns.

You've learned how to:

  • Build a hash map from scratch with put, get, remove, and separate chaining for collision handling.
  • Solve Two Sum using the complement-lookup pattern to turn O(n²) brute force into a single O(n) pass.
  • Solve Group Anagrams using the canonical-key pattern to group items by their sorted form.
  • Secret Mission: Added dynamic resizing with rehashing so your hash map scales automatically when the load factor exceeds 0.7.

Ready to quiz yourself?