LRU算法 + Java实现代码 /自定义双链表/Java自带的双链表

- 日理万妓 2021-09-25 03:34 305阅读 0赞

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

*  最常见的实现是使用一个链表保存缓存数据，详细算法实现如下

![3620e4abe48eaed95f8051b837510848.png][]

1.  新数据插入到链表头部；
2.  每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
3.  当链表满的时候，将链表尾部的数据丢弃。  
    【命中率】  
    当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。  
    【复杂度】  
    实现简单。  
    【代价】  
    命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部。

在一般标准的操作系统教材里，会用下面的方式来演示 LRU 原理，假设内存只能容纳3个页大小，按照 7 0 1 2 0 3 0 4 的次序访问页。假设内存按照栈的方式来描述访问时间，在上面的，是最近访问的，在下面的是，最远时间访问的，LRU就是这样工作的。  
但是如果让我们自己设计一个基于 LRU 的缓存，这样设计可能问题很多，这段内存按照访问时间进行了排序，会有大量的内存拷贝操作，所以性能肯定是不能接受的。

那么如何设计一个LRU缓存，使得放入和移除都是 O(1) 的，我们需要把访问次序维护起来，但是不能通过内存中的真实排序来反应，有一种方案就是使用双向链表。

【如果是单链表的话（单链表只知道head指针），移除尾部节点时，时间复杂度不再是O(1)，而是O(n)】

**基于 HashMap 和 双向链表实现 LRU 的  
整体的设计思路是，可以使用 HashMap 存储 key，这样可以做到 save 和 get key的时间都是 O(1)，而 HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点，如图所示。**

LRU 存储是基于双向链表实现的，下面的图演示了它的原理。其中 h 代表双向链表的表头，t 代表尾部。首先预先设置 LRU 的容量，如果存储满了，可以通过 O(1) 的时间淘汰掉双向链表的尾部，每次新增和访问数据，都可以通过 O(1)的效率把新的节点增加到对头，或者把已经存在的节点移动到队头。

下面展示了，预设大小是 3 的，LRU存储的在存储和访问过程中的变化。为了简化图复杂度，图中没有展示 HashMap部分的变化，仅仅演示了上图 LRU 双向链表的变化。我们对这个LRU缓存的操作序列如下：

save("key1", 7)， save("key2", 0)， save("key3", 1)， save("key4", 2)， get("key2")， save("key5", 3)， get("key2")， save("key6", 4)

相应的 LRU 双向链表部分变化如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMDIxODQ_size_16_color_FFFFFF_t_70][]

核心操作的步骤:

**【1】save(key, value)，首先在 HashMap 找到 Key 对应的节点，如果节点存在，更新节点的值，并把这个节点移动队头。如果不存在，需要构造新的节点，并且尝试把节点塞到队头，如果LRU空间不足，则通过 tail 淘汰掉队尾的节点，同时在 HashMap 中移除 Key。  
【2】get(key)，通过 HashMap 找到 LRU 链表节点，把节点插入到队头，返回缓存的值。**  
完整基于 Java 的代码参考如下：

方法1自定义双链表：

class DLinkedNode {
    	String key;
    	int value;
    	DLinkedNode pre;
    	DLinkedNode post;
    }
    
    public class LRUCache {
       
        private Hashtable<String, DLinkedNode>
                cache = new Hashtable<String, DLinkedNode>();
        private int count;
        private int capacity;
        private DLinkedNode head, tail;
     
        public LRUCache(int capacity) {
            this.count = 0;
            this.capacity = capacity;
     
            head = new DLinkedNode();
            head.pre = null;
     
            tail = new DLinkedNode();
            tail.post = null;
     
            head.post = tail;
            tail.pre = head;
        }
     
        public int get(String key) {
     
            DLinkedNode node = cache.get(key);
            if(node == null){
                return -1; // should raise exception here.
            }
     
            // move the accessed node to the head;
            this.moveToHead(node);
     
            return node.value;
        }
     
     
        public void set(String key, int value) {
            DLinkedNode node = cache.get(key);
     
            if(node == null){
     
                DLinkedNode newNode = new DLinkedNode();
                newNode.key = key;
                newNode.value = value;
     
                this.cache.put(key, newNode);
                this.addNode(newNode);
     
                ++count;
     
                if(count > capacity){
                    // pop the tail
                    DLinkedNode tail = this.popTail();
                    this.cache.remove(tail.key);
                    --count;
                }
            }else{
                // update the value.
                node.value = value;
                this.moveToHead(node);
            }
        }
        /**
         * Always add the new node right after head;
         */
        private void addNode(DLinkedNode node){
            node.pre = head;
            node.post = head.post;
     
            head.post.pre = node;
            head.post = node;
        }
     
        /**
         * Remove an existing node from the linked list.
         */
        private void removeNode(DLinkedNode node){
            DLinkedNode pre = node.pre;
            DLinkedNode post = node.post;
     
            pre.post = post;
            post.pre = pre;
        }
     
        /**
         * Move certain node in between to the head.
         */
        private void moveToHead(DLinkedNode node){
            this.removeNode(node);
            this.addNode(node);
        }
     
        // pop the current tail.
        private DLinkedNode popTail(){
            DLinkedNode res = tail.pre;
            this.removeNode(res);
            return res;
        }
    }

