Java 实现LRU 算法（缓存清除经典算法）

蔚落 2021-12-03 10:15 368阅读 0赞

**目录**

LinkedHashMap 源码解析

Java 实现LRU算法

--------------------

**LRU：Last Recent Used 最近最少使用 算法**。

是一种常见的缓存清除算法。被广泛应用在各种缓存中间件比如Redis 中。

比较常见的实现是LinkedHashMap

## LinkedHashMap 源码解析 ##

可以理解，它的主要特点是：

1.这是一个链表。

2.每次插入一个数据都放在最头部，之前的数据往里推，如果长度超过了最大值，就删除最尾部的数据。

3.每访问一个数据，就移到最头部。

![20190719211505902.jpg][]

LinkedHashMap 中每一个Entry 都是继承自HashMap 的Node

static class Entry<K,V> extends HashMap.Node<K,V> {
            Entry<K,V> before, after;
            Entry(int hash, K key, V value, Node<K,V> next) {
                super(hash, key, value, next);
            }
        }

Entry 都有对前一个对象和后一个对象的引用，保存当前的key 和 value。

/**
         * The head (eldest) of the doubly linked list.
         */
        transient LinkedHashMap.Entry<K,V> head;
    
        /**
         * The tail (youngest) of the doubly linked list.
         */
        transient LinkedHashMap.Entry<K,V> tail;

定义了头部和尾部

## Java 实现LRU算法 ##

/**
     * @ClassName LRUCache
     * @Description TODO
     * @Author xl
     * @Date 2019/7/19 20:15
     * @Version 1.0
     */
    public class LRUCache<K,V> {
    
        private int currentCacheSize;
        private int cacheCapacity;
        private HashMap<K,CacheNode> caches;
        private CacheNode header;
        private CacheNode tail;
    
        public LRUCache(int size){
            currentCacheSize = 0;
            this.cacheCapacity = size;
            caches = new HashMap<>(size);
        }
    
        public void put(K k,V v){
            CacheNode node = caches.get(k);
            if(node == null){
                if(caches.size() >= cacheCapacity){
                    caches.remove(tail.key);
                    removeLast();
                }
                node = new CacheNode();
                node.key = k;
            }
            node.value = v;
            moveToFirst(node);
            caches.put(k,node);
        }
    
        public Object get(K k){
            CacheNode node = caches.get(k);
            if(node == null){
                return null;
            }
            moveToFirst(node);
            return node.value;
        }
    
        public Object remove(K k) {
            CacheNode node = caches.get(k);
            if (node != null) {
                // 有可能它不是第一个
                if (node.pre != null) {
                    node.pre.next = node.next;
                }
                // 有可能它不是最后一个
                if (node.next != null){
                    node.next.pre = node.pre;
                }
    
                if(node == header){
                    header = node.next;
                }
                if(node == tail){
                    tail = node.pre;
                }
            }
            return caches.remove(k);
        }
    
        public void removeLast(){
            if(tail != null){
                tail = tail.pre;
                if(tail == null){
                    header = null;
                }else{
                    tail.next = null;
                }
            }
        }
    
        public void clear(){
            tail = null;
            header = null;
            caches.clear();
        }
    
        public void moveToFirst(CacheNode node){
            if(header == node){
                return ;
            }
    
            if(node.next != null){
                node.next.pre = node.pre;
            }
    
            if(node.pre!=null){
                node.pre.next = node.next;
            }
    
            if(node == tail){
                tail = node.pre;
            }
    
            if(tail == null || header == null){
                tail = header = node;
                return ;
            }
    
            node.next = header;
            header.pre = node;
            header = node;
            header.pre = null;
        }
    
        class CacheNode{
            CacheNode pre;
            CacheNode next;
            Object key;
            Object value;
    
            public CacheNode(){
    
            }
        }
    
        @Override
        public String toString(){
            StringBuilder sb = new StringBuilder();
            CacheNode node = header;
            while (node != null) {
                sb.append(String.format("%s%s",node.key,node.value));
                node = node.next;
            }
            return sb.toString();
        }
    
        public static void main(String[] args) {
            LRUCache<Integer,String> lru = new LRUCache<>(3);
            lru.put(1,"a");
            System.out.println("lru : "+lru.toString());
    
            lru.put(2,"b");
            System.out.println("lru : "+lru.toString());
    
            lru.put(3,"c");
            System.out.println("lru : "+lru.toString());
    
            lru.put(4,"d");
            System.out.println("lru : "+lru.toString());
    
            lru.put(1,"aa");
            System.out.println("lru : "+lru.toString());
    
            lru.put(2,"bb");
            System.out.println("lru : "+lru.toString());
    
            lru.get(4);
            System.out.println("lru : "+lru.toString());
    
            lru.remove(2);
            System.out.println("lru : "+lru.toString());
        }
    
    
    }

**参考：**

[缓存淘汰算法--LRU算法(java代码实现)][--LRU_java]

[20190719211505902.jpg]: /images/20211203/3a633a6e0e7f4bb9959bc260532fc735.png
[--LRU_java]: https://blog.csdn.net/wangxilong1991/article/details/70172302