LRU cache in Java with Generics and O(1) operations

Question

This is a question that comes up a lot in job interviews. The idea is to define a data structure instead of using Java's built in LinkedHashMap.

An LRU cache deletes the least recently used entry to insert a new one. So, given the following scenario:

 A - B - C - D - E

Where A is the least recently used item, if we were to insert F, we need to remove A.

This can be easily implemented if we keep a HashMap with the cache entries by (key,value) and a separate list that contains the elements' key and time of use. However, we would need to query the list to find the least recently used item, with a potential O(n) time complexity.

How can this structure be implemented in Java for Generic objects and O(1) operations?

This is different from the possible duplicate in that it focuses on efficiency (O(1) ops) and implementing the data structure itself, not extending Java's.

Answer 1

Golang Solution for leetcode problem i.e. Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. The functions get and put must each run in O(1) average time complexity.

Note:- Only 17 test cases are passing out of 21.

type Node struct {
    key  int
    val  int
    prev *Node
    next *Node
}

type LRUCache struct {
    cache    map[int]*Node
    currSize int
    capacity int
    leastRU  *Node
    mostRU   *Node
}

func Constructor(capacity int) LRUCache {
    return LRUCache{
        capacity: capacity,
        currSize: 0,
        leastRU: &Node{
            key:  0,
            val:  0,
            prev: nil,
            next: nil,
        },
        mostRU: &Node{
            key:  0,
            val:  0,
            prev: nil,
            next: nil,
        },
        cache: make(map[int]*Node),
    }

}

func (this *LRUCache) Get(key int) int {
    tempNode, ok := this.cache[key]
    if !ok {
        return -1
    } else if this.mostRU.key == tempNode.key {
        return tempNode.val
    }

    nextNode := tempNode.next
    prevNode := tempNode.prev

    if this.leastRU.key == tempNode.key {
        nextNode.prev = nil
        this.leastRU = nextNode

    } else if this.mostRU.key != tempNode.key {
        prevNode.next = nextNode
        nextNode.prev = prevNode
    }

    tempNode.prev = this.mostRU
    this.mostRU.next = tempNode
    this.mostRU = tempNode
    this.mostRU.next = nil

    return tempNode.val
}

func (this *LRUCache) Put(key int, value int) {
    if _, ok := this.cache[key]; ok {
        this.cache[key].val = value
        if this.leastRU.key != this.mostRU.key {
            tempNode := this.cache[key]
            nextNode := tempNode.next
            prevNode := tempNode.prev

            if this.leastRU.key == tempNode.key {
                nextNode.prev = nil
                this.leastRU = nextNode

            } else if this.mostRU.key != tempNode.key {
                prevNode.next = nextNode
                nextNode.prev = prevNode
            }

            tempNode.prev = this.mostRU
            this.mostRU.next = tempNode
            this.mostRU = tempNode
            this.mostRU.next = nil
        }

        return
    } else {

        newNode := &Node{
            key:  key,
            val:  value,
            prev: nil,
            next: nil,
        }
        this.mostRU.next = newNode
        newNode.prev = this.mostRU
        this.mostRU = newNode
        this.cache[key] = newNode
        if this.currSize == this.capacity {
            fmt.Println(key, this.leastRU.key)
            delete(this.cache, this.leastRU.key)
            this.leastRU = this.leastRU.next
            this.leastRU.prev = nil
        } else if this.currSize < this.capacity {
            if this.currSize == 0 {
                this.leastRU = newNode
            }
            this.currSize++
        }
    }

    // fmt.Println(this.cache)
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

Answer 2

Implementation that passes the tests of the leetcode question with simple unit tests

I have made a pull request with this at: https://github.com/haoel/leetcode/pull/90/files The code was later improved here in the answer with accessOrder = true and I didn't bother to make another pull request though, so the code here is slightly better for now.

LRUCache.java

import java.util.Iterator;
import java.util.LinkedHashMap;

public class LRUCache {

    private int capacity;
    private LinkedHashMap<Integer,Integer> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new LinkedHashMap<>(16, 0.75f, true);
    }

    public int get(int key) {
        Integer value = this.map.get(key);
        if (value == null) {
            value = -1;
        }
        return value;
    }

    public void put(int key, int value) {
        if (
            !this.map.containsKey(key) &&
            this.map.size() == this.capacity
        ) {
            Iterator<Integer> it = this.map.keySet().iterator();
            it.next();
            it.remove();
        }
        this.map.put(key, value);
    }
}

