1 min lesson

Hash trees to detect changed files

Explain what the example in "Hash trees to detect changed files" is doing and why it matters.

Hash trees to detect changed filesMerkle-style structure

A hash tree (Merkle tree) hashes each file, then hashes each directory as a hash of its children's hashes, up to a single root hash. Two trees with the same root are identical. When something changes, only the path from that file to the root changes, so you find the changed subtree in O(log n) of the directory depth instead of rescanning everything.

Directory hash is a hash of its children's hashes.ts

type FsNode =
  | { kind: 'file'; name: string; bytes: Uint8Array }
  | { kind: 'dir'; name: string; children: FsNode[] };

function merkleHash(node: FsNode): string {
  if (node.kind === 'file') return hashContent(node.bytes);
  const childHashes = node.children
    .map((c) => `${c.name}:${merkleHash(c)}`)
    .sort();                                  // stable order -> stable hash
  return hashContent(new TextEncoder().encode(childHashes.join('|')));
}

Watch out

Sort children before hashing a directory. If the hash depends on file-system enumeration order, two identical directories can produce different roots and your change detection breaks. This is the bug interviewers wait to see if you spot.

Hash trees to detect changed files

Step 1 of 2

Hash trees to detect changed filesMerkle-style structure