typescript 36 lines · 8 steps

Building an LRU cache on a JS Map

A least-recently-used cache that exploits Map's insertion-order guarantee to evict the stalest entry in O(1).

Explained by highlit
Intermediate caching data-structures generics eviction insertion-order
1class LRUCache<K, V> {
2 private readonly capacity: number;
3 private readonly map: Map<K, V>;
4 
5 constructor(capacity: number) {
6 if (capacity <= 0) throw new Error("capacity must be positive");
7 this.capacity = capacity;
8 this.map = new Map();
9 }
10 
11 get(key: K): V | undefined {
12 if (!this.map.has(key)) return undefined;
13 const value = this.map.get(key)!;
14 this.map.delete(key);
15 this.map.set(key, value);
16 return value;
17 }
18 
19 put(key: K, value: V): void {
20 if (this.map.has(key)) {
21 this.map.delete(key);
22 } else if (this.map.size >= this.capacity) {
23 const oldest = this.map.keys().next().value as K;
24 this.map.delete(oldest);
25 }
26 this.map.set(key, value);
27 }
28 
29 has(key: K): boolean {
30 return this.map.has(key);
31 }
32 
33 get size(): number {
34 return this.map.size;
35 }
36}
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1JavaScript's Map preserves insertion order, so the first key it yields is always the oldest.
  2. 2Re-inserting a key after deleting it moves it to the most-recent position, which is how recency is tracked.
  3. 3Wrapping a single Map gives you O(1) get, put, and eviction without a separate linked list.

Related explainers

typescript 
import {
  CallHandler,
  ExecutionContext,
  Injectable,

Wrapping responses in a NestJS interceptor

interceptors rxjs response-shaping
Intermediate 7 steps
typescript 
type RetryOptions = {
  retries?: number;
  timeoutMs?: number;
  baseDelayMs?: number;

Retry with timeout and backoff in TypeScript

promises retry exponential-backoff
Intermediate 10 steps
typescript 
import { Pipe, PipeTransform, ChangeDetectorRef, NgZone, OnDestroy } from '@angular/core';
 
@Pipe({
  name: 'timeAgo',

A self-refreshing timeAgo pipe in Angular

impure-pipe change-detection timers
Advanced 10 steps
go 
package cache
 
import (
	"container/list"

Building a generic LRU cache in Go

lru-cache generics linked-list
Intermediate 8 steps
typescript 
const DIVISIONS: { amount: number; unit: Intl.RelativeTimeFormatUnit }[] = [
  { amount: 60, unit: "seconds" },
  { amount: 60, unit: "minutes" },
  { amount: 24, unit: "hours" },

Human-readable relative times with Intl

internationalization date-formatting lookup-table
Intermediate 7 steps
rust 
use std::collections::HashMap;
 
pub struct Memoizer<K, V, F> {
    cache: HashMap<K, V>,

A generic memoizer in Rust

memoization generics caching
Intermediate 6 steps

Share this explainer

Here's the card — post it anywhere.

Building an LRU cache on a JS Map — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code