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 flask import Blueprint, jsonify, request, abort
 
v1 = Blueprint("users_v1", __name__)
v2 = Blueprint("users_v2", __name__)

Versioning a Flask API with Blueprints

api versioning blueprints rest
Intermediate 7 steps
python 
import time
import threading
from enum import Enum
from functools import wraps

Building a circuit breaker in Python

circuit-breaker resilience decorators
Advanced 7 steps
php 
<?php
 
namespace App\Http\Middleware;
 

Idempotent requests with Laravel middleware

idempotency middleware caching
Advanced 8 steps
python 
from django.contrib.postgres.search import SearchQuery, SearchRank, SearchVector
from django.core.cache import cache
from django.db.models import F
from django.http import JsonResponse

Ranked full-text search in Django

full-text-search debouncing caching
Advanced 9 steps
python 
import os
from datetime import timedelta
 
 

Class-based config in a Flask app factory

configuration app-factory inheritance
Intermediate 7 steps
python 
import time
 
from flask import Flask, g, request
 

Timing requests with Flask hooks

middleware request-lifecycle instrumentation
Intermediate 5 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