LRUCacheTest.java

public class LRUCacheTest {
    public static void main(String[] args) {
        LRUCache c;

        // Starts empty.
        c = new LRUCache(2);
        assert c.get(1) == -1;

        // Below capcity.
        c = new LRUCache(2);
        c.put(1, 1);
        assert c.get(1) == 1;
        assert c.get(2) == -1;
        c.put(2, 4);
        assert c.get(1) == 1;
        assert c.get(2) == 4;

        // Above capacity, oldest is removed.
        c = new LRUCache(2);
        c.put(1, 1);
        c.put(2, 4);
        c.put(3, 9);
        assert c.get(1) == -1;
        assert c.get(2) == 4;
        assert c.get(3) == 9;

        // get renews entry
        c = new LRUCache(2);
        c.put(1, 1);
        c.put(2, 4);
        assert c.get(1) == 1;
        c.put(3, 9);
        assert c.get(1) == 1;
        assert c.get(2) == -1;
        assert c.get(3) == 9;

        // Double put does not remove due to capacity.
        c = new LRUCache(2);
        assert c.get(2) == -1;
        c.put(2, 6);
        assert c.get(1) == -1;
        c.put(1, 5);
        c.put(1, 2);
        assert c.get(1) == 2;
        assert c.get(2) == 6;
    }
}

removeEldestEntry() alternative implementation

Not sure it is worth it as it takes the same number of lines, but here goes for completeness:

import java.util.LinkedHashMap;
import java.util.Iterator;
import java.util.Map;

import java.io.*;

class LinkedhashMapWithCapacity<K,V> extends LinkedHashMap<K,V> {
    private int capacity;

    public LinkedhashMapWithCapacity(int capacity) {
        super(16, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return this.size() > this.capacity;
    }
}

public class LRUCache {

    private LinkedhashMapWithCapacity<Integer,Integer> map;

    public LRUCache(int capacity) {
        this.map = new LinkedhashMapWithCapacity<>(capacity);
    }

    public int get(int key) {
        Integer value = this.map.get(key);
        if (value == null) {
            value = -1;
        }
        return value;
    }

    public void put(int key, int value) {
        this.map.put(key, value);
    }
}

Tested on Ubuntu 20.10, OpenJDK 11.0.10.

Answer 3

This solution would also pass LeetCode's online Judge for the LRU cache problem, similar to this answer. Here we use HashMap with a Doubly Linked List. The memory complexity is constant also.

public class LRUCache {
    private final Node head = new Node(0, 0);
    private final Node tail = new Node(0, 0);
    private final Map<Integer, Node> cache;
    private final int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>(capacity);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = cache.get(key);

        if (node == null) {
            return -1;
        }

        remove(node);
        append(node);

        return node.value;
    }

    public void put(int key, int value) {
        Node currentNode = cache.get(key);

        if (currentNode != null) {
            updateNodeValue(value, currentNode);

        } else {
            createNewNode(key, value);
        }
    }

    private void createNewNode(int key, int value) {
        if (cache.size() == capacity) {
            cache.remove(tail.prev.key);
            remove(tail.prev);
        }

        Node node = new Node(key, value);
        append(node);
        cache.put(key, node);
    }

    private void updateNodeValue(int value, Node currentNode) {
        remove(currentNode);
        currentNode.value = value;
        append(currentNode);
    }

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

    private void append(Node node) {
        Node headNext = head.next;
        head.next = node;
        headNext.prev = node;
        node.prev = head;
        node.next = headNext;
    }

    private class Node {
        Node prev, next;
        int key, value;
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}

Here is LeetCode's solution for the LRU Cache problem:

public class LRUCache {

    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
    }

    private void addNode(DLinkedNode node) {
        /**
         * Always add the new node right after head.
         */
        node.prev = head;
        node.next = head.next;

        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
        /**
         * Remove an existing node from the linked list.
         */
        DLinkedNode prev = node.prev;
        DLinkedNode next = node.next;

        prev.next = next;
        next.prev = prev;
    }

