Skip to content

PATTERN Cited by 1 source

Constant-time state map

Intent

Replace O(n) array scans / multi-hop lookups on a hot path with O(1) access via a JavaScript Map (or nested Maps) keyed by the identifier the caller already has.

Context

Rendering a long list (10,000 diff lines, rows, items) frequently needs per-item state lookups: "does this line have a comment?" "is this row selected?" "is this item highlighted?" The naive shape is an array of objects scanned on each lookup:

const comment = comments.find(c => c.file === path && c.line === L);

At 10,000 items with ~10 per-item state queries per render, this is 100M operations per render on a 10K-row list — even with tiny per-op cost it dominates frame budget and INP (concepts/interaction-to-next-paint).

Mechanism

Build a JavaScript Map (or nested Maps, or a plain object-tree) keyed by the natural lookup key:

// commentsMap: Map<filePath, Map<lineId, Comment>>
const commentsMap = new Map();
for (const c of comments) {
  if (!commentsMap.has(c.file)) commentsMap.set(c.file, new Map());
  commentsMap.get(c.file).set(c.line, c);
}

// O(1) query per line:
const comment = commentsMap.get(path)?.get(L);

Or GitHub's plain-object form:

commentsMap['path/to/file.tsx']['L8']

Four load-bearing properties:

  • O(1) average-case lookup — hash-based, does not scan.
  • Single lookup invocation replaces multi-hop find operations.
  • Stable structure across renders — the map itself is constructed once per state update, shared across all renders it informs; doesn't trigger per-line re-renders if used via selectors.
  • Cache-friendly — the hot-path check on each render is one dereference, not a loop across heap-allocated object comparisons. (Same lesson as concepts/cache-locality at the JS-runtime substrate.)

Canonical instance

GitHub's Files-changed tab v2 — "In v1, we gradually accumulated a lot of O(n) lookups across shared data stores and component state... we redesigned our global and diff state machines to utilize O(1) constant time lookups by employing JavaScript Map. This let us build fast, consistent selectors for common operations throughout our codebase, such as line selection and comment management. These changes have enhanced code quality, improved performance, and reduced complexity by maintaining flattened, mapped data structures. Now, any given diff line simply checks a map by passing the file path and the line number to determine whether or not there are comments on that line. An access might look like: commentsMap['path/to/file.tsx']['L8']" (Source: sources/2026-04-03-github-the-uphill-climb-of-making-diff-lines-performant)

The pattern enabled the complementary patterns: a diff-line component can now cheaply check "should I render the comment- thread child?" per render (via the Map), making patterns/conditional-child-state-scoping practical.

Trade-offs

  • Build cost: constructing the map is O(n) each time the source array updates. At 10,000 items the build is milliseconds — amortized across the render cycles that consume it.
  • Memory: Maps add overhead over raw arrays; at 10,000 items this is typically sub-MB — negligible next to per-render cost.
  • Keying: natural keys must be derivable from the source data. GitHub's path + line-id works because both are already in every comment record.
  • Invalidation: when the source data changes, the map must be rebuilt — libraries like Reselect or custom memo selectors make this automatic.

Anti-patterns

  • Using .find() on a big array inside render. The classic failure mode this pattern fixes.
  • Nested .find() chains across multiple arrays. Each is an O(n); products are O(n²) or worse.
  • Maps keyed by objects (Map-key identity semantics are surprising). Use string/number keys derived from the object's identity fields.
  • Rebuilding the map per render. Build in a useMemo / state slice so renders share the same Map.
  • Not measuring. At small list sizes the .find() shape is fine. This pattern is for 1,000+ items with per-render lookups.
Last updated · 200 distilled / 1,178 read