Implement an LRU cache

preface

LRU is the abbreviation for Least Recently Used.

The elimination strategy is commonly used for cache implementation. Since cache memory is very valuable, data needs to be eliminated according to some rules to ensure that memory is not full.

Redis, for example, has the following strategies:

strategy	describe
volatile-lru	Select the least recently used data from the data set with expiration time
volatile-ttl	Select the data to be obsolete from the set with expiration time
volatile-random	Select any data from a data set with an expiration time
allkeys-lru	Select the least recently used data from all data sets for elimination
allkeys-random	Randomly select data from all data sets for elimination
no-envicition	Deporting data is prohibited

From: github.com/CyC2018/Int…

Implement a

I have also had contact with an interview question before, and the requirements are as follows:

• Implement an LRU cache. When the cache reaches N, the least recently used data needs to be eliminated.
• Data that has not been accessed within N hours also needs to be eliminated.

Here is my implementation:

public class LRUAbstractMap extends java.util.AbstractMap {

    private final static Logger LOGGER = LoggerFactory.getLogger(LRUAbstractMap.class);

    /** * Check whether threads are overdue */
    private ExecutorService checkTimePool ;

    /** * map maximum size */
    private final static int MAX_SIZE = 1024 ;

    private final static ArrayBlockingQueue<Node> QUEUE = new ArrayBlockingQueue<>(MAX_SIZE) ;

    /** * Default size */
    private final static int DEFAULT_ARRAY_SIZE =1024 ;


    /** * Array length */
    private int arraySize ;

    /** * array */
    private Object[] arrays ;


    /** * Determine whether to stop flag */
    private volatile boolean flag = true ;


    /** * Timeout duration */
    private final static Long EXPIRE_TIME = 60 * 60 * 1000L ;

    /** * The size of the entire Map */
    private volatile AtomicInteger size  ;


    public LRUAbstractMap(a) {


        arraySize = DEFAULT_ARRAY_SIZE;
        arrays = new Object[arraySize] ;

        // Start a thread to check whether the value first queued is expired
        executeCheckTime();
    }

    /** * starts a thread to check if the first value to be queued is expired and set to daemon thread */
    private void executeCheckTime(a) {
        ThreadFactory namedThreadFactory = new ThreadFactoryBuilder()
                .setNameFormat("check-thread-%d")
                .setDaemon(true)
                .build();
        checkTimePool = new ThreadPoolExecutor(1.1.0L, TimeUnit.MILLISECONDS,
                new ArrayBlockingQueue<>(1),namedThreadFactory,new ThreadPoolExecutor.AbortPolicy());
        checkTimePool.execute(new CheckTimeThread()) ;

    }

    @Override
    public Set<Entry> entrySet(a) {
        return super.keySet();
    }

