Hash Maps, Trees and Graphs

Mental model: A hash map turns a key into an address so lookup does not depend on size. A tree is a graph that agreed not to have cycles. A graph is just a map from each node to its neighbours.

Level: advanced · about 22 minutes

These three structures answer the same question at different scales: given this thing, what is connected to it? A hash map connects a key to one value. A tree connects a node to its children. A graph drops the last restriction and lets anything point at anything, including back at itself. Once you can traverse one you can traverse all three, because a tree traversal is a graph traversal that does not need to remember where it has been.

Object or Map

Both are hash tables. The difference is that a plain object was designed to model a record with named fields and inherits from Object.prototype, while a Map was designed to be a dictionary and inherits nothing that matters.

const words = ['tea', '__proto__', 'tea', 'constructor', 'toString'];

const asObject = {};
for (const w of words) asObject[w] = (asObject[w] ?? 0) + 1;
console.log(JSON.stringify(asObject));
// -> {"tea":2,"constructor":"function Object() { [native code] }1","toString":"function toString() { [native code] }1"}
console.log('is __proto__ an own key?', Object.hasOwn(asObject, '__proto__'));
// -> false   the assignment went to the prototype setter and was silently dropped

const asMap = new Map();
for (const w of words) asMap.set(w, (asMap.get(w) ?? 0) + 1);
console.log([...asMap]);
// -> [ [ 'tea', 2 ], [ '__proto__', 1 ], [ 'constructor', 1 ], [ 'toString', 1 ] ]

Counting words. The object version is correct until the data contains a word you did not think about.

What a hash table actually does

A hash function turns a key of any length into a fixed-size integer, and that integer modulo the number of buckets is an address. Storing and finding a key both cost one hash plus one array index, and neither depends on how many entries exist, which is where O(1) comes from. Two different keys can hash to the same bucket, which is a collision, and the usual fix is to keep a small list per bucket and scan it. When the average bucket gets too long (the load factor passes some threshold, often around 0.75) the table allocates more buckets and rehashes everything. That resize is O(n), it happens rarely, and it amortises away exactly like array growth.

key ---> hash(key) ---> index = hash % 4 ---> bucket

  bucket 0: [ 'tea', 'coffee', 'juice' ]      <- three keys collided here
  bucket 1: [ 'cocoa' ]
  bucket 2: [ 'sugar' ]
  bucket 3: [ 'milk', 'water' ]

lookup('water') = hash('water') % 4 = 3, then scan a 2-item list.
worst case: every key in one bucket, and lookup degrades to O(n).

function hashIndex(key, bucketCount) {
  const str = String(key);
  let hash = 0;
  for (let i = 0; i < str.length; i += 1) {
    hash = (hash * 31 + str.charCodeAt(i)) | 0;   // | 0 keeps it a 32-bit int
  }
  return Math.abs(hash) % bucketCount;
}

const BUCKETS = 4;
const buckets = Array.from({ length: BUCKETS }, () => []);
for (const key of ['tea', 'coffee', 'milk', 'sugar', 'water', 'juice', 'cocoa']) {
  buckets[hashIndex(key, BUCKETS)].push(key);
}

buckets.forEach((bucket, i) => console.log('bucket', i, bucket));
// -> bucket 0 [ 'tea', 'coffee', 'juice' ]
// -> bucket 1 [ 'cocoa' ]
// -> bucket 2 [ 'sugar' ]
// -> bucket 3 [ 'milk', 'water' ]

console.log('longest chain:', Math.max(...buckets.map((b) => b.length)));  // -> 3
console.log('with 16 buckets, longest chain:', (() => {
  const wide = Array.from({ length: 16 }, () => []);
  for (const k of ['tea', 'coffee', 'milk', 'sugar', 'water', 'juice', 'cocoa']) wide[hashIndex(k, 16)].push(k);
  return Math.max(...wide.map((b) => b.length));
})());

Four buckets, seven keys, real collisions. This is the whole idea in twenty lines.

Two honest notes on the real thing. First, V8 does not implement Map with buckets of arrays like this: it uses an ordered hash table that keeps insertion order and makes deletion cheap, and its keys are compared with SameValueZero, which is why NaN works as a key even though NaN !== NaN. Second, a plain object with a fixed, small set of known keys is often faster than a Map, because the engine gives it a hidden class and can compile property access down to a fixed offset. So the guidance is about intent, not speed: fields you wrote yourself, use an object. Keys that arrive at runtime, or keys that are not strings, or a set that is added to and deleted from constantly, use a Map.

Trees

