java实现LRU、FIFO缓存

比眉伴天荒 2021-06-22 15:36 515阅读 0赞

**1、LRU缓存**

1）LRU缓存的思想：

*  固定缓存大小，需要给缓存分配一个固定的大小。
 *  每次读取缓存都会改变缓存的使用时间，将缓存的存在时间重新刷新。
 *  需要在缓存满了后，将最近最久未使用的缓存删除，再添加最新的缓存。

2）LRU缓存实现：

通过一个map和双向链表实现：

*  map：用来存储、检索缓存数据数据（效率高）
 *  双向链表：用来记录访问顺序（链表方便将一个元素快速移动到头、尾、删除）。

注：为了达到从map中的获取的缓存，能够快速映射到链表中，map的value类型就是链表的node。

假设规定：链表尾部是最新的数据，具体算法如下：

*  **put**：首先从map中获取数据，如果已存在则更新值，同时修改链表将元素move到尾部；如果不存在，判断是否超出阈值，没有超过，加到map中，同时修改链表将元素move到尾部，如果超过，先从map中删除链表头部元素，同时修改链表，将头元素删掉。
 *  **get**：从map中获取数据，如果不存在返回null，如果存在修改链表将元素移动到尾部。
 *  **remove**：从map中获取数据，如果不存在直接返回，如果存在从map、链表中都删除。

3）根据LinkedHashMap实现：

java中的LinkedHashMap实现了Map的接口，此外还维持了一个所有entries的双向链表用来记录entries的顺序。

*  可以通过构造参数accessOrder来指定访问entiry的顺序：true按照LRU顺序，false按照FIFO顺序（默认为false）；
 *  重载protected boolean removeEldestEntry(Map.Entry<K,V> eldest)方法，实现容量的限制；

public class LRUCache2<K, V> extends LinkedHashMap<K, V> {
        private final int MAX_CACHE_SIZE;
    
        public LRUCache2(int cacheSize) {
            super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
            MAX_CACHE_SIZE = cacheSize;
        }
    
        @Override
        protected boolean removeEldestEntry(Map.Entry eldest) {
            return size() > MAX_CACHE_SIZE;
        }
    
       
        public static void main(String[] args) {
    		
    		LRUCache2<Integer, Integer> lru2 = new LRUCache2<>(5);
            lru2.put(1, 1);
            System.out.println(lru2);
            lru2.put(2, 2);
            System.out.println(lru2);
            lru2.put(3, 3);
            System.out.println(lru2);
            lru2.get(1);
            System.out.println(lru2);
            lru2.put(4, 4);
            lru2.put(5, 5);
            lru2.put(6, 6);
            System.out.println(lru2);
    	}
    }

或者：（省去了单独建一个类的麻烦）

final int cacheSize = 100;
    Map<String, String> map = new LinkedHashMap<String, String>((int) Math.ceil(cacheSize / 0.75f) + 1, 0.75f, true) {
        @Override
        protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return size() > cacheSize;
        }
    };

4）手写一个LRU：

