I've seen a lot of developers try to roll their own hash table for the first time, and almost everyone makes the same mistake. They focus so much on the "hash" part that they completely forget about the "collision" part. Let's look at a snippet of code that looks correct on the surface but will drive you crazy in production.

// BUGGY CODE: Don't do this!
class SimpleMap {
    std::string keys[10];
    std::string values[10];

    int hash(std::string k) {
        int h = 0;
        for (char c : k) h += c;
        return h % 10;
    }

public:
    void insert(std::string k, std::string v) {
        int idx = hash(k);
        keys[idx] = k;
        values[idx] = v;
    }

    std::string get(std::string k) {
        int idx = hash(k);
        return values[idx];
    }
};

// Usage
SimpleMap map;
map.insert("Apple", "Red");
map.insert("Banana", "Yellow"); 
// Wait... what if "Apple" and "Banana" hash to the same index?

The Vanishing Data Problem

In the code above, we have a classic collision. If hash("Apple") and hash("Banana") both return 5, the "Banana" entry simply overwrites "Apple". You didn't get a crash or a compiler error; you just lost your data. This is the most dangerous kind of bug because it's silent. Your tests might pass with a few items, but the moment your dataset grows, your map starts "forgetting" things randomly.

To fix this, we need a way to store multiple items at the same index. The most common way to handle this is called Separate Chaining. Instead of the bucket being a single value, the bucket becomes a list of pairs. When a collision happens, we just append the new key-value pair to that list.

Implementing Separate Chaining

Here is how I would rewrite this to be robust. I'm using std::list for the buckets because it's clear and handles dynamic growth well, though in a high-performance system, you might use a small vector to be more cache-friendly.

#include <iostream>
#include <vector>
#include <list>
#include <string>

class HashTable {
    struct Entry {
        std::string key;
        std::string value;
    };

    // A vector of lists. Each list is a "bucket".
    std::vector<std::list<Entry>> buckets;
    int capacity;

    int hash(const std::string& k) const {
        // Using a slightly better hash than just adding characters
        size_t h = std::hash<std::string>{}(k);
        return h % capacity;
    }

public:
    HashTable(int cap = 10) : capacity(cap) {
        buckets.resize(capacity);
    }

    void insert(const std::string& k, const std::string& v) {
        int idx = hash(k);
        
        // First, check if the key already exists to update it
        for (auto& entry : buckets[idx]) {
            if (entry.key == k) {
                entry.value = v;
                return;
            }
        }
        // If we get here, it's a new key. Add it to the bucket.
        buckets[idx].push_back({k, v});
    }

    std::string get(const std::string& k) {
        int idx = hash(k);
        for (const auto& entry : buckets[idx]) {
            if (entry.key == k) return entry.value;
        }
        return "NOT_FOUND";
    }
};

Choosing a Better Hash Function

You'll notice I swapped the manual character-sum loop for std::hash<std::string>{}. I strongly recommend doing this. Writing your own hash function is a fun academic exercise, but it's a nightmare in practice. A poor hash function creates "clustering," where too many keys land in the same bucket. If every single key hashes to index 5, your $O(1)$ hash table effectively becomes a $O(n)$ linked list, and your performance falls off a cliff.

The Load Factor and Resizing

There's one more thing: the capacity. If you have 10 buckets and you insert 1,000 items, your average list length is 100. That's slow. Professional implementations track the Load Factor (number of items / number of buckets). Once the load factor hits a certain threshold (usually 0.75), the table "resizes."

Resizing isn't as simple as calling vector::resize(). Because the index depends on hash(key) % capacity, changing the capacity changes the index for every single item. You have to create a brand new, larger array and re-hash every single existing element into the new buckets. It's an expensive operation, but because it happens infrequently, the "amortized" cost remains $O(1)$.

📋 Practical Task

Exercise: Building a Rare-Word Frequency Tracker

Your task is to implement a hash table that tracks how many times specific words appear in a text. Instead of mapping string to string, you will map string to int.

Requirements:

• Implement a WordCounter class with a void addWord(std::string word) method and an int getCount(std::string word) method.
• Use separate chaining (a vector of lists) to handle collisions.
• The addWord method should increment the count if the word already exists, or create a new entry with a count of 1 if it doesn't.
• Use std::hash for the hashing logic.
• Test your implementation by passing in a list of words where at least two different words hash to the same bucket (you can verify this by printing the bucket index inside the addWord method).