LRU and LFU Java code *

LRU Cache (Least Recently Used) Concept of LRU Cache: In an LRU cache, when the cache reaches its limit, the least recently used item is removed to make space for new data. It ensures that the most recently accessed data remains in the cache. Data Structures Used: HashMap: To store the key-value pairs. Doubly Linked List: To keep track of the order of access, where the most recently used element is at the front, and the least recently used one is at the back. Java Code for LRU Cache: import java.util.; class LRUCache { private final int capacity; private final Map cache; private final DoublyLinkedList order; // Node for the doubly linked list class Node { int key, value; Node prev, next; Node(int key, int value) { this.key = key; this.value = value; } } // Doubly Linked List for keeping track of recent usage class DoublyLinkedList { Node head, tail; DoublyLinkedList() { head = new Node(-1, -1); tail = new Node(-1, -1); head.next = tail; tail.prev = head; } void addFirst(Node node) { node.next = head.next; node.prev = head; head.next.prev = node; head.next = node; } void remove(Node node) { node.prev.next = node.next; node.next.prev = node.prev; } } public LRUCache(int capacity) { this.capacity = capacity; this.cache = new HashMap(); this.order = new DoublyLinkedList(); } public int get(int key) { if (!cache.containsKey(key)) return -1; Node node = cache.get(key); order.remove(node); order.addFirst(node); return node.value; } public void put(int key, int value) { if (cache.containsKey(key)) { Node node = cache.get(key); order.remove(node); } else if (cache.size() == capacity) { Node lruNode = order.tail.prev; cache.remove(lruNode.key); order.remove(lruNode); } Node newNode = new Node(key, value); cache.put(key, newNode); order.addFirst(newNode); } } Explanation: Doubly Linked List: The doubly linked list allows quick removal and insertion of nodes, ensuring that the most recently used node is at the front and the least recently used node is at the back. HashMap: Stores the key to Node mapping to allow fast lookups. get(): If the key exists, it is moved to the front of the list (marking it as most recently used). put(): If the key is already in the cache, it updates the value and moves the key to the front. If the cache is full, it evicts the least recently used item. LFU Cache (Least Frequently Used) Concept of LFU Cache: In an LFU cache, when the cache reaches its limit, the least frequently used item is removed. The key idea is to track how often each item is accessed. Data Structures Used: HashMap: To store the key-value pairs. HashMap: To track the frequency of access. Doubly Linked List: To store keys with the same frequency and manage eviction based on frequency. Java Code for LFU Cache: import java.util.; class LFUCache { private final int capacity; private final Map cache; // Stores key-value pairs private final Map frequency; // Stores frequency of keys private final Map frequencyList; // Stores keys with the same frequency private int minFrequency; public LFUCache(int capacity) { this.capacity = capacity; this.cache = new HashMap(); this.frequency = new HashMap(); this.frequencyList = new HashMap(); this.minFrequency = 0; } public int get(int key) { if (!cache.containsKey(key)) return -1; increaseFrequency(key); return cache.get(key); } public void put(int key, int value) { if (capacity = capacity) { evictLFU(); } cache.put(key, value); frequency.put(key, 1); frequencyList.putIfAbsent(1, new LinkedHashSet()); frequencyList.get(1).add(key); minFrequency = 1; } private void increaseFrequency(int key) { int freq = frequency.get(key); frequency.put(key, freq + 1); frequencyList.get(freq).remove(key); if (freq == minFrequency && frequencyList.get(freq).size() == 0) { minFrequency++; } frequencyList.putIfAbsent(freq + 1, new LinkedHashSet()); frequencyList.get(freq + 1).add(key); } private void evictLFU() { LinkedHashSet leastFrequentKeys = frequencyList.get(minFrequency); Integer keyToEvict = leastFrequentKeys.iterator().next(); leastFrequentKeys.remove(keyToEvict); cache.remove(keyToEvict); frequency.remov

Apr 27, 2025 - 09:45

LRU Cache (Least Recently Used)

Concept of LRU Cache:

In an LRU cache, when the cache reaches its limit, the least recently used item is removed to make space for new data. It ensures that the most recently accessed data remains in the cache.

Data Structures Used:

HashMap: To store the key-value pairs.
Doubly Linked List: To keep track of the order of access, where the most recently used element is at the front, and the least recently used one is at the back.

Java Code for LRU Cache:

import java.util.*;

class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> cache;
    private final DoublyLinkedList order;

    // Node for the doubly linked list
    class Node {
        int key, value;
        Node prev, next;
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    // Doubly Linked List for keeping track of recent usage
    class DoublyLinkedList {
        Node head, tail;
        DoublyLinkedList() {
            head = new Node(-1, -1);
            tail = new Node(-1, -1);
            head.next = tail;
            tail.prev = head;
        }

        void addFirst(Node node) {
            node.next = head.next;
            node.prev = head;
            head.next.prev = node;
            head.next = node;
        }

        void remove(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.order = new DoublyLinkedList();
    }

    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        Node node = cache.get(key);
        order.remove(node);
        order.addFirst(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            order.remove(node);
        } else if (cache.size() == capacity) {
            Node lruNode = order.tail.prev;
            cache.remove(lruNode.key);
            order.remove(lruNode);
        }

        Node newNode = new Node(key, value);
        cache.put(key, newNode);
        order.addFirst(newNode);
    }
}

Explanation:

Doubly Linked List: The doubly linked list allows quick removal and insertion of nodes, ensuring that the most recently used node is at the front and the least recently used node is at the back.
HashMap: Stores the key to Node mapping to allow fast lookups.
get(): If the key exists, it is moved to the front of the list (marking it as most recently used).
put(): If the key is already in the cache, it updates the value and moves the key to the front. If the cache is full, it evicts the least recently used item.

LFU Cache (Least Frequently Used)

Concept of LFU Cache:

In an LFU cache, when the cache reaches its limit, the least frequently used item is removed. The key idea is to track how often each item is accessed.

Data Structures Used:

HashMap: To store the key-value pairs.
HashMap: To track the frequency of access.
Doubly Linked List: To store keys with the same frequency and manage eviction based on frequency.

Java Code for LFU Cache:

import java.util.*;

class LFUCache {
    private final int capacity;
    private final Map<Integer, Integer> cache; // Stores key-value pairs
    private final Map<Integer, Integer> frequency; // Stores frequency of keys
    private final Map<Integer, LinkedHashSet<Integer>> frequencyList; // Stores keys with the same frequency
    private int minFrequency;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.frequency = new HashMap<>();
        this.frequencyList = new HashMap<>();
        this.minFrequency = 0;
    }

    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        increaseFrequency(key);
        return cache.get(key);
    }

    public void put(int key, int value) {
        if (capacity <= 0) return;

        if (cache.containsKey(key)) {
            cache.put(key, value);
            increaseFrequency(key);
            return;
        }

        if (cache.size() >= capacity) {
            evictLFU();
        }

        cache.put(key, value);
        frequency.put(key, 1);
        frequencyList.putIfAbsent(1, new LinkedHashSet<>());
        frequencyList.get(1).add(key);
        minFrequency = 1;
    }

    private void increaseFrequency(int key) {
        int freq = frequency.get(key);
        frequency.put(key, freq + 1);
        frequencyList.get(freq).remove(key);

        if (freq == minFrequency && frequencyList.get(freq).size() == 0) {
            minFrequency++;
        }

        frequencyList.putIfAbsent(freq + 1, new LinkedHashSet<>());
        frequencyList.get(freq + 1).add(key);
    }

    private void evictLFU() {
        LinkedHashSet<Integer> leastFrequentKeys = frequencyList.get(minFrequency);
        Integer keyToEvict = leastFrequentKeys.iterator().next();
        leastFrequentKeys.remove(keyToEvict);
        cache.remove(keyToEvict);
        frequency.remove(keyToEvict);
    }
}

Explanation:

frequencyList: This is a map of frequency to a set of keys. Keys with the same frequency are grouped together. We use this to quickly find which key to evict when the cache is full.
cache: Stores the key-value pairs.
frequency: Stores the frequency of access for each key.
minFrequency: Tracks the current least frequent access frequency, which is the frequency of the keys to be evicted.
get(): Retrieves a key and increases its frequency.
put(): Inserts a new key or updates an existing key's value and frequency. If the cache is full, it evicts the least frequently used key.

Key Differences:

LRU (Least Recently Used): Removes the least recently accessed item when the cache reaches capacity.
LFU (Least Frequently Used): Removes the least frequently accessed item when the cache reaches capacity.

Use Cases:

LRU is useful when you want to keep the most recently accessed data.
LFU is ideal when you want to prioritize caching the most frequently accessed data over recency.

You can integrate these cache implementations into your system to improve performance by reducing the need to repeatedly compute or fetch data. Both algorithms offer efficient solutions for cache eviction based on different access patterns.