import java.util.HashMap;
    
    class Node<K,V> {
    	Node<K,V> pre;
    	Node<K,V> next;
    	K key;
    	V value;
    }
    public class LRUCache<K,V> {
    	//lru容量
    	private static int MAX_CACHE_SIZE;
    	//双向链表
    	private Node<K,V> head = null;
        private Node<K,V> tail = null;
        //map
        private HashMap<K, Node<K, V>> cache;
    	
        public LRUCache (int size) {
        	MAX_CACHE_SIZE = size;
        	cache = new HashMap<>();
        }
        
        public void put(K key,V value) {
        	Node<K, V> node = getNode(key);//从map中获取
        	if(node == null) {//不存在：判断容量
        		if (cache.size() >= MAX_CACHE_SIZE) {
        			//从map中删除
        			cache.remove(key);
        			//从链表中删除（删除最老的头部元素）
        			removeHead();
        		} 
        		//添加到map
        		node = new Node<K,V>();
        		node.key = key;
        		node.value = value;
        		cache.put(key, node);
        		//移动链表位置
        		move2tail(node);
        	} else {//存在：更新值&&移动链表位置
        		node.value = value;
        		move2tail(node);
        	}
        }
        
        public V get(K key) {
        	Node<K, V> node = getNode(key);//从map中获取
        	if (node == null) {//不存在
        		return null;
        	} else {//存在：修改链表位置
        		move2tail(node);
        		return node.value;
        	}
        }
        
        public void remove(K key) {
        	Node<K, V> node = getNode(key);//从map中获取
        	if (node == null) {
        		return;
        	}
        	//从map中删除
        	cache.remove(key);
        	//从链表中删除
        	removeNode(node);
        }
        //从map中检索元素
        private Node<K,V> getNode(K key) {
        	Node<K, V> node = cache.get(key);
        	return node;
        }
        //移动指定的node到尾部（最新位置）
        private void move2tail(Node<K,V> node) {
        	if (head == null || tail == null) {
                head = tail = node;
                return;
            }
        	if (node == tail) {
        		return;
        	}
        	//脱链
        	if (node.pre != null) {
        		node.pre.next = node.next;
            }
            if (node.next != null) {
            	node.next.pre = node.pre;
            }
            if (node == head) {
        		Node<K,V> next = node.next;
        		if (next != null) {
        			head.next = null;
        			head = next;
        			head.pre = null;
        		}
        	}
            //连到尾部
            node.pre = tail;
            tail.next = node;
            node.next = null;
            tail = node;
        }
        //删除链表头部node（最老的）
        private void removeHead() {
        	if (head != null) {
        		Node<K,V> next = head.next;
        		if (next == null) {
        			head = null;
        			tail = null;
        		} else {
        			head.next = null;
        			head = next;
        			head.pre = null;
        		}
        	}
        }
        //删除链表指定的node
        private void removeNode(Node<K,V> node) {
        	if (node == head) {
        		removeHead();
        	} else if (node == tail) {
        		Node<K,V> prev = tail.pre;
        		tail.next = null;
        		tail = prev;
        		tail.pre = null;
        	} else {
        		node.pre.next = node.next;
        		node.next.pre = node.pre;
        	}
        }
        @Override
        public String toString() {
            StringBuilder stringBuilder = new StringBuilder();
            Node<K, V> entry = tail;
            while (entry != null) {
                stringBuilder.append(String.format("%s:%s ", entry.key, entry.value));
                entry = entry.pre;
            }
            return stringBuilder.toString();
        }
    
    	public static void main(String[] args) {
    		
    		LRUCache<Integer, Integer> lru2 = new LRUCache<>(5);
            lru2.put(1, 1);
            System.out.println(lru2);
            lru2.put(2, 2);
            System.out.println(lru2);
            lru2.put(3, 3);
            System.out.println(lru2);
            lru2.get(1);
            System.out.println(lru2);
            lru2.put(4, 4);
            lru2.put(5, 5);
            lru2.put(6, 6);
            System.out.println(lru2);
    	}
    }

**2、FIFO缓存**

使用LinkedHashMap进行实现，第三个参数为false即可。

以上就是使用Java实现这两种缓存的方式，从中可以看出，LinkedHashMap实现缓存较为容易，因为底层函数对此已经有了支持，自己编写链表实现LRU缓存也是借鉴了LinkedHashMap中实现的思想。

**3、并发性**

上面通过LinkedHashMap、手动方式实现的LRU都是线程不安全的，如果要实现线程安全的LRU可以考虑以下方案：

*  加锁：在get、put、remove方法上加锁；
 *  使用ConcurrentLinkedHashMap：google提供，对concurrentHashMap的一个封装，提供了线程安全的LRU缓存；（现已经继承到guava中）
 *  使用guava提供的cache功能；

[https://www.cnblogs.com/lzrabbit/p/3734850.html][https_www.cnblogs.com_lzrabbit_p_3734850.html]

[https://www.cnblogs.com/liuyang0/p/6664586.html][https_www.cnblogs.com_liuyang0_p_6664586.html]

[https://juejin.im/post/5a4b433b6fb9a0451705916f][https_juejin.im_post_5a4b433b6fb9a0451705916f]

[https_www.cnblogs.com_lzrabbit_p_3734850.html]: https://www.cnblogs.com/lzrabbit/p/3734850.html
[https_www.cnblogs.com_liuyang0_p_6664586.html]: https://www.cnblogs.com/liuyang0/p/6664586.html
[https_juejin.im_post_5a4b433b6fb9a0451705916f]: https://juejin.im/post/5a4b433b6fb9a0451705916f