LRU Cache in Pure PHP Using Ordered Arrays

A least-recently-used cache evicts the entry that has gone untouched the longest when it runs out of room. The textbook implementation pairs a hash map with a doubly linked list, but PHP arrays already maintain insertion order, so you can get the same behavior with far less code. The trick is to treat the front of the array as oldest and the back as newest.

On every get you remove the key and reinsert it, which moves it to the tail and marks it most recently used. On put, if you exceed capacity you array_shift the front, which is by construction the least recently used entry. This keeps both reads and writes constant time amortized and needs nothing beyond core PHP.

final class LruCache {
    private array $map = [];

    public function __construct(private int $capacity) {
        if ($capacity < 1) {
            throw new InvalidArgumentException('capacity must be >= 1');
        }
    }

    public function get(string $key): mixed {
        if (!array_key_exists($key, $this->map)) {
            return null;
        }
        $value = $this->map[$key];
        unset($this->map[$key]);
        $this->map[$key] = $value; // re-append as most recent
        return $value;
    }

    public function put(string $key, mixed $value): void {
        unset($this->map[$key]);
        $this->map[$key] = $value;
        if (count($this->map) > $this->capacity) {
            array_shift($this->map); // drop least recent
        }
    }
}

$cache = new LruCache(2);
$cache->put('a', 1);
$cache->put('b', 2);
$cache->get('a');        // touch a, now b is oldest
$cache->put('c', 3);     // evicts b
echo $cache->get('a') . "\n"; // 1
var_dump($cache->get('b'));   // NULL
echo $cache->get('c') . "\n"; // 3