A tree is nodes with children and exactly one route from the root to any node. The DOM is a tree, a file system is a tree, a JSON document is a tree, and a binary search tree is a tree with an ordering rule: everything smaller goes left, everything larger goes right. That rule makes lookup a series of halvings, which is O(log n), as long as the tree is balanced.

insert 8, 3, 10, 1, 6, 14, 4, 7, 13

              8
            /   \
          3      10
         / \       \
        1   6       14
           / \      /
          4   7   13

left subtree < node < right subtree, at every level.
finding 7: 7 < 8 go left, 7 > 3 go right, 7 > 6 go right. Three comparisons, nine nodes.

const node = (value) => ({ value, left: null, right: null });

function insert(root, value) {
  if (!root) return node(value);
  if (value < root.value) root.left = insert(root.left, value);
  else if (value > root.value) root.right = insert(root.right, value);
  return root;                                  // duplicates ignored
}

let root = null;
for (const v of [8, 3, 10, 1, 6, 14, 4, 7, 13]) root = insert(root, v);

const inorder = (n, out = []) => {
  if (!n) return out;
  inorder(n.left, out);
  out.push(n.value);        // visit between the two sides
  inorder(n.right, out);
  return out;
};
const preorder = (n, out = []) => {
  if (!n) return out;
  out.push(n.value);        // visit first
  preorder(n.left, out);
  preorder(n.right, out);
  return out;
};
const postorder = (n, out = []) => {
  if (!n) return out;
  postorder(n.left, out);
  postorder(n.right, out);
  out.push(n.value);        // visit last
  return out;
};

console.log('inorder  ', inorder(root).join(' '));    // -> 1 3 4 6 7 8 10 13 14
console.log('preorder ', preorder(root).join(' '));   // -> 8 3 1 6 4 7 10 14 13
console.log('postorder', postorder(root).join(' '));  // -> 1 4 7 6 3 13 14 10 8

Insert, then walk the same tree three ways. Only the position of the visit line changes.

Inorder on a binary search tree comes out sorted, which is the fastest way to check you built it correctly. Preorder visits a node before its children, which is what you want when copying a tree or serialising it. Postorder visits children first, which is what you want when deleting, or when a node needs a value computed from its subtrees (folder sizes, for example).

//        8
//      /   \
//     3     10
//    / \      \
//   1   6      14
// depth-first preorder vs breadth-first, same tree
// A: 8 3 1 6 10 14
// B: 8 3 10 1 6 14
// Which is which?

Depth-first dives to the bottom of one branch before backing out, so it prints 8, then all of the left subtree (3, 1, 6), then the right (10, 14). Breadth-first drains one level at a time, so it prints 8, then both children (3, 10), then all four grandchildren. The only structural difference between the two algorithms is that depth-first takes the most recently discovered node next (a stack) and breadth-first takes the oldest (a queue).

Recursion is the clearest way to write depth-first, and it borrows the call stack to remember where to go back to. That stack is finite: somewhere around ten thousand frames in a browser, and you get a RangeError: Maximum call stack size exceeded. Depth like that does not happen in a balanced tree of a million nodes (its depth is 20), but it happens easily in a degenerate one, in a linked list treated as a tree, or in a graph walk. The fix is to hold the pending nodes in your own array and loop.

const tree = {
  value: 8,
  left: { value: 3, left: { value: 1, left: null, right: null }, right: { value: 6, left: null, right: null } },
  right: { value: 10, left: null, right: { value: 14, left: null, right: null } },
};

function depthFirst(root) {
  const out = [];
  const stack = [root];                 // most recent out first
  while (stack.length) {
    const n = stack.pop();
    if (!n) continue;
    out.push(n.value);
    stack.push(n.right);                // pushed first, so popped last
    stack.push(n.left);
  }
  return out;
}

function breadthFirst(root) {
  const out = [];
  const queue = [root];
  let head = 0;                         // head index, never shift (see 16.2)
  while (head < queue.length) {
    const n = queue[head++];
    if (!n) continue;
    out.push(n.value);
    queue.push(n.left, n.right);
  }
  return out;
}

console.log('depth-first  ', depthFirst(tree).join(' '));    // -> 8 3 1 6 10 14
console.log('breadth-first', breadthFirst(tree).join(' '));  // -> 8 3 10 1 6 14

// a degenerate tree: every node has only a right child
let deep = { value: 0, left: null, right: null };
let tail = deep;
for (let i = 1; i < 50000; i += 1) {
  tail.right = { value: i, left: null, right: null };
  tail = tail.right;
}
console.log('iterative handles depth 50000:', depthFirst(deep).length);   // -> 50000
// the recursive version would throw RangeError long before this

