ruby 41 lines · 7 steps

How an LRU cache works in Ruby

A least-recently-used cache built on Ruby's insertion-ordered Hash, evicting the oldest key once capacity is exceeded.

Explained by highlit

Intermediate caching eviction hash-ordering data-structures

1class LRUCache
def initialize(capacity)
  raise ArgumentError, "capacity must be positive" unless capacity.positive?
4 
  @capacity = capacity
  @store = {}
end
8 
def get(key)
  return nil unless @store.key?(key)
11 
  value = @store.delete(key)
  @store[key] = value
  value
end
16 
def put(key, value)
  @store.delete(key)
  @store[key] = value
  @store.delete(@store.first.first) if @store.size > @capacity
  value
end
23 
def fetch(key)
  return get(key) if @store.key?(key)
26 
  put(key, yield(key))
end
29 
def delete(key)
  @store.delete(key)
end
33 
def keys
  @store.keys
end
37 
def size
  @store.size
end
41end

01 / 01

STEP 01

Walkthrough

Space play ←→ step click any line

Three takeaways

1Ruby Hashes preserve insertion order, so re-inserting a key moves it to the newest position for free.
2Deleting then re-adding a key on every access is the trick that keeps recency ordering accurate.
3Bounding a cache means evicting the oldest entry the moment size crosses capacity, not before.

Related explainers

ruby

class QueryParser
  def self.parse(query_string)
    new(query_string).parse
  end

Parsing nested query strings in Ruby

parsing recursion tokenization

Intermediate 9 steps

ruby

class Article < ApplicationRecord
  belongs_to :author, class_name: "User"
  has_many :taggings, dependent: :destroy
  has_many :tags, through: :taggings

How scopes compose in Rails

scopes activerecord query-composition

Intermediate 8 steps

python

import json
import hashlib
from datetime import timedelta

Idempotent payment endpoints in FastAPI

idempotency redis distributed-locking

Advanced 9 steps

ruby

class Order
  class InvalidTransition < StandardError; end
 
  TRANSITIONS = {

A state machine for order transitions in Ruby

state-machine data-driven error-handling

Intermediate 8 steps

ruby

class CreateOrderItems < ActiveRecord::Migration[7.1]
  def change
    create_table :order_items do |t|
      t.references :order, null: false, foreign_key: { on_delete: :cascade }