Cache System (LRU)

O(1) Get Aur Put Ka Design

💡 LRU cache EK CHHOTI MEZ hai jispar sirf 10 files aa sakti hain. Nayi file rakhni ho to wo file hatao jise SABSE PEHLE dekha tha. Trick ye hai ki "sabse purani" file DHOONDHNI na pade.

LRU cache LLD aur DSA dono ka favourite hai. Requirement hai get() aur put() DONO O(1) mein. Iska ek hi jawab hai: HashMap (key → node) + DOUBLY LINKED LIST (recency order). HashMap se O(1) lookup, linked list se O(1) mein node ko head par move karna.

Sirf LRU par mat ruko — EvictionPolicy ko interface banao taaki LRU, LFU, FIFO swap ho sakein. Aur production concerns bolo: TTL support, thread safety (ConcurrentHashMap + lock, ya segment-wise locking), aur cache stats (hit ratio).

class LRUCache<K, V> {
  private final Map<K, Node<K, V>> map = new HashMap<>();
  private final Node<K, V> head, tail;   // dummy sentinels
  private final int capacity;

  V get(K key) {
    Node<K, V> n = map.get(key);
    if (n == null) return null;
    moveToHead(n);                // O(1) — recency update
    return n.value;
  }

  void put(K key, V value) {
    // ... insert at head
    if (map.size() > capacity) {
      Node<K, V> lru = tail.prev;  // O(1) — sabse purana
      remove(lru); map.remove(lru.key);
    }
  }
}

⚡

LRU cache EK CHHOTI MEZ hai jispar sirf 10 files aa sakti hain. Nayi file rakhni ho to wo file hatao jise SABSE PEHLE dekha tha. Trick ye hai ki "sabse purani" file DHOONDHNI na pade.

1 / 2

⚡ Quick Recap

HashMap + Doubly Linked List = get aur put dono O(1)
EvictionPolicy interface banao — LRU/LFU/FIFO swappable
TTL, thread safety aur hit-ratio stats production ke liye zaroori

Is page mein (2 subtopics)

LRU (Least Recently Used) sabse purana ACCESS hataata hai — temporal locality wale workloads ke liye best aur sabse common. FIFO sabse purana INSERT hataata hai — simple par aksar bura, kyunki popular item bhi nikal jaata hai.

LFU (Least Frequently Used) sabse kam BAAR use hua item hataata hai. Ye stable popularity wale data ke liye achha hai, par naya item turant evict ho jaata hai (cache pollution) — isliye aging/decay lagana padta hai.

💡Tip: Interview mein LRU implement karo par LFU ka trade-off zaroor bolo — "LFU better hit ratio de sakta hai par naye items ko punish karta hai." Ye comparison hi seniority dikhata hai.

Simple approach: poore cache par ek lock. Correct hai par high concurrency mein bottleneck. Behtar: SEGMENTED locking — cache ko N segments mein baanto, har segment ka apna lock (ConcurrentHashMap yahi karta hai).

TTL ke liye har entry mein expiry timestamp rakho. Expired entry ko LAZY hatao (get par check karo) plus periodic cleanup thread. Sirf lazy rakhoge to kabhi access na hone wali expired entries memory khaati rahengi.

class CacheEntry<V> {
  V value; long expiryAt;
  boolean isExpired() { return System.currentTimeMillis() > expiryAt; }
}

V get(K key) {
  var e = map.get(key);
  if (e == null) return null;
  if (e.isExpired()) { remove(key); return null; }   // lazy eviction
  moveToHead(e); return e.value;
}

← Previous📝 Logging Framework Next →🚦 Rate Limiter

Code10x

Cache System (LRU)

LRU vs LFU vs FIFO

Thread Safety Aur TTL