    private void moveToHead(DLinkedNode node) {
        /**
         * Move certain node in between to the head.
         */
        removeNode(node);
        addNode(node);
    }

    private DLinkedNode popTail() {
        /**
         * Pop the current tail.
         */
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;

        head = new DLinkedNode();
        // head.prev = null;

        tail = new DLinkedNode();
        // tail.next = null;

        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);

        if (node == null) { return -1; }

        // move the accessed node to the head;
        moveToHead(node);

        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);

        if (node == null) {
            DLinkedNode newNode = new DLinkedNode();
            newNode.key = key;
            newNode.value = value;

            cache.put(key, newNode);
            addNode(newNode);

            ++size;

            if (size > capacity) {
                // pop the tail
                DLinkedNode tail = popTail();
                cache.remove(tail.key);
                --size;
            }

        } else {
            // update the value.
            node.value = value;
            moveToHead(node);
        }
    }
}

Reference

Code Review

Answer 4

From the question itself, we can see that the problem of O(n) operations arises when querying the linked list. Therefore, we need an alternative data structure. We need to be able to update the items' last access time from the HashMap without searching.

We can keep two separate data structures. A HashMap with (Key,Pointer) pairs and a doubly linked list which will work as the priority queue for deletion and store the Values. From the HashMap, we can point to an element in the doubly linked list and update its' retrieval time. Because we go directly from the HashMap to the item in the list, our time complexity remains at O(1)

For example, our doubly linked list can look like:

least_recently_used  -> A <-> B <-> C <-> D <-> E <- most_recently_used

We need to keep a pointer to the LRU and MRU items. The entries' values will be stored in the list and when we query the HashMap, we will get a pointer to the list. On get(), we need to put the item at the right-most side of the list. On put(key,value), if the cache is full, we need to remove the item at the left-most side of the list from both, the list and the HashMap.

The following is an example implementation in Java:

public class LRUCache<K, V>{

    // Define Node with pointers to the previous and next items and a key, value pair
    class Node<T, U> {
        Node<T, U> previous;
        Node<T, U> next;
        T key;
        U value;

        public Node(Node<T, U> previous, Node<T, U> next, T key, U value){
            this.previous = previous;
            this.next = next;
            this.key = key;
            this.value = value;
        }
    }

    private HashMap<K, Node<K, V>> cache;
    private Node<K, V> leastRecentlyUsed;
    private Node<K, V> mostRecentlyUsed;
    private int maxSize;
    private int currentSize;

    public LRUCache(int maxSize){
        this.maxSize = maxSize;
        this.currentSize = 0;
        leastRecentlyUsed = new Node<K, V>(null, null, null, null);
        mostRecentlyUsed = leastRecentlyUsed;
        cache = new HashMap<K, Node<K, V>>();
    }

    public V get(K key){
        Node<K, V> tempNode = cache.get(key);
        if (tempNode == null){
            return null;
        }
        // If MRU leave the list as it is
        else if (tempNode.key == mostRecentlyUsed.key){
            return mostRecentlyUsed.value;
        }

        // Get the next and previous nodes
        Node<K, V> nextNode = tempNode.next;
        Node<K, V> previousNode = tempNode.previous;

        // If at the left-most, we update LRU 
        if (tempNode.key == leastRecentlyUsed.key){
            nextNode.previous = null;
            leastRecentlyUsed = nextNode;
        }

        // If we are in the middle, we need to update the items before and after our item
        else if (tempNode.key != mostRecentlyUsed.key){
            previousNode.next = nextNode;
            nextNode.previous = previousNode;
        }

        // Finally move our item to the MRU
        tempNode.previous = mostRecentlyUsed;
        mostRecentlyUsed.next = tempNode;
        mostRecentlyUsed = tempNode;
        mostRecentlyUsed.next = null;

        return tempNode.value;

    }

    public void put(K key, V value){
        if (cache.containsKey(key)){
            return;
        }

        // Put the new node at the right-most end of the linked-list
        Node<K, V> myNode = new Node<K, V>(mostRecentlyUsed, null, key, value);
        mostRecentlyUsed.next = myNode;
        cache.put(key, myNode);
        mostRecentlyUsed = myNode;

        // Delete the left-most entry and update the LRU pointer
        if (currentSize == maxSize){
            cache.remove(leastRecentlyUsed.key);
            leastRecentlyUsed = leastRecentlyUsed.next;
            leastRecentlyUsed.previous = null;
        }

        // Update cache size, for the first added entry update the LRU pointer
        else if (currentSize < maxSize){
            if (currentSize == 0){
                leastRecentlyUsed = myNode;
            }
            currentSize++;
        }
    }
}