    @Override
    public Object put(Object key, Object value) {
        int hash = hash(key);
        int index = hash % arraySize ;
        Node currentNode = (Node) arrays[index] ;

        if (currentNode == null){
            arrays[index] = new Node(null.null, key, value);

            // Write to queue
            QUEUE.offer((Node) arrays[index]) ;

            sizeUp();
        }else {
            Node cNode = currentNode ;
            Node nNode = cNode ;

            // If it exists, override it
            if (nNode.key == key){
                cNode.val = value ;
            }

            while(nNode.next ! =null) {// The presence of the key overrides the simple judgment
                if (nNode.key == key){
                    nNode.val = value ;
                    break ;
                }else {
                    // Add a list if it does not exist
                    sizeUp();
                    Node node = new Node(nNode,null,key,value) ;

                    // Write to queueQUEUE.offer(currentNode) ; cNode.next = node ; } nNode = nNode.next ; }}return null ;
    }


    @Override
    public Object get(Object key) {

        int hash = hash(key) ;
        int index = hash % arraySize ;
        Node currentNode = (Node) arrays[index] ;

        if (currentNode == null) {return null ;
        }
        if (currentNode.next == null) {// Update time
            currentNode.setUpdateTime(System.currentTimeMillis());

            // There is no conflict
            return currentNode ;

        }

        Node nNode = currentNode ;
        while(nNode.next ! =null) {if (nNode.key == key){

                // Update time
                currentNode.setUpdateTime(System.currentTimeMillis());

                return nNode ;
            }

            nNode = nNode.next ;
        }

        return super.get(key);
    }


    @Override
    public Object remove(Object key) {

        int hash = hash(key) ;
        int index = hash % arraySize ;
        Node currentNode = (Node) arrays[index] ;

        if (currentNode == null) {return null ;
        }

        if (currentNode.key == key){
            sizeDown();
            arrays[index] = null ;

            // Remove the queue
            QUEUE.poll();
            return currentNode ;
        }

        Node nNode = currentNode ;
        while(nNode.next ! =null) {if (nNode.key == key){
                sizeDown();
                // Next points to the next node of the current node
                nNode.pre.next = nNode.next ;
                nNode = null ;

                // Remove the queue
                QUEUE.poll();

                return nNode;
            }

            nNode = nNode.next ;
        }

        return super.remove(key);
    }

    /** * add size */
    private void sizeUp(a){

        // The value of put is thought to contain data
        flag = true ;

        if (size == null){
            size = new AtomicInteger() ;
        }
        int size = this.size.incrementAndGet();
        if (size >= MAX_SIZE) {
            // Find the data in the queue header
            Node node = QUEUE.poll() ;
            if (node == null) {throw new RuntimeException("data error"); }// Remove the keyObject key = node.key ; remove(key) ; lruCallback() ; }}/** * The number is reduced */
    private void sizeDown(a){

        if (QUEUE.size() == 0){
            flag = false ;
        }

        this.size.decrementAndGet() ;
    }

    @Override
    public int size(a) {
        return size.get() ;
    }

    /**
     * 链表
     */
    private class Node{
        private Node next ;
        private Node pre ;
        private Object key ;
        private Object val ;
        private Long updateTime ;

        public Node(Node pre,Node next, Object key, Object val) {
            this.pre = pre ;
            this.next = next;
            this.key = key;
            this.val = val;
            this.updateTime = System.currentTimeMillis() ;
        }

        public void setUpdateTime(Long updateTime) {
            this.updateTime = updateTime;
        }

        public Long getUpdateTime(a) {
            return updateTime;
        }

        @Override
        public String toString(a) {
            return "Node{" +
                    "key=" + key +
                    ", val=" + val +
                    '} '; }}/** * copy hash implementation of HashMap *@param key
     * @return* /
    public int hash(Object key) {
        int h;
        return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    private void lruCallback(a){
        LOGGER.debug("lruCallback");
    }


    private class CheckTimeThread implements Runnable{

        @Override
        public void run(a) {
            while (flag){
                try {
                    Node node = QUEUE.poll();
                    if (node == null) {continue ;
                    }
                    Long updateTime = node.getUpdateTime() ;

                    if((updateTime - System.currentTimeMillis()) >= EXPIRE_TIME){ remove(node.key) ; }}catch (Exception e) {
                    LOGGER.error("InterruptedException");
                }
            }
        }
    }

}
Copy the code

Interested friends can directly from:

Github.com/crossoverJi…

Download the code to run locally.

The code looks more, in fact, the implementation of the idea is relatively simple:

• It uses the same way of saving data as HashMap, but implements a simple version manually.
• Internally, a queue is used to store data for each write.
• Check whether the cache is larger than the threshold N. If yes, delete the data in the queue header according to the FIFO feature of the queue. Because the data in the queue header must be put in first.
• A daemon thread is also started to determine whether the data put in first is expired (because even if it is, the data put in first is most likely to meet the expiration condition).
• Setting it as a daemon thread is a better indication of its purpose (in the worst case, if it is a user thread, it may end up causing the program to fail because the thread is always running, which is not the case with the daemon thread).

The above code satisfies the general function, but there is a fatal problem.

If the least recently used data is not satisfied, the deleted data is the first data to be added.

However, the PUT Get process is a simple implementation of HashMap, and you can understand HashMap a little better.

Realize the

So how to implement a full LRU cache, this time regardless of expiration time.

In fact, there are some ideas from the previous implementation:

• To keep track of the least recent use, at least one ordered set is required to guarantee the order of the writes.
• The ability to update the order of data after it has been used.

Based on these two points, it’s easy to think of a common data structure: linked lists.

1. Puts data into the linked list header each time it is written.
2. Move data to a header when using data.
3. Remove the tail of the list when the number of caches exceeds the threshold.

Hence the following implementation:

public class LRUMap<K.V> {
    private final Map<K, V> cacheMap = new HashMap<>();

    /** * Maximum cache size */
    private int cacheSize;

    /** * Node size */
    private int nodeCount;


    /** ** header */
    private Node<K, V> header;

    /** * end */
    private Node<K, V> tailer;

    public LRUMap(int cacheSize) {
        this.cacheSize = cacheSize;
        // The next node of the header is null
        header = new Node<>();
        header.next = null;

        // The last node of the end node is null
        tailer = new Node<>();
        tailer.tail = null;

        // The top node of the bidirectional list head points to the tail node
        header.tail = tailer;

        // The lower node of the tail points to the head node
        tailer.next = header;


    }

    public void put(K key, V value) {
        cacheMap.put(key, value);

        // Add nodes to the bidirectional list
        addNode(key, value);
    }

    public V get(K key){

        Node<K, V> node = getNode(key);

        // Move the header
        moveToHead(node) ;

        return cacheMap.get(key);
    }

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

        // If it is the last node
        if (node.tail == null){
            node.next.tail = null ;
            tailer = node.next ;
            nodeCount -- ;
        }

        // If it is already the head node, it is not processed
        if (node.next == null) {return ;
        }

        // If it is an intermediate node
        if(node.tail ! =null&& node.next ! =null) {// Its previous node points to its next node and deletes the current node
            node.tail.next = node.next ;
            nodeCount -- ;
        }

        // Finally add the current node to the header
        // Note that a new object is required, otherwise the original Node still has the following reference, causing memory overflow.
        node = new Node<>(node.getKey(),node.getValue()) ;
        addHead(node) ;

    }

    /** * List query efficiency is low *@param key
     * @return* /
    private Node<K,V> getNode(K key){
        Node<K,V> node = tailer ;
        while(node ! =null) {if (node.getKey().equals(key)){
                return node ;
            }

            node = node.next ;
        }

        return null ;
    }


    /** * writes the header *@param key
     * @param value
     */
    private void addNode(K key, V value) {

        Node<K, V> node = new Node<>(key, value);

        // Delete the last one
        if (cacheSize == nodeCount) {
            // Delete the end node
            delTail();
        }

        // Write the header
        addHead(node);

    }



    /** * add header **@param node
     */
    private void addHead(Node<K, V> node) {

        // Write the header
        header.next = node;
        node.tail = header;
        header = node;
        nodeCount++;

        // If more than two data are written, the initialized header and tail are deleted
        if (nodeCount == 2) {
            tailer.next.next.tail = null; tailer = tailer.next.next; }}private void delTail(a) {
        // Remove the endnode from the cache
        cacheMap.remove(tailer.getKey());

        // Delete the end node
        tailer.next.tail = null;
        tailer = tailer.next;

        nodeCount--;

    }

    private class Node<K.V> {
        private K key;
        private V value;
        Node<K, V> tail;
        Node<K, V> next;

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

        public Node(a) {}public K getKey(a) {
            return key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public V getValue(a) {
            return value;
        }

        public void setValue(V value) {
            this.value = value; }}@Override
    public String toString(a) {
        StringBuilder sb = new StringBuilder() ;
        Node<K,V> node = tailer ;
        while(node ! =null){
            sb.append(node.getKey()).append(":")
                    .append(node.getValue())
                    .append("-- >"); node = node.next ; }returnsb.toString(); }}Copy the code

Source: github.com/crossoverJi…

In practice, when writing:

    @Test
    public void put(a) throws Exception {
        LRUMap<String,Integer> lruMap = new LRUMap(3); lruMap.put("1".1); lruMap.put("2".2); lruMap.put("3".3); System.out.println(lruMap.toString()); lruMap.put("4".4); System.out.println(lruMap.toString()); lruMap.put("5".5); System.out.println(lruMap.toString()); }/ / output:
1:1-->2:2-->3:3-->
2:2-->3:3-->4:4-->
3:3-->4:4-->5:5-->
Copy the code

When using:

    @Test
    public void get(a) throws Exception {
        LRUMap<String,Integer> lruMap = new LRUMap(3); lruMap.put("1".1); lruMap.put("2".2); lruMap.put("3".3); System.out.println(lruMap.toString()); System.out.println("= = = = = = = = = = = = = =");

        Integer integer = lruMap.get("1");
        System.out.println(integer);
        System.out.println("= = = = = = = = = = = = = =");
        System.out.println(lruMap.toString());
    }
    
/ / output
1:1-->2:2-->3:3-- > = = = = = = = = = = = = = =1= = = = = = = = = = = = = =2:2-->3:3-->1:1-->
Copy the code

To achieve the same idea as mentioned above, let’s say the key points:

• The data is stored directly using the HashMap.
• Internally, a bidirectional linked list is used to store data, so there is a header and a tailer.
• Each time you write a header or delete a tail, you rely on the header tailer. If you feel confused, you are advised to implement a linked list to familiarize yourself with it, or use the following object diagram to understand it.
• When using data to move to the head of a list, the first step is to find the node in the bidirectional list. This is where the problem with linked lists comes in. Search efficiency is very low, the worst needO(N). It then moves depending on the current node.
• The initialized header and tail nodes need to be deleted when the size of the linked list is determined to be equal to 2. This is because initialization generates two two-way nodes with no data to form a data structure. When the real data comes in, it needs to be deleted to facilitate subsequent operations (this can be further optimized).
• All of the above operations are thread-unsafe and require user control.

Here is the object diagram:

Initialization time

When writing data

LRUMap<String,Integer> lruMap = new LRUMap(3); lruMap.put("1".1);Copy the code

lruMap.put("2".2);Copy the code

lruMap.put("3".3);Copy the code

lruMap.put("4".4);Copy the code

When obtaining data

The data is the same as above:

Integer integer = lruMap.get("2");
Copy the code

The above pictures should give you a good idea of how the data is stored.

Implement three

In fact, if you are familiar with Java collections, you will notice that the structure above is very similar to LinkedHashMap.

For those not familiar with this, take a look at the underlying LinkedHashMap analysis.

So we can use it to achieve:

public class LRULinkedMap<K.V> {


    /** * Maximum cache size */
    private int cacheSize;

    private LinkedHashMap<K,V> cacheMap ;


    public LRULinkedMap(int cacheSize) {
        this.cacheSize = cacheSize;

        cacheMap = new LinkedHashMap(16.0.75 F.true) {@Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                if (cacheSize + 1 == cacheMap.size()){
                    return true ;
                }else {
                    return false; }}}; }public void put(K key,V value){
        cacheMap.put(key,value) ;
    }

    public V get(K key){
        return cacheMap.get(key) ;
    }


    public Collection<Map.Entry<K, V>> getAll() {
        return newArrayList<Map.Entry<K, V>>(cacheMap.entrySet()); }}Copy the code

Source: github.com/crossoverJi…

This time it’s a little more succinct, just a few lines of code (the specific logical LinkedHashMap has already been implemented for us)

Actual effect:

    @Test
    public void put(a) throws Exception {
        LRULinkedMap<String,Integer> map = new LRULinkedMap(3); map.put("1".1);
        map.put("2".2);
        map.put("3".3);

        for (Map.Entry<String, Integer> e : map.getAll()){
            System.out.print(e.getKey() + ":" + e.getValue() + "\t");
        }

        System.out.println("");
        map.put("4".4);
        for (Map.Entry<String, Integer> e : map.getAll()){
            System.out.print(e.getKey() + ":" + e.getValue() + "\t"); }}/ / output
1 : 1	2 : 2	3 : 3	
2 : 2	3 : 3	4 : 4	    
Copy the code

When using:

    @Test
    public void get(a) throws Exception {
        LRULinkedMap<String,Integer> map = new LRULinkedMap(4); map.put("1".1);
        map.put("2".2);
        map.put("3".3);
        map.put("4".4);

        for (Map.Entry<String, Integer> e : map.getAll()){
            System.out.print(e.getKey() + ":" + e.getValue() + "\t");
        }

        System.out.println("");
        map.get("1");for (Map.Entry<String, Integer> e : map.getAll()){
            System.out.print(e.getKey() + ":" + e.getValue() + "\t"); }}}/ / output
1 : 1	2 : 2	3 : 3	4 : 4	
2 : 2	3 : 3	4 : 4	1 : 1
Copy the code

LinkedHashMap also maintains a bidirectional queue and is initialized with a buffer size threshold. During initialization, you need to define whether to delete recently infrequently used data. If yes, data is managed according to implementation 2.

The main code overrides the removeEldestEntry method of LinkedHashMap:

    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }
Copy the code

By default, it returns false, that is, it does not care if the threshold is exceeded.

So we custom return true above the threshold so that LinkedHashMap will remove the least recently used data for us.

conclusion

That’s the implementation of the LRU cache, at least in everyday use.

Guava’s implementation is also widely used in the industry, and it supports multiple expiration policies.

extra

Recently in the summary of some Java related knowledge points, interested friends can maintain together.

Address: github.com/crossoverJi…