> ## Documentation Index
> Fetch the complete documentation index at: https://akshanshgusain.mintlify.site/llms.txt
> Use this file to discover all available pages before exploring further.

# Cache Eviction Policies – "How You Decide What to Remove When Cache Is Full"

> Eviction policies determine which cached entries to remove when the cache is full and needs space

Cache eviction is a `policy` or `algorithm` that determines which item(s) to remove from a cache when it reaches its maximum
capacity. It’s a crucial aspect of cache management to maintain efficiency and performance.

| Policy                          | Description                      | Typical Use                             |
| :------------------------------ | :------------------------------- | :-------------------------------------- |
| **LRU (Least Recently Used)**   | Removes least recently used item | General-purpose caching                 |
| **LFU (Least Frequently Used)** | Removes least accessed item      | Skewed traffic where few items dominate |
| **FIFO (First In First Out)**   | Removes oldest inserted item     | Simple caches                           |
| **Random**                      | Removes a random item            | High-throughput caches like Redis       |
| **Time-based Expiry**           | Removes items after TTL expires  | CDN, session storage                    |

## LRU Least Recently Used

LRU stands for Least Recently Used, which is a popular cache eviction policy used in computing. When a cache reaches its
size limit and needs to make space for new items, LRU removes the item that has not been accessed or used for the longest
time—i.e., the "least recently used" item is evicted.

```python LRU implementation theme={null}
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1  # Cache miss
        else:
            self.cache.move_to_end(key)  # Mark recently used
            return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            evicted_key, evicted_value = self.cache.popitem(last=False)  # Evict least recently used
            print(f"Evicted: {evicted_key}")

# Usage Example:
cache = LRUCache(2)

cache.put(1, 'A')
cache.put(2, 'B')

print(cache.get(1))  # returns 'A', cache: {2:'B', 1:'A'}

cache.put(3, 'C')  # Evicts key 2
print(cache.get(2))  # returns -1 (evicted)
print(cache.get(3))  # returns 'C'

```

## LFU Least Frequently Used

Evict the key with the lowest access frequency. Ties can be broken by recency or arbitrary order.

```python LFU theme={null}
from collections import defaultdict, OrderedDict

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 0
        self.key_to_val = {}           # key → value
        self.key_to_freq = {}          # key → freq
        self.freq_to_keys = defaultdict(OrderedDict)
        # freq → keys in order of insertion (to break ties by recency)

    def _update_freq(self, key: int):
        freq = self.key_to_freq[key]
        # remove from current freq list
        del self.freq_to_keys[freq][key]
        if not self.freq_to_keys[freq]:
            del self.freq_to_keys[freq]
            if freq == self.min_freq:
                self.min_freq += 1
        # add to next freq list
        self.key_to_freq[key] = freq + 1
        self.freq_to_keys[freq + 1][key] = True

    def get(self, key: int) -> int:
        if key not in self.key_to_val:
            return -1
        self._update_freq(key)
        return self.key_to_val[key]

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
        if key in self.key_to_val:
            # update value and frequency
            self.key_to_val[key] = value
            self._update_freq(key)
            return

        if len(self.key_to_val) >= self.capacity:
            # evict LFU key
            # min_freq holds the smallest freq currently in cache
            evict_key, _ = self.freq_to_keys[self.min_freq].popitem(last=False)
            del self.key_to_val[evict_key]
            del self.key_to_freq[evict_key]
            print(f"Evicted LFU key: {evict_key}")

        # insert new key with freq = 1
        self.key_to_val[key] = value
        self.key_to_freq[key] = 1
        self.freq_to_keys[1][key] = True
        self.min_freq = 1

# Usage Example:
cache = LFUCache(2)
cache.put(1, 'A')  # cache: {1:'A'}
cache.put(2, 'B')  # cache: {1:'A', 2:'B'}
print(cache.get(1))  # returns 'A', freq of 1→2
cache.put(3, 'C')    # evicts key 2 (freq=1), inserts 3
print(cache.get(2))  # returns -1 (evicted)
print(cache.get(3))  # returns 'C'

```

## FIFO First in last out

Evict the oldest entry—i.e., the one that was inserted earliest.

```python LFU theme={null}
from collections import deque

class FIFOCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}          # key → value
        self.queue = deque()     # track insertion order

    def get(self, key: int) -> int:
        return self.cache.get(key, -1)

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # update value but keep insertion order
            self.cache[key] = value
            return

        if len(self.cache) >= self.capacity:
            evict_key = self.queue.popleft()
            del self.cache[evict_key]
            print(f"Evicted FIFO key: {evict_key}")

        self.cache[key] = value
        self.queue.append(key)

# Usage Example:
cache = FIFOCache(2)
cache.put(1, 'A')
cache.put(2, 'B')
cache.put(3, 'C')  # evicts key 1
print(cache.get(1))  # -1
print(cache.get(2))  # 'B'
print(cache.get(3))  # 'C'

```

## Random Eviction

Evict a random entry when capacity is exceeded.

```python theme={null}
import random

class RandomCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key → value

    def get(self, key: int) -> int:
        return self.cache.get(key, -1)

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache[key] = value
            return

        if len(self.cache) >= self.capacity:
            evict_key = random.choice(list(self.cache.keys()))
            del self.cache[evict_key]
            print(f"Evicted Random key: {evict_key}")

        self.cache[key] = value

# Usage Example:
cache = RandomCache(2)
cache.put(1, 'A')
cache.put(2, 'B')
cache.put(3, 'C')  # randomly evicts either 1 or 2
print(cache.get(1), cache.get(2), cache.get(3))

```