The same two traversals with no recursion. One data structure is the only difference.

That last block is also the honest case against hand-rolled binary search trees in JavaScript. Insert sorted data into the simple BST above and every node hangs off the previous one: depth n, lookups O(n), and traversal that overflows the stack. Production trees keep themselves balanced (red-black, AVL) and that machinery is a lot of code to maintain. Since Map already gives you O(1) average lookup and insertion-ordered iteration, the honest reason to build a BST in JavaScript is a range query (all keys between two bounds, in order) or an interview.

Graphs

A graph is nodes plus edges, with no restriction: cycles are allowed, and a node can have any number of neighbours. Almost every real model is a graph. Followers, module imports, flight routes, task dependencies. Two representations cover practically everything.

const routes = {
  london: ['paris', 'dublin'],
  paris: ['london', 'milan', 'berlin'],
  dublin: ['london'],
  milan: ['paris', 'rome'],
  berlin: ['paris', 'warsaw'],
  rome: ['milan'],
  warsaw: ['berlin'],
  reykjavik: [],
};

function shortestPath(graph, start, goal) {
  if (!graph[start] || !graph[goal]) return null;
  if (start === goal) return [start];

  const cameFrom = new Map([[start, null]]);   // doubles as the visited set
  const queue = [start];
  let head = 0;

  while (head < queue.length) {
    const current = queue[head++];
    for (const next of graph[current] ?? []) {
      if (cameFrom.has(next)) continue;        // already discovered, and by a shorter route
      cameFrom.set(next, current);
      if (next === goal) {
        const path = [goal];
        let step = current;
        while (step !== null) {
          path.push(step);
          step = cameFrom.get(step);
        }
        return path.reverse();
      }
      queue.push(next);
    }
  }
  return null;                                  // goal is unreachable
}

console.log(shortestPath(routes, 'london', 'rome'));       // -> [ 'london', 'paris', 'milan', 'rome' ]
console.log(shortestPath(routes, 'dublin', 'warsaw'));     // -> [ 'dublin', 'london', 'paris', 'berlin', 'warsaw' ]
console.log(shortestPath(routes, 'london', 'reykjavik'));  // -> null
console.log(shortestPath(routes, 'london', 'atlantis'));   // -> null
console.log(shortestPath(routes, 'rome', 'rome'));         // -> [ 'rome' ]

Breadth-first search finds the shortest unweighted path, and the trick is remembering who discovered whom.

Two details carry that function. Marking a node as discovered when you enqueue it, not when you dequeue it, is what stops a cycle from queueing the same node repeatedly. And BFS is only a shortest path algorithm when every edge costs the same, because it assumes the first time you reach a node is via the fewest hops. Add weights (miles, latency, price) and the first arrival is no longer the cheapest, so you need Dijkstra: same traversal, but always expand the cheapest known node next, which needs a priority queue rather than a plain queue. Depth-first search finds a path and makes no claim about its length, which is fine for reachability, cycle detection or topological order, and wrong for routing.

Try it yourself

Four traversals, one tree

const node = (value, left = null, right = null) => ({ value, left, right });

const tree = node(1,
  node(2, node(4), node(5)),
  node(3, node(6), node(7)));

const preorder = (n, out = []) => n ? (out.push(n.value), preorder(n.left, out), preorder(n.right, out), out) : out;
const inorder = (n, out = []) => n ? (inorder(n.left, out), out.push(n.value), inorder(n.right, out), out) : out;

function depthFirst(root) {
  const out = [];
  const stack = [root];
  while (stack.length) {
    const n = stack.pop();
    if (!n) continue;
    out.push(n.value);
    stack.push(n.right);      // swap these two lines
    stack.push(n.left);
  }
  return out;
}

function byLevel(root) {
  const levels = [];
  let current = [root];
  while (current.length) {
    levels.push(current.map((n) => n.value));
    current = current.flatMap((n) => [n.left, n.right]).filter(Boolean);
  }
  return levels;
}

console.log('preorder   ', preorder(tree).join(' '));
console.log('inorder    ', inorder(tree).join(' '));
console.log('iterative  ', depthFirst(tree).join(' '));
console.log('by level   ', JSON.stringify(byLevel(tree)));

Swap the two pushes in depthFirst and watch the order mirror. Then insert 100000 sorted values with the recursive insert and find where it throws.

Distances from one node

const graph = {
  a: ['b', 'c'],
  b: ['a', 'd'],
  c: ['a', 'd'],
  d: ['b', 'c', 'e'],
  e: ['d'],
  f: [],                 // an island
};

