欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LRU缓存淘汰策略实现

程序员文章站 2022-07-15 17:07:07
...

一般来说,对于经常被访问的数据,希望可以快速的返回给访问者,采用内存进行缓存就是很好的方式,直接访问内存中已缓存的数据可以被更快的被访问到,分布式中常用的缓存Ehcache,Redis等等;下面介绍几种缓存中常用的缓存淘汰策略:

  • FIFO:First In First Out,先进先出:判断存储时间,排队伍尾部(长时间未用)的先被淘汰;
  • LFU: Least Frequently Used,最近最少使用,被使用次数最少的缓存先被淘汰;
  • LRU:Least Recently Used,最近最少被使用的,就是淘汰长时间未用的数据,一般用过的数据会进行更新到前排,认为是常用的数据;
  • LRU缓存机制的实现,采用的是HashMap+DoubleLinkedList,采用Map是其查找数据的O(1)复杂度,而更新删除和插入数据采用双向链表可以快速进行定位操作,使用 key 和 value 作为双向链表的节点,在双向链表的头部添加该节点,并将 key 和该节点添加进哈希表中,我们首先使用哈希表进行定位,找出缓存项在双向链表中的位置,随后将其移动到双向链表的头部,即可在 O(1) 的时间内完成 get 或者 put 操作,具体的方法如下:
  • 哈希表即为普通的哈希映射(HashMap),通过缓存数据的键映射到其在双向链表中的位置。
  • 双向链表按照被使用的顺序存储了这些键值对,靠近头部的键值对是最近使用的,而靠近尾部的键值对是最久未使用的。LRU缓存淘汰策略实现
  • 对于 get 操作,首先判断 key 是否存在:
    1.若 key 不存在,则返回−1;
    2.若 key 存在,则 key 对应的节点是最近被使用的节点,通过哈希表定位到该节点在双 向链表中的位置,并将其移动到双向链表的头部,最后返回该节点的值。
  • 对于 put 操作,首先判断 key 是否存在:
    1.若 key 不存在,使用 key 和 value 创建一个新的节点,在双向链表的头部添加该节点,并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量,如果超出容量,则删除双向链表的尾部节点,并删除哈希表中对应的项;
    2.若 key 存在,则与 get 操作类似,先通过哈希表定位,再将对应的节点的值更新为 value,并将该节点移到双向链表的头部。
  • 上述各项操作中,访问哈希表的时间复杂度为 O(1),在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 O(1)。
  • 需要注意的是,在创建双向链表时设置了一个头结点first和一个尾结点last作为哨兵节点,为了更好地进行更新等操作,first后面指向的就是第一个节点,last前面指向的就是最后一个节点,这样在插入和删除时便可以写出逻辑,一般插入在第一个节点前面插入,而删除最后一个节点即可。
  • 使用双向链表+HashMap实现O(1)复杂度如下:
					package Threadtest;
					import java.util.HashMap;
					import java.util.Map;
					/**
					 * @Description:
					 * @Author:sds
					 * @Create 缓存过期策略LRU的实现,将HashMap的value作为双向链表的node进行存储,node.val;
					 * #@Version:1.0
					 */
					public class LRUCache {
					
					    // 双向链表结点,注意key也要存放,删除最不常用值时要用到key,使用key删除map中的记录
					    class Node{
					        int val;
					        int key;
					        Node prev;
					        Node next;
					
					        Node(int key, int val){
					            this.key = key;
					            this.val = val;
					        }
					        private void remove(Node node){
					            node.next.prev = node.prev;
					            node.prev.next = node.next;
					        }
					
					        private void addFirst(Node node){
					            node.next = first.next;
					            node.prev = first;
					            first.next.prev = node;
					            first.next = node;
					        }
					        private void moveToFirst(Node node){
					            remove(node);
					            addFirst(node);
					        }
					    }
					
					    // 缓存容量
					    int capacity;
					    // 当前缓存数量
					    int size;
					    // 两个哑结点,分别指向双向链表的头和尾结点
					    Node first;
					    Node last;
					    // 以关键字为key,结点为value
					    Map<Integer, Node> map;
					
					    // 初始化一系列参数
					    public LRUCache(int capacity) {
					        this.capacity = capacity;
					        size = 0;
					        first = new Node(0, 0);
					        last = new Node(0, 0);
					        // 构成初始的双向链表
					        first.next = last;
					        last.prev = first;
					        map = new HashMap<>();
					    }
					
					    // 如果当前链表中包含key缓存,从map中取出对应的结点,并把该结点移动到链表头
					    public int get(int key) {
					        if(map.containsKey(key)){
					            Node node = map.get(key);
					            moveToFirst(node);
					            return node.val;
					        }
					        return -1;
					    }
					
					    public void put(int key, int value) {
					        // 如果缓存存在,修改key对应的结点中的val值,并把该结点移动到链表头
					        if(map.containsKey(key)){
					            Node node = map.get(key);
					            node.val = value;
					            moveToFirst(node);
					        }else{
					            // 如果不存在,判断当前缓存数量是否超出容量,如果超出,先删除掉map中的记录
					            // 然后在删除处于链表尾部的结点
					            if(size >= capacity){
					                Node node = last.prev;
					                map.remove(node.key);
					                size--;
					                remove(node);
					            }
					            // 如果没超出缓存容量,创建一个新结点放到链表头
					            Node node = new Node(key, value);
					            map.put(key, node);
					            size++;
					            addFirst(node);
					        }
					    }
					
					    // 将结点node从双向链表中移除的方法
					    private void remove(Node node){
					        node.next.prev = node.prev;
					        node.prev.next = node.next;
					    }
					
					    // 将结点node插入到双向链表头部的方法
					    private void addFirst(Node node){
					        node.next = first.next;
					        node.prev = first;
					        first.next.prev = node;
					        first.next = node;
					    }
					
					    // 将node从链表中移除并将其插入到头部的方法
					    private void moveToFirst(Node node){
					        remove(node);
					        addFirst(node);
					    }
					}
  • 使用LinkedList+HashMap实现O(n)复杂度:
  • 使用HashMap可以通过O(1)时间拿到元素,但是无法在O(1)时间定位它在链表中的位置,在LinkedList里访问元素仍然是顺序遍历,所以删除元素的时间复杂度仍然是O(n),代码如下:
	                	package Threadtest;
						import java.util.HashMap;
						import java.util.Map;
						/**
						 * @Description:
						 * @Author:sds
						 * @Create 缓存过期策略LRU的实现,将HashMap的value作为双向链表的node进行存储,node.val;
						 * #@Version:1.0
						 */
						public class LRUCacheBeta<K, V> {
					    int capacity;
					    Map<K, V> map;
					    LinkedList<K> list;
					
					    public LRUCacheBeta(int capacity) {
					        this.capacity = capacity;
					        this.map = new HashMap<>();
					        this.list = new LinkedList<>();
					    }
					
					    /**
					     * 添加元素
					     * 1.元素存在,放到队尾
					     * 2.不存在,判断链表是否满。
					     * 如果满,则删除队首元素,放入队尾元素,删除更新哈希表
					     * 如果不满,放入队尾元素,更新哈希表
					     */
					    public void put(K key, V value) {
					        V v = map.get(key);
					        if (v != null) {
					            list.remove(key);
					            list.addLast(key);
					            map.put(key, value);
					            return;
					        }
					
					        //队列未满,添加到尾部
					        if (list.size() < capacity) {
					            list.addLast(key);
					            map.put(key, value);
					        } else {
					            //队列已满,移除队首
					            K firstKey = list.removeFirst();
					            map.remove(firstKey);
					            list.addLast(key);
					            map.put(key, value);
					        }
					    }
					
					    /**
					     * 访问元素
					     * 元素存在,放到队尾
					     */
					    public V get(K key) {
					        V v = map.get(key);
					        if (v != null) {
					            list.remove(key);
					            list.addLast(key);
					            return v;
					        }
					        return null;
					    }
					}