Hash Map (Dictionary)

Concept

A Hash Map (called a Dictionary in Python, or a Map in Java/C++) is the standard implementation of a Hash Table that stores data in Key-Value pairs.

You provide a unique Key (the identifier you use to look it up later), and a Value (the actual data payload you want to store).

Implementation in JavaScript

JavaScript has two ways to implement a Hash Map: The legacy Object ({}) and the modern Map class. Always use the Map class in algorithmic interviews.

// Initializing
const cache = new Map();

// O(1) Insertion
cache.set("Alice", 100);
cache.set("Bob", 200);

// O(1) Lookup
console.log(cache.get("Alice")); // 100

// O(1) Check Existence
if (cache.has("Bob")) {
    console.log("Bob is in the map!");
}

// O(1) Deletion
cache.delete("Alice");

// Iteration (Maintains Insertion Order)
for (let [key, value] of cache) {
    console.log(key, value);
}

Why Object {} is dangerous in Interviews

1. Iteration Order: Map mathematically guarantees that when you iterate over it, the items will come out in the exact order they were inserted. Standard Objects do not guarantee order across different JS engines (they often sort integer keys automatically).
2. Key Types: Objects coerce all keys to Strings. Map allows numbers, booleans, and even other Objects to be used as keys.
3. Prototype Pollution: Objects inherit properties from Object.prototype. If you check if (obj["constructor"]), it will evaluate to true even if you never inserted it! Map is a clean data structure.
4. Size: Map has an instant $O(1)$ map.size property. Getting the size of an Object requires an $O(N)$ Object.keys(obj).length scan.

Classic Pattern: The Caching Wrapper

A very common use case for a Hash Map in interviews is Memoization (Caching).
If you have an incredibly slow, recursive function (like calculating Fibonacci numbers), you can wrap it with a Hash Map. Before the function does any math, it checks the Map. If the answer is already there, it returns it in $O(1)$ time, bypassing millions of recursive operations.

const memo = new Map<number, number>();

function slowFibonacci(n: number): number {
    // 1. Base Cases
    if (n <= 1) return n;
    
    // 2. Check the Cache (O(1))
    if (memo.has(n)) {
        return memo.get(n)!;
    }
    
    // 3. Do the slow calculation
    const result = slowFibonacci(n - 1) + slowFibonacci(n - 2);
    
    // 4. Save the result to the cache before returning!
    memo.set(n, result);
    return result;
}

Interview Questions

Q: A developer uses a Hash Map to store the configuration of a User object. map.set(userObject, "Admin"). Later, they reconstruct the exact same user object from a database payload: const reconstructedUser = { id: 5 }. They try to look up the role: map.get(reconstructedUser). It returns undefined. Why?
A: When you use an Object as a Key in a Map, the Map hashes the object’s physical memory address (reference), not its contents.
Even though reconstructedUser has the exact same properties as the original userObject, it was created as a brand new object, meaning it lives at a different memory address. Therefore, the Hash Map treats it as a completely different key. To fix this, the developer should use a primitive primitive value (like the user.id string/number) as the Key, not the object itself.

Q: What is a WeakMap in JavaScript?
A: A WeakMap is a specialized Hash Map where the Keys must be Objects (primitives are not allowed).
The “Weak” part refers to memory management. In a standard Map, as long as the Map exists, the garbage collector is forbidden from deleting the objects stored as keys, causing memory leaks if the objects are no longer needed elsewhere in the app.
In a WeakMap, the keys are “weakly held”. If all other references to the object are deleted in the application, the Garbage Collector will automatically aggressively delete the key-value pair from the WeakMap to free up RAM. It is highly useful for storing private data tied to DOM elements.