function distancesFrom(graph, start) {
  const dist = new Map([[start, 0]]);
  const queue = [start];
  let head = 0;
  while (head < queue.length) {
    const current = queue[head++];
    for (const next of graph[current] ?? []) {
      if (dist.has(next)) continue;
      dist.set(next, dist.get(current) + 1);
      queue.push(next);
    }
  }
  return dist;
}

console.log([...distancesFrom(graph, 'a')]);
// -> [ [ 'a', 0 ], [ 'b', 1 ], [ 'c', 1 ], [ 'd', 2 ], [ 'e', 3 ] ]
console.log('f reachable from a?', distancesFrom(graph, 'a').has('f'));

Add an edge from a to e and watch e drop from distance 4 to 1. Then grow the graph to a 100 node chain and check the distance to the last node.

Exercises

Build a hash table with buckets

Write class HashTable taking a bucket count (default 8) with set(key, value), get(key), has(key), delete(key) returning a boolean, and a size getter. Keys are strings. Handle collisions by keeping a list per bucket, so new HashTable(1) (every key in one bucket) must still behave correctly. Keys such as '__proto__' and 'constructor' must work like any other string.

Shortest path with breadth-first search

A graph is a plain object from node name to an array of neighbour names. Write shortestPath(graph, start, goal) returning the array of nodes from start to goal inclusive, using the fewest hops, or null when there is no route. shortestPath(g, 'a', 'a') is ['a']. An unknown start or goal is null. Cycles must not hang it.

Check yourself

Why is Map the right choice for counting words from user-supplied text?

a plain object inherits keys such as constructor, so a missing count is not undefined — counts['constructor'] on a plain object finds Object.prototype.constructor, a function, so ?? 0 never fires and the count becomes a string. counts['__proto__'] = 1 hits a setter and is dropped entirely. Map has no prototype keys and preserves insertion order. Object.create(null) is the other valid fix, and a plain object can be faster for a small fixed set of known keys.

A hash map lookup is O(1) on average. What makes it O(n)?

every key hashing into the same bucket, so the lookup becomes a scan of one long chain — The constant comes from a good hash spreading keys across buckets so each chain stays short. If all keys collide, the bucket is a list of n entries and finding one means scanning it. This is not only theoretical: hash-collision denial of service attacks work by sending keys crafted to collide, which is why some runtimes seed their hash function per process.

You must find the fewest hops between two nodes. Which traversal, and why?

breadth-first, because the first time it reaches a node is by the fewest edges — BFS expands nodes in order of distance from the start, so the first arrival at a node is via the fewest edges. DFS dives down one branch and may reach the goal by a long route first. Note the qualifier: fewest hops. With weighted edges, first arrival is no longer cheapest and you need Dijkstra, which is BFS with a priority queue instead of a queue.

What does this print?

3 'a' 'c' — Object keys in a Map are compared by identity, so the two { id: 1 } literals are different keys and the size is 3. get(key) finds the original entry, 'a'. NaN works as a key because Map uses SameValueZero, which treats NaN as equal to itself even though NaN !== NaN. That is one thing a Map does that no plain object can, since object keys would both stringify.

Common mistakes

• Using a plain object as a lookup table for external data, and meeting __proto__ or constructor as a key.
• Reading obj[key] to test presence instead of Object.hasOwn(obj, key).
• Building buckets with new Array(n).fill([]), which puts the same array in every slot.
• Recomputing size by summing bucket lengths, turning an O(1) read into O(buckets).
• Recursing depth-first over user data of unknown depth, then meeting a RangeError in production.
• Marking graph nodes as visited on dequeue rather than enqueue, so a cycle enqueues the same node many times.
• Using BFS on a weighted graph and calling the result a shortest path.
• Hand-rolling a binary search tree, feeding it sorted data, and getting a linked list with extra steps.

Takeaways

• Objects and Maps are both hash tables. Objects model records and inherit keys, Maps model dictionaries and do not.
• A hash maps a key to a bucket index, so lookup cost does not depend on the number of entries.
• Collisions are normal, chains keep them correct, and resizing keeps them short. O(1) is an average.
• Inorder on a binary search tree is sorted. Preorder copies, postorder deletes and aggregates.
• Depth-first takes the newest pending node (a stack), breadth-first takes the oldest (a queue). That is the only difference.
• Recursion borrows the call stack, which runs out around ten thousand frames. Your own array does not.
• Adjacency lists suit sparse graphs, which is nearly all real graphs.
• BFS gives shortest paths only when every edge costs the same. Weights need Dijkstra and a priority queue.