6
\$\begingroup\$

Idea

The cache is nothing but a circular arrayList. This list contains Entry<K,V>. Whenever 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 to get any element, we need to traverse the list, which takes \$O(n)\$ time complexity. In order to avoid this, I'm maintaining HashMap<K,IndexNode<Entry>>. 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}
\$\endgroup\$
8
\$\begingroup\$

You can instead use a LinkedHashMap, which lets you get the in access order if you made it with the (int, float, boolean) constructor.

Then adding means removing map.entrySet().iterator().next().remove() if it becomes too large.

However LinkedHashMap is specially designed to let a subclass decide when to remove the oldest entry using the removeEldestEntry which gets called on each put:

public class MyLRUCache<K,V> extends LinkedHashMap<K,V> {

    private static final int MAX_CACHE = 4;

    public MyLRUCache(){
        super(MAX_CACHE, 1, true); 
        // sets the super class to use access order instead of insertion order.
    }

    @Override
    protected boolean removeEldestEntry(
            java.util.Map.Entry<K, V> eldest) {
        return size() > MAX_CACHE;
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Have you considered composition instead of inheritance? \$\endgroup\$ – janos Feb 10 '15 at 16:01
  • 2
    \$\begingroup\$ @janos except linkedHashMap was designed for inheritance. the first part assumes you were still using composition \$\endgroup\$ – ratchet freak Feb 10 '15 at 16:02
  • 2
    \$\begingroup\$ Oh I see. Composition would be the natural thing to do here, except the LinkedHashMap is just not flexible enough to allow this. So we have no choice, it forces us to extend, which sucks, but the most reasonable solution here \$\endgroup\$ – janos Feb 10 '15 at 16:21
  • 3
    \$\begingroup\$ @janos: Actually, no. You could let an inner class inherit from LinkedHashMap and expose methods on an outer one. \$\endgroup\$ – Stefan Hanke Feb 10 '15 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.