转自 [https://www.pianshen.com/article/2754325537/][https_www.pianshen.com_article_2754325537]

方法2使用Java自带的双链表：

import java.util.HashMap;
    import java.util.LinkedList;
    import java.util.Map;
    import java.util.Objects;
     
    
    /**
     * @description: lru算法，线程安全
     * 使用jdk的双向链表
     * get元素时，如果不存在则返回null，反之，删除链表的该节点，把该节点放到表头
     * put元素时，
     *  如果没满，
     *    如果map中不存在，则插入表头，同时存入map
     *    如果map中存在，删除链表的该节点，把该节点放到表头；同时更新map中的值
     *  如果已满，
     *    如果map中不存在，则先删除表尾节点，再把新节点插入表头，同时存入map
     *    如果map中存在，则先删除表尾节点，再把新节点插入表头，同时更新map中的值
     */
      class Node<K,V>{
            /**
             * 键
             */
            K key;
     
            /**
             * 值
             */
            V value;
     
            public Node(K key, V value) {
                this.key = key;
                this.value = value;
            }
     
            @Override
            public String toString() {
                return "(" +
                        "key=" + key +
                        ", value=" + value +
                        ')';
            }
       }
    
    
     class LruCache<K,V> {
     
     
        /**
         * 通过与链表配合，使其查找速度在O(1)下完成
         */
        private Map<K,Node<K,V>> map;
     
        /**
         * 链表优点：便于添加和删除元素，都在O(1)时间内完成
         */
        private LinkedList<Node<K,V>> linkedList;
     
        /**
         * 缓存存储元素的数量
         */
        private int size;
     
        private  int defaultSize = 16;
     
        public LruCache() {
            this(16);
        }
     
        public LruCache(int size) {
            if(size <= 0){
                this.size = 16;
            }else {
                this.size = size;
            }
            this.map = new HashMap<>(this.size);
            this.linkedList = new LinkedList<>();
        }
     
        /**
         * 判断缓存元素是否存在，如果存在，则把链表中的元素删除，map中的数据不用删除，再在链表头部插入元素，并更新map
         * 当缓存没有满的话，直接把元素插入链表的表头，否则移除表尾元素（最旧未访问元素）,在插入表头，注意更新map
         *
         * @param key : 键
         * @param value ：值
         */
        public synchronized void put(K key,V value){
            //待添加元素
            Node<K,V> insertNode = new Node<>(key, value);
            //判断元素是否存在
            Node<K,V> node = map.get(key);
            //如果存在，则把链表中的元素删除，map中的数据不用删除，再在链表头部插入元素
            if(Objects.nonNull(node)){
                linkedList.remove(node);
                linkedList.addFirst(insertNode);
                //更新map中的相应value
                map.put(key,insertNode);
                return;
            }
            //如果缓存已经满的话，则删除最后未访问元素
            if(this.size == map.size()){
                //直接删除队列尾部元素，同时更新map
                linkedList.removeLast();
                map.remove(key);
                //在队列头部插入元素，同时更新map
                linkedList.addFirst(insertNode);
                map.put(key,insertNode);
                return;
            }
            //如果缓存没满，则执行添加即可
            map.put(key,insertNode);
            linkedList.addFirst(insertNode);
        }
     
        /**
         * 如果key存在，则返回相应value值，否者返回null
         *
         * @param key ：键
         * @return ：值
         */
        public synchronized V get(K key){
            //先向map查询是否存在
            Node<K,V> node = map.get(key);
            if(Objects.isNull(node)){
                return null;
            }
            //如果存在，则先删除后添加到队列头
            linkedList.remove(node);
            linkedList.addFirst(node);
            return node.value;
        }
     
        @Override
        public String toString() {
            StringBuilder stringBuilder = new StringBuilder();
            for(Node<K,V> node : linkedList ){
                stringBuilder.append(node.toString()).append(",");
            }
            return stringBuilder.toString().substring(0,stringBuilder.length()-1);
        }
     
    }
    
    
     
    public class LruCacheTest {
     
        public static void main(String[] args){
            LruCache<String,String> lruCache = new LruCache<>(3);
            lruCache.put("one","one");
            lruCache.put("two","two");
            lruCache.put("three","three");
            System.out.println(lruCache.toString());
            lruCache.get("one");
            System.out.println(lruCache.toString());
            lruCache.put("four","four");
            System.out.println(lruCache.toString());
            lruCache.get("one");
            System.out.println(lruCache.toString());
            System.out.println(lruCache.get("five"));
            lruCache.put("four","five");
            System.out.println(lruCache.toString());
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTU5NjQx_size_16_color_FFFFFF_t_70][]

转自：[https://blog.csdn.net/qq\_39559641/article/details/112689253][https_blog.csdn.net_qq_39559641_article_details_112689253]

[3620e4abe48eaed95f8051b837510848.png]: /images/20210923/dd26f4470a484ec0ad34d242ea2c0a06.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMDIxODQ_size_16_color_FFFFFF_t_70]: /images/20210923/50a7477616704422afa2b8b9376096dd.png
[https_www.pianshen.com_article_2754325537]: https://www.pianshen.com/article/2754325537/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTU5NjQx_size_16_color_FFFFFF_t_70]: /images/20210923/cc836a91aa994ef381b12f2f9a47ef11.png
[https_blog.csdn.net_qq_39559641_article_details_112689253]: https://blog.csdn.net/qq_39559641/article/details/112689253