Implementing a HashMap from Scratch (No STL)

0) Problem Restatement

NVIDIA asked: implement a hash map without using standard library containers (in C/C++ style: no std::unordered_map, no std::vector). Support put(key, value), get(key) and remove(key) in average O(1), and explain the design decisions.

1) How a Hash Map Works (simple version)

• Keep an array of buckets.
• To store a key, compute hash(key), then index = hash % capacity, and put the entry in that bucket.
• Two keys can land in the same bucket (a collision), so each bucket must hold multiple entries. That's the design choice.
• If the table gets too full, operations slow down, so resize (usually double) and rehash everything when size / capacity > load_factor (e.g., 0.75).

2) Collision Strategies

We implement separate chaining (simplest to get right in an interview), and mention linear probing as the faster alternative.

flowchart LR
    K["key"] --> H["hash(key) % capacity"]
    H --> B0["bucket 0 → null"]
    H --> B1["bucket 1 → (k1,v1) → (k7,v7)"]
    H --> B2["bucket 2 → (k3,v3)"]

3) Code (C++, no STL)

#include <cstdint>
#include <cstring>

struct Node {
    int key; int value; Node* next;
};

class HashMap {
    Node** buckets; int capacity; int count;
    static constexpr double LOAD = 0.75;

    static uint32_t hashInt(int k) {             // integer mixer (spreads bits)
        uint32_t x = (uint32_t)k;
        x ^= x >> 16; x *= 0x7feb352d; x ^= x >> 15; x *= 0x846ca68b; x ^= x >> 16;
        return x;
    }
    int indexFor(int key, int cap) const { return hashInt(key) % cap; }

    void resize() {
        int newCap = capacity * 2;
        Node** nb = new Node*[newCap];
        std::memset(nb, 0, sizeof(Node*) * newCap);
        for (int i = 0; i < capacity; i++) {       // move every node to its new bucket
            Node* n = buckets[i];
            while (n) {
                Node* nxt = n->next;
                int j = indexFor(n->key, newCap);
                n->next = nb[j]; nb[j] = n;
                n = nxt;
            }
        }
        delete[] buckets; buckets = nb; capacity = newCap;
    }

public:
    HashMap(int cap = 16) : capacity(cap), count(0) {
        buckets = new Node*[capacity];
        std::memset(buckets, 0, sizeof(Node*) * capacity);
    }
    ~HashMap() {
        for (int i = 0; i < capacity; i++) {
            Node* n = buckets[i];
            while (n) { Node* nxt = n->next; delete n; n = nxt; }
        }
        delete[] buckets;
    }
    void put(int key, int value) {
        int i = indexFor(key, capacity);
        for (Node* n = buckets[i]; n; n = n->next)
            if (n->key == key) { n->value = value; return; }   // update existing
        buckets[i] = new Node{key, value, buckets[i]};          // insert at head
        if (++count > LOAD * capacity) resize();
    }
    bool get(int key, int& out) const {
        for (Node* n = buckets[indexFor(key, capacity)]; n; n = n->next)
            if (n->key == key) { out = n->value; return true; }
        return false;
    }
    bool remove(int key) {
        int i = indexFor(key, capacity);
        Node** link = &buckets[i];
        while (*link) {
            if ((*link)->key == key) { Node* d = *link; *link = d->next; delete d; count--; return true; }
            link = &(*link)->next;
        }
        return false;
    }
};

4) Explaining the Decisions

• Hash quality: a good mixing function spreads keys evenly. Bad hashes (e.g., identity with a power-of-two capacity) put many keys in few buckets and make operations O(n).
• Resizing doubles capacity. It's O(n) when it happens, but happens rarely, so the amortized cost per insert stays O(1).
• Memory: free all nodes in the destructor, and copying should be disabled or deep-copied (rule of three).
• Generic keys: use templates with a hash functor and an equality comparison.

5) Follow-ups

• Thread safety: one mutex (simple), or lock striping (a lock per group of buckets) so threads touching different buckets don't block each other. Resizing then needs all locks, or an incremental resize.
• Open addressing: linear probing with tombstones for deletes, and a load factor of ~0.5–0.7. Robin Hood hashing reduces long probe chains.
• Hash flooding attacks: attackers craft keys that collide. Use a randomized seeded hash (e.g., SipHash), or switch long chains to balanced trees (as Java does).

6) Wrap-Up

Use an array of bucket heads with linked-list chains, a good mixing hash, and doubling plus rehashing when the load factor passes 0.75, which gives average O(1) put/get/remove with amortized resizing. Manage memory carefully, and discuss open addressing, lock striping for concurrency, and seeded hashes against collision attacks as follow-ups.