LRU Cache

Requirements

A cache keeps recent results close so the next request is fast. It has a fixed size, so something must be thrown out when it is full. LRU (Least Recently Used) throws out the entry that was used longest ago.

• get(key) returns the value, or a miss, and marks the entry as most recently used.
• put(key, value) inserts or updates, and marks the entry as most recently used.
• When the cache is full, put of a new key evicts the least recently used entry.
• Both operations must run in $O(1)$ time.
• Safe to call from several threads.