Answer 5

As K and Others have said this can be done with the LinkedHashMap class. At a squeeze you can get a minimal version in 15 lines of code.

@Ciro Santilli, why not just cut out the extra class definition? If the tests used put like other java maps then we wouldn't have to alias that method with a set method, which we would actually expect to return some sort of set view from the map.

import java.utils.LinkedHashMap
import java.util.Map;

public class LRUCache<K,V> extends LinkedHashMap<K,V> {
    private int maxSize;

    // and other constructors for load factor and hashtable capacity
    public LRUCache(int initialCapacity, float loadFactor, int maxSize) {
        super(initialCapacity, loadFactor, true);
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return size() > maxSize;
    }

    // I don't like this. set should return a set put should put an item
    public V set(K key, V value) {
        put(key, value)
    }
}

see here and In the Docs for more.

Answer 6

Using a Stack and a HashMap:

import java.util.HashMap;
import java.util.Stack;
public class LRU {
    private HashMap<String,Object> lruList;
    private Stack<String> stackOrder;
    private int capacity;
    LRU(int capacity){
      this.capacity = capacity;
      this.lruList = new HashMap<String, Object>(capacity);
      this.stackOrder = new Stack<String>();
    }
    public void put(String key, Object value){
      if(lruList.containsKey(key) || this.capacity < lruList.size() + 1) {
        if(lruList.containsKey(key)){
            String remove = key;
        }else{
            String remove = this.stackOrder.firstElement();
        }
        this.stackOrder.removeElement(remove);
        this.lruList.remove(remove);
      }
      this.lruList.put(key, value);
      this.stackOrder.add(key);
    }
    public Stack<String> get(){
      return this.stackOrder;
    }
    public Object get(String key){
      Object value = lruList.get(key);
      put(key, value);
      return value;
    }
}

public static void main(String[] args) {
    LRU lru = new LRU(3);
    lru.put("k1","v1");
    lru.put("k2","v2");
    lru.put("k3","v3");
    System.out.println(lru.get());
    lru.get("k1");
    System.out.println(lru.get());
    lru.put("k4","v4");
    System.out.println(lru.get());
}

Output:

[k1, k2, k3]

[k2, k3, k1]

[k3, k1, k4]

Answer 7

Here is the java implementation with Generics and LinkedHashMap, and complexity of O(1) on get() and put().

import java.util.LinkedHashMap;

public class LRUCache<K, V> {

    private LinkedHashMap<K, V> lruCacheMap;
    private final int capacity;
    private final boolean SORT_BY_ACCESS = true;
    private final float LOAD_FACTOR = 0.75F;

    public LRUCache(int capacity){
        this.capacity = capacity;
        this.lruCacheMap = new LinkedHashMap<>(capacity, LOAD_FACTOR, SORT_BY_ACCESS);
    }

    public V get(K k){
        return lruCacheMap.get(k);
    }

    public void put(K k, V v){
        if(lruCacheMap.containsKey(k)){
            lruCacheMap.remove(k);
        }else if(lruCacheMap.size() >= capacity){
            lruCacheMap.remove(lruCacheMap.keySet().iterator().next());
        }
        lruCacheMap.put(k, v);
    }

    public void printSequence(){
        System.out.println(lruCacheMap.keySet());
    }
}

This is the code for testing it:

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class TestLruCache {

    static class MyHardDrive {
        Map<String, Object> resources = new HashMap<>();

        MyHardDrive(){
            for(Character i='A'; i<='Z'; i++){
                resources.put(i.toString(), new Object());
            }
        }

        Object loadResource(String name){
            return resources.get(name);
        }
    }

    public static void main(String[] args) {
        MyHardDrive hd = new MyHardDrive();
        LRUCache<String,Object> cache = new LRUCache<>(4);

        for(String key: Arrays.asList("A","B","C","A","D","E","F","E","F","G","A")){
            Object object = cache.get(key);
            if(object==null){
                object = hd.loadResource(key);
                cache.put(key, object);
            }
            cache.printSequence();
        }
    }
}

