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 { NestFactory } from '@nestjs/core';
import { DocumentBuilder, SwaggerModule } from '@nestjs/swagger';
import { ValidationPipe } from '@nestjs/common';
import { ApiProperty } from '@nestjs/swagger';

Wiring validation and Swagger docs in NestJS

validation openapi decorators
Intermediate 8 steps
rust 
use axum::{extract::{Path, State}, http::StatusCode, Json};
use dashmap::DashMap;
use serde::Serialize;
use std::sync::Arc;

Request coalescing in an Axum handler

caching concurrency request-coalescing
Advanced 8 steps
typescript 
import { Component, Input } from '@angular/core';
 
interface Order {
  id: string;

How Angular ICU plurals localize an order summary

i18n pluralization standalone-component
Intermediate 8 steps
typescript 
import { Injectable, NestInterceptor, ExecutionContext, CallHandler } from '@nestjs/common';
import { Observable, catchError, concatMap, finalize } from 'rxjs';
import { DataSource, QueryRunner } from 'typeorm';
 

Wrapping requests in a transaction with NestJS

interceptors transactions rxjs
Advanced 7 steps
typescript 
type CsvColumn<T> = {
  header: string;
  value: (row: T) => string | number | boolean | null | undefined;
};

Building a type-safe CSV writer in TypeScript

generics serialization escaping
Intermediate 7 steps
go 
package scheduler
 
import (
	"container/heap"

A priority job queue with Go's container/heap

priority-queue heap interfaces
Intermediate 9 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