Question

Define the meaning of following java code in public void refer, line by line. thank you

public class LRUCache {

    // store keys of cache

    static Deque<Integer> dq;

    // store references of key in cache

    static HashSet<Integer> map;

    // maximum capacity of cache

    static int csize;

  

    LRUCache(int n)

    {

        dq = new LinkedList<>();

        map = new HashSet<>();

        csize = n;

    }

    public void refer(int x)

    {

        if (!map.contains(x)) {

            if (dq.size() == csize) {

                int last = dq.removeLast();

                map.remove(last);

            }

        }

        else {

            int index = 0, i = 0;

            Iterator<Integer> itr = dq.iterator();

            while (itr.hasNext()) {

                if (itr.next() == x) {

                    index = i;

                    break;

                }

                i++;

            }

            dq.remove(index);

        }

        dq.push(x);

        map.add(x);

    }

Answer 1

Understanding the Concept.....

1st of all the deque internally uses LinkedList to store the data in an ordered way however, the map does not store the data in an ordered way but the feature of map is that we can find our desired data whether it is present in our map collection or not in O(1) time.

So, we will store our data in two Data Structure which are LinkedList and HashSet.

LinkedList-----> is used for maintaining the order in which search query in the cache is coming.

for example:

Suppose the cache size is 4.

if the order of query is like 1 (1) (*here front means Recently used.)

6 (6--->1)

5 (5---->6---->1)

7 (7----->5------>6------>1)

      but now if another query like 6 comes then (6----->7------>5----->1) i.e; 6 comes in the recently used state. Here we simply deleted 6 from its initial position and put into the front.

And if query like 8 comes then as we can see 8 is not present in the cache that means we have to bring it from the memory and put it into the front of the cache and as the size of our cache is only 4 that means we have to delete the last element (Least used Element) from cache then our cache will looks like 8---->6----->7------>5.

This is self sufficient in implementing the Cache.

But

But

why we need the HashSet data structure if it is self-sufficient?

HashSet------> As we discussed above the HashSet data structure can tell in O(1) time weather the given data present in it or not. But in case of linked list we can only tell this only by traversing the linked list which overall takes O(N) time. Suppose if our size of the cache is 1000000 then effectively for each query we have to traverse the 1000000 to know whether the data is available or not which will actually increase the time and make our cache slow.

And the problem with the HashSet is that it stores the data in a random way unlike as data stored in Linked List is stored in an ordered.

We have to use the properties of both of the data structure to bring the best out of them.

We will store the data both data structures i.e; in  HashSet and LinkedList.

We will use HashSet to know whether the given data is available inside the cache or not and LinkedList to maintain the order.

if data is available in the HashSet that means it is also available in the LinkedList.

so we will bring that data from the current position in Linked to the front of the LinkedList without affecting the Map.

if it is not available in the map that means it is also not available in linked list so we will add that data in front of LinkedList and also in the Map.

In case when the data is not available in the map i.e; not in the cache then we have to add that data in the cache i.e;in Map and in the LinkedList and suppose the size of the cache is full, then we have to delete the last element of the LinkedList because it the last element which is not used recently and also we have to delete that element from the Map as well.

Understanding the Code

public class LRUCache {

    // store keys of cache

    static Deque<Integer> dq; ---------------> It is simply a doubly liked list that will store the data in order.

    // store references of key in cache

static HashSet<Integer> map;--> It is simply a HashSet that will facilitate us to know whether the data is present or not in O(1).

    // maximum capacity of cache

    static int csize; --------->size of the cache..

  

    LRUCache(int n) -------> it is just only the constructor that will run when we create the object of LRU and put the Object of

    { -->linked list and hashset.

        dq = new LinkedList<>();

        map = new HashSet<>();

        csize = n;

    }

public void refer(int x) ------>it is the important function that will do the LRU operations where x is the data

to be searched in cache.

    {

        if (!map.contains(x)) { ------> condition if data is not present in the cache...then we have to add in cache(i.e; in Likned List & in HashSet(named as dp & map here))

            if (dq.size() == csize) { -------> if the cache is full which will be known from by comparing size of likedlist i.e dp is equals to the cache size. if it is then we have to delete the last element of the linked list and we also have to delete it from the map as well.

                int last = dq.removeLast(); -------> getting the last element and removing from linkedlist.

                map.remove(last); ------------------> also removing it from the map (i.e; HashSet).

            }

        }

        else { ----------------------> Which means yes element is Present in the cache..

            int index = 0, i = 0;

            Iterator<Integer> itr = dq.iterator(); ------> Map will only tell wheather it is present or not and will not give the positon of that element.

            while (itr.hasNext()) { -------> so we will traverse the linked list and find the correct postion of the data

                if (itr.next() == x) {

                    index = i; -------> index will store the postion of that data or element and after that we will break the loop.

                    break;

                }

                i++;

            }

            dq.remove(index); -----------> we will remove that data from the linkedlist and as now it have to come in front..

        }

        dq.push(x); --------> pushing data in front of the linkedlist and it is the Least Recently used element.

        map.add(x); --------->we will also add it to the HashSet

    }