HashSet

How It Works

A HashSet stores a collection of unique values and answers one question extremely fast: "have I seen this before?" It uses the exact same hashing mechanism as a HashMap (each value is run through a hash function to determine its bucket), except there's no associated value to store, only the presence of the key itself. That's why you can think of a HashSet as a HashMap where you only ever care about the keys.

Because membership checks (has) are average O(1), a HashSet is the go-to structure for deduplication, tracking visited nodes in a graph/grid traversal, and computing set operations (union, intersection, difference) efficiently.

In JavaScript, the built-in Set is the idiomatic HashSet. Like Map, it can hold values of any type, preserves insertion order, and is directly iterable. Values are compared using the same algorithm as ===, with one exception: NaN is considered equal to itself in a Set (unlike normal NaN === NaN, which is false).

Core operations and their complexity:

• add(value) / has(value) / delete(value): average O(1).
• Iteration: O(n).
• Deduplicating an array: O(n) via [...new Set(arr)].

// Set is the idiomatic hashset in JS
const visited = new Set();

visited.add("A");
visited.add("B");
visited.add("A"); // no-op, already present

console.log(visited.has("B")); // true
console.log(visited.size); // 2

// Deduplicate an array in O(n)
const nums = [1, 2, 2, 3, 3, 3];
const unique = [...new Set(nums)]; // [1, 2, 3]

// Classic interview pattern: detect a duplicate in O(n) time / O(n) space
function hasDuplicate(nums) {
  const seen = new Set();
  for (const n of nums) {
    if (seen.has(n)) return true;
    seen.add(n);
  }
  return false;
}

// Common pattern: tracking visited nodes during BFS/DFS
function countIslands(grid) {
  const visited = new Set();
  let islands = 0;

  function key(r, c) {
    return `${r},${c}`;
  }

  function dfs(r, c) {
    const k = key(r, c);
    if (
      r < 0 || c < 0 || r >= grid.length || c >= grid[0].length ||
      grid[r][c] === 0 || visited.has(k)
    ) {
      return;
    }
    visited.add(k);
    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }

  for (let r = 0; r < grid.length; r++) {
    for (let c = 0; c < grid[0].length; c++) {
      if (grid[r][c] === 1 && !visited.has(key(r, c))) {
        islands++;
        dfs(r, c);
      }
    }
  }
  return islands;
}

Common Mistakes

• Reaching for an array and .includes() instead of a Set: this silently turns an O(n) dedup/visited check into O(n²) because array .includes is itself O(n).
• Forgetting to serialize composite keys: when tracking visited (row, col) pairs, you must combine them into a single primitive (e.g. a string key or row * numCols + col), since objects/arrays as Set values compare by reference, not value.
• Confusing Set with Map: reaching for a Set when you actually need to store an associated value (counts, indices) per key; that's a Map, not a Set.
• Assuming insertion order doesn't matter and being surprised it's preserved: Set iterates in insertion order, which is sometimes relied upon and sometimes a subtle gotcha.
• Not clearing/scoping the set per traversal: reusing one global visited set across multiple independent BFS/DFS calls when each call needs its own.

Pattern Summary

Reach for a HashSet whenever the problem is really about membership or uniqueness: deduplication, "has this been seen," or visited-tracking in graph/grid traversal. The edge it gives you in interviews is collapsing an O(n) or O(n²) linear-scan check into an average O(1) lookup, which is often the single change that gets a brute-force solution to the optimal one.