Hash maps and hash sets

The problem we are solving:

Imagine a phonebook. You have 1 million names and phone numbers. If you store them in an array and search for “Alice”, you scan from the start: Alice? No. Bob? No. Charlie? No. … — O(n) time.

But a phonebook is organized alphabetically. You jump to the “A” section, then scan just a few names. Still linear, but faster in practice.

Can we do better? Yes, if we can jump straight to the answer without scanning at all. That is what hashing does.

The idea of hashing:

A hash function is a function that takes a key (a name, a number, a word) and returns an index — a number between 0 and n-1, where n is the size of the array. The idea is clever: instead of scanning an array, use the hash function to calculate where the data should be, then look there instantly.

function hash(key, arraySize) {
  // Turn the key into a number between 0 and arraySize - 1
  return someFormula(key) % arraySize;
}

const index = hash("Alice", 1000);  // Returns, say, 342
// Look at position 342 — Alice's phone number is there (ideally)

In a good hash function, different keys map to different indices. “Alice” always maps to 342. “Bob” might map to 157. “Charlie” to 899. The array has a bucket at each index, and the key–value pair sits in that bucket.

Why O(1)? Calculate the index (one formula) and look at that index (one operation). Done. No loop.

Hash set vs. hash map:

A hash set (or unordered set) stores only values — it answers “is X in the set?”. It uses a hash function to map each value to an array index, then stores the value (or a marker) at that index.

      1
      const mySet = new Set();
    

      2
      mySet.add(10);
    

      3
      mySet.add(20);
    

      4
      mySet.add(30);
    

      5
       
    

      6
      console.log(mySet.has(20));  // true, found instantly via hash
    

      7
      console.log(mySet.has(99));  // false, looked and not there
    

A hash map (or dictionary) stores key–value pairs. For each key, it calculates an index using a hash function, then stores both the key and the value at that index. Lookups by key are O(1) on average.

      1
      const myMap = new Map();
    

      2
      myMap.set("Alice", "555-1234");
    

      3
      myMap.set("Bob", "555-5678");
    

      4
       
    

      5
      console.log(myMap.get("Alice"));  // "555-1234", found in O(1)
    

      6
      console.log(myMap.get("Charlie"));  // undefined, not there, still O(1)
    

Core operations on a hash set or map:

1. Add/set by key — Hash the key, jump to the index, place the value. O(1) average.
2. Lookup/contains — Hash the key, jump to the index, check if it is there. O(1) average.
3. Delete by key — Hash the key, jump to the index, remove it. O(1) average.

The word “average” is important: in a badly designed hash function or under heavy collisions (see the edge case), performance can degrade. But with a good hash function and reasonable load factor (number of items / array size), O(1) average is reliable.

The tradeoff:

• Memory cost: A hash set or map uses extra memory—an array to hold the buckets, usually with spare capacity to keep collisions rare. You spend memory to save time.
• No order: Iteration over a hash set or map does not follow any predictable order (except that JavaScript Maps iterate in insertion order, a concession to developer expectations).
• Keys must be hashable: In some languages, only certain types can be keys (immutable types in Python, for example). JavaScript is more forgiving: you can hash any value.