Random Replacement
What you'll learn: How randomly evicting cache entries can be a surprisingly effective and simple eviction strategy.
The Core Idea
When your cache is full and you need to make room for new data, Random Replacement simply picks an entry at random and evicts it. No tracking of access times, no frequency counters, no complex bookkeeping—just roll the dice and remove whatever entry gets selected.
This sounds too simple to work well, but it's surprisingly effective in many real-world scenarios.
Why It Works
Think of a crowded parking lot where you need to make space. Instead of checking which car has been there longest or which owner visits least often, you just pick any random car and have it moved. While not optimal, it works reasonably well when:
- Most cached items have similar access patterns
- The cost of tracking metadata outweighs the benefit of smarter eviction
- You need absolute simplicity and speed
Implementation Benefits
Random Replacement requires almost zero overhead:
- No timestamps to maintain (unlike LRU)
- No access counters to update (unlike LFU)
- No queue reordering (unlike FIFO)
- Eviction decision is O(1) constant time
Real-World Performance
Studies show Random Replacement often performs within 5-10% of more sophisticated algorithms like LRU, especially when cache hit rates are already high or access patterns are fairly uniform. The simplicity means fewer bugs, faster operations, and less memory overhead for metadata.
When to Use It
Random Replacement shines when you value implementation simplicity over squeezing out maximum hit rate, or when access patterns don't show strong temporal or frequency locality.
Key Takeaway: Random Replacement trades slightly lower hit rates for extreme simplicity—no metadata, no tracking, just random selection when eviction is needed.