python 33 lines · 6 steps

Building an LRU cache with OrderedDict

An OrderedDict tracks recency so the least recently used entry is evicted first when capacity is exceeded.

Explained by highlit
Intermediate caching eviction data-structures ordered-dict dunder-methods
1from collections import OrderedDict
2from typing import Any, Hashable, Optional
3 
4 
5class LRUCache:
6 def __init__(self, capacity: int):
7 if capacity <= 0:
8 raise ValueError("capacity must be positive")
9 self.capacity = capacity
10 self._store: OrderedDict[Hashable, Any] = OrderedDict()
11 
12 def get(self, key: Hashable, default: Any = None) -> Optional[Any]:
13 if key not in self._store:
14 return default
15 self._store.move_to_end(key)
16 return self._store[key]
17 
18 def put(self, key: Hashable, value: Any) -> None:
19 if key in self._store:
20 self._store.move_to_end(key)
21 self._store[key] = value
22 if len(self._store) > self.capacity:
23 self._store.popitem(last=False)
24 
25 def __contains__(self, key: Hashable) -> bool:
26 return key in self._store
27 
28 def __len__(self) -> int:
29 return len(self._store)
30 
31 def __repr__(self) -> str:
32 items = ", ".join(f"{k!r}: {v!r}" for k, v in self._store.items())
33 return f"LRUCache({self.capacity}, {{{items}}})"
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1An OrderedDict gives you O(1) reordering, which is exactly what recency-based eviction needs.
  2. 2Both reads and writes must refresh an entry's position for recency tracking to stay accurate.
  3. 3Implementing dunder methods lets your class behave like a native container with `in`, `len`, and readable output.

Related explainers

python 
from fastapi import FastAPI, WebSocket, WebSocketDisconnect
 
app = FastAPI()
 

Building a WebSocket chat with FastAPI

websockets broadcast connection-management
Intermediate 9 steps
python 
import time
import uuid
 
from django.utils.deprecation import MiddlewareMixin

Attaching per-request context in Django

middleware request lifecycle multi-tenancy
Intermediate 7 steps
javascript 
import { useState, useEffect, useCallback, useRef } from 'react';
 
const cache = new Map();
const inflight = new Map();

Building a stale-while-revalidate hook in React

caching request-deduplication custom-hooks
Advanced 10 steps
python 
import random
from typing import Iterator, List
 
 

How reservoir sampling picks k items

reservoir-sampling streaming randomness
Intermediate 5 steps
php 
<?php
 
namespace App\Services;
 

Building a cached daily leaderboard in Laravel

caching aggregation eager-loading
Intermediate 9 steps
python 
import secrets
 
from django.contrib.auth import authenticate, login
from django.core.cache import cache

Two-factor login with OTP in Django

two-factor-auth one-time-passwords caching
Intermediate 9 steps

Share this explainer

Here's the card — post it anywhere.

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