Answer 8

/*Java implementation using Deque and HashMap    */

interface Cache<K,V> {
    V get(K key) ;
    void set(K key, V value);
}

class Node <K,V>{
    K key;
    V value;

    public Node (K key, V value) {
        this.key = key;
        this.value = value;
    }
}

public class LRUCache <K,V> implements Cache<K,V>{
    Deque<Node<K,V>> dq = new LinkedList<>();
    Map<K, Node<K, V>> map = new HashMap<>();
    static int SIZE;

    public LRUCache(int size) {
        this.SIZE = size;
    }

    public V get(K key) {
        Node<K,V> result = map.get(key);
        if(result != null) {
            dq.remove(result);
            dq.addFirst(result);
            System.out.println("Get " +key +" : " +result.value);
            return result.value;
        }
        else {
            System.out.println("Cache miss");
            return null;
        }
    }

    public void set(K key, V value) {
        System.out.println("Set " +key +" : " +value);
        Node<K,V> result = map.get(key);
        if(result != null) {
            result.value = value;
            map.put(key, result);
            dq.remove(result);
            dq.addFirst(result);
            System.out.println("Updated frame " +key+" as " + value);
        }
        else {
            if(dq.size() == SIZE) {
                Node<K,V> toRemove = dq.removeLast();
                map.remove(toRemove);
                System.out.println("Frame removed " +toRemove.key +" : " +toRemove.value);
            }
            Node<K,V> newNode = new Node(key, value);
            dq.addFirst(newNode);
            map.put(key, newNode);
            System.out.println("Frame added " + key + " : " +value);
        }
    }

    public static void main(String[] args) {
        Cache<Integer, Integer> lru = new LRUCache<>(5);
        lru.get(2);
        lru.set(1, 11);
        lru.set(2, 22);
        lru.get(2);
        lru.set(3, 33);
        lru.set(4, 44);
        lru.set(5, 55);
        lru.get(2);
        lru.get(1);
        lru.set(6, 66);
    }
}

Answer 9

I just write this very simple Generic solution though this one is not Thread safe.

LRUCacheDemo.java (public class)

import java.io.*;
import java.util.*;

/* We can keep two separate data structures. A HashMap with (Key,Pointer) pairs and a doubly linked
  list which will work as the priority queue for deletion and store the Values. From the HashMap, 
  we can point to an element in the doubly linked list and update its' retrieval time. Because we
  go directly from the HashMap to the item in the list, our time complexity remains at O(1) 
*/
public class LRUCacheDemo {
    public static void main(String args[]) {
        LRUCache<Integer, Integer> lru = new LRUCache<>(3);
        for(int i=1; i<=9; ++i) {
            lru.put(i, 100*i+10*i+i); //i   iii
        }

        lru.get(8);
        /* for(Map.Entry<Integer, Integer> entry : lru.entrySet()) {
            System.out.printf("\n%1$-5s  %2$-5s", entry.getKey(), entry.getValue());
        } */

        System.out.println("LRU  : " + lru);
    }
} 

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int CACHE_SIZE;

    //NOTE : LinkedHashMap have already given implementation for LRU, this class has just used those method
    //See http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedHashMap.java#LinkedHashMap

    // LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
    // accessOrder - to maintain in order of elements from least-recently accessed to most-recently.
    LRUCache(final int sizeIn) {
        super(sizeIn, 0.75F, true);
        this.CACHE_SIZE = sizeIn;
    }

    @Override 
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return size() > this.CACHE_SIZE; 
        /* Returns true if this map should remove its eldest entry. This method is invoked by put and putAll after 
           inserting a new entry into the map. It provides the implementor with the opportunity to remove the eldest 
           entry each time a new one is added. This is useful if the map represents a cache.
        */
    }
}

O/P :

LRU : {7=777, 9=999, 8=888}

Answer 10

@templatetypedef

public LinkedHashMap(int initialCapacity,
         float loadFactor,
         boolean accessOrder)

accessOrder - the ordering mode - true for access-order, false for insertion-order

Answer 11

public class LeastRecentlyUsed {

    public static <K, V> Map<K, V> leastRecentlyUsedCache(final int maxSize) {
        return new LinkedHashMap<K, V>(maxSize , 0.7f, true) {
            private static final long serialVersionUID = -3588047435434569014L;
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > maxSize;
            }
        };
    }

    public static void main(String[] args) {
        Map<Object, Object> leastRecentlyUsed = LeastRecentlyUsed.leastRecentlyUsedCache(3);
        leastRecentlyUsed.put("Robert", "Raj");
        leastRecentlyUsed.put("Auzi", "Aiz");
        leastRecentlyUsed.put("Sandy", "S");
        leastRecentlyUsed.put("Tript", "tty");  
        System.out.println(leastRecentlyUsed);
    }
  }

Answer 12

The LinkedHashMap designed with that in mind

From the javadocs:

A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). This kind of map is well-suited to building LRU caches. Invoking the put, putIfAbsent, get, getOrDefault, compute, computeIfAbsent, computeIfPresent, or merge methods results in an access to the corresponding entry (assuming it exists after the invocation completes). The replace methods only result in an access of the entry if the value is replaced. The putAll method generates one entry access for each mapping in the specified map, in the order that key-value mappings are provided by the specified map's entry set iterator. No other methods generate entry accesses. In particular, operations on collection-views do not affect the order of iteration of the backing map.

The removeEldestEntry(Map.Entry) method may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map.

Answer 13

Here is the java implementation

import java.util.HashMap;
import java.util.Map;

import com.nadeem.app.dsa.adt.Cache;
// Kind of linkedHashMap
public class LRUCache <K, V> implements Cache<K, V> {

private int capacity;
private Node<K, V> head, tail;
private Map<K, Node<K, V>> map;

private static final int DEFAULT_CAPACITY = 10;

public LRUCache(int capacity) {
    this.capacity = capacity;
    this.map = new HashMap<K, Node<K,V>>();
}

public LRUCache() {
    this(DEFAULT_CAPACITY);
}

@Override
public V get(K key) {
    V result = null;
    Node<K, V> node = this.map.get(key);
    if (node != null) {
        result = node.value;
        remove(node);
        addAsHead(node);
    }
    return result;
}

@Override
public void set(K key, V value) {
    Node<K, V> node = this.map.get(key);
    if (node == null) {
        Node<K, V> temp = new Node<K, V>(key, value);
        if (this.map.size() < this.capacity) {
            addAsHead(temp);
        } else {
            this.map.remove(this.tail.key);
            remove(this.tail);
            addAsHead(temp);
        }
        this.map.put(key, temp);
    } else {
        node.value = value;
        remove(node);
        addAsHead(node);
    }
}

private void remove(Node<K, V> node) {

    if (node.pre == null) {
        this.head = node.next;
    } else {
        node.pre.next = node.next;
    }

    if (node.next == null) {
        this.tail = node.pre;
    } else {
        node.next.pre = node.pre;
    }       
}

private void addAsHead(Node<K, V> node) {
    if (this.head == null) {
        this.head = node;
        this.tail = node;
    } else {
        this.head.pre = node;
        node.next = this.head;
        this.head = node;
    }
}

@Override
public void remove(K key) {
    Node<K, V> node = this.map.get(key);
    if (node != null) {
        this.remove(node);
    }       
}

private static class Node <S, T> {
    public S key;
    public T value;
    Node<S, T> pre;
    Node<S, T> next;

    Node(S key, T value) {
        this.key = key;
        this.value = value;
    }       
}

@Override
public int size() {
    return this.map.size();
}

}

Here is the unit test

public class LRUCacheTest {

private LRUCache<Integer, Integer> cache;

@Before
public void doBeforeEachTestCase() {
    this.cache = new LRUCache<Integer, Integer>(2);
}

@Test
public void setTest() {
    this.cache.set(1, 1);
    assertThat(this.cache.size(), equalTo(1));
    assertThat(this.cache.get(1), equalTo(1));

    this.cache.set(2, 2);
    assertThat(this.cache.size(), equalTo(2));
    assertThat(this.cache.get(2), equalTo(2));

    this.cache.set(3, 3);
    assertThat(this.cache.size(), equalTo(2));
    assertThat(this.cache.get(3), equalTo(3));

    this.cache.set(1, 3);
    assertThat(this.cache.size(), equalTo(2));
    assertThat(this.cache.get(1), equalTo(3));

    assertThat(this.cache.get(4), equalTo(null));
}

}

Answer 14

we can use LinkedHashMap .. it has feature to remove the eldest entry

import java.util.LinkedHashMap;
import java.util.Map;

public LRUCache<K, V> extends LinkedHashMap<K, V> {
  private int cacheSize;

  public LRUCache(int cacheSize) {
  super(16, 0.75, true);
  this.cacheSize = cacheSize;
}

  protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
  return size() >= cacheSize;
 }
}

The only catch is that by default the linked list order is the insertion order, not access. However one of the constructor exposes an option use the access order instead.

Answer 15

Idea

cache is nothing but circular arrayList. This list contains Entry. when ever new entries are coming add at the end of the list. That means least recently used element at the first. Suppose if you are reusing any element then unlink from the list and add at the end.

In order get any element we need to traverse the list which takes O(n) time complexity. In order to avoid this i'm maintaining HashMap>. Here k is key and IndexNode will contain a pointer to the Entry in the list. so we can get the O(1) time complexity.

working solution

package lrucache;

import java.util.HashMap;

public class LRUCache<K, V> {

    private transient Entry<K, V> header = new Entry<K, V>(null, null, null, null);
    public HashMap<K,IndexNode<Entry<K,V>>> indexMap = new HashMap<K,IndexNode<Entry<K,V>>>();
    private final int CACHE_LIMIT = 3;
    private int size;

    public LRUCache() {
        header.next = header.previous = header;
        this.size = 0;
    }

    public void put(K key,V value){
        Entry<K,V> newEntry = new Entry<K,V>(key,value,null,null);
        addBefore(newEntry, header);
    }

    private void addBefore(Entry<K,V> newEntry,Entry<K,V> entry){
        if((size+1)<(CACHE_LIMIT+1)){
            newEntry.next=entry;
            newEntry.previous=entry.previous;
            IndexNode<Entry<K,V>> indexNode = new IndexNode<Entry<K,V>>(newEntry);
            indexMap.put(newEntry.key, indexNode);
            newEntry.previous.next=newEntry;
            newEntry.next.previous=newEntry;
            size++;
        }else{
            Entry<K,V>  entryRemoved = remove(header.next);
            indexMap.remove(entryRemoved.key);
            addBefore(newEntry, entry);
        }
    }

    public void get(K key){
        if(indexMap.containsKey(key)){
            Entry<K,V> newEntry = remove(indexMap.get(key).pointer);
            addBefore(newEntry,header);
        }else{
            System.out.println("No such element was cached. Go and get it from Disk");
        }
    }

    private Entry<K,V> remove(Entry<K,V> entry){
        entry.previous.next=entry.next;
        entry.next.previous = entry.previous;
        size--;
        return entry;
    }

    public void display(){
        for(Entry<K,V> curr=header.next;curr!=header;curr=curr.next){
            System.out.println("key : "+curr.key+" value : " + curr.value);
        }
    }

    private static class IndexNode<Entry>{
        private Entry pointer;
        public IndexNode(Entry pointer){
            this.pointer = pointer;
        }
    }

    private static class Entry<K, V> {
        K key;
        V value;
        Entry<K, V> previous;
        Entry<K, V> next;

        Entry(K key, V value, Entry<K, V> next, Entry<K, V> previous) {
            this.key = key;
            this.value = value;
            this.next = next;
            this.previous = previous;
        }
    }

    public static void main(String[] args) {
        LRUCache<String, Integer> cache = new LRUCache<String, Integer>();
        cache.put("abc", 1);
        //cache.display();
        cache.put("def", 2);
        cache.put("ghi", 3);
        cache.put("xyz", 4);
        cache.put("xab", 5);
        cache.put("xbc", 6);
        cache.get("xyz");
        cache.display();
        System.out.println(cache.indexMap);
    }
}

output

key : xab value : 5
key : xbc value : 6
key : xyz value : 4
{xab=lrucache.LRUCache$IndexNode@c3d9ac, xbc=lrucache.LRUCache$IndexNode@7d8bb, xyz=lrucache.LRUCache$IndexNode@125ee71}