缓存淘汰算法LRU及JAVA实现

  • Post author:
  • Post category:java


一、基本概念

命中:访问缓存是通过key get到对应value

回源: miss了,未命中导致回读源数据

淘汰:缓存满了,那么就会按照某一种策略,把缓存中的旧对象踢出,而把新的对象加入缓存池。(只有5个存储单元,来了第6个元素。则考虑谁出队)

淘汰策略:即缓存算法,决定到底应该踢出哪些对象

缓存污染:不常用的数据加入进缓存,降低了缓存效率的现象

二、缓存淘汰算法LRU

LRU(Least recently used,最近最少使用)

原理:根据数据的历史访问记录,淘汰最近最少使用的元素

实现:链表,实现简单


1. 新数据插入到链表头部;


2. 每当缓存命中(即缓存数据被访问),则将数据移到链表头部;


3. 当链表满的时候,将链表尾部的数据丢弃。

package com.max.mybatis.LRU;

import java.util.HashMap;


public class LRUCache<K, V> {

    private int currentCacheSize;
    private int CacheCapcity;
    private HashMap<K,CacheNode> caches;
    private CacheNode first;
    private CacheNode last;

    public LRUCache(int size){
        currentCacheSize = 0;
        this.CacheCapcity = size;
        caches = new HashMap<K,CacheNode>(size);
    }

    /**
     * 插入元素 (超容量移除队尾元素,新元素插队头)
     * 1.put前先校验缓存size已达最大容量,则remove 队尾的key
     * 2.为超容量,则赋值node,并把node移动到队头
     * @param k
     * @param v
     */
    public void put(K k,V v){
        CacheNode node = caches.get(k);
        if(node == null){
            //1.put前先校验缓存size已达最大容量,则remove 队尾的key
            if(caches.size() >= CacheCapcity){
                caches.remove(last.key);
                removeLast();
            }
            node = new CacheNode();
            node.key = k;
        }
        node.value = v;
        //2.把node移动到队头
        moveToFirst(node);
        caches.put(k, node);
    }

    /**
     * 获取元素 命中后将该元素移至对头
     * @param k
     */
    public Object  get(K k){
        CacheNode node = caches.get(k);
        if(node == null){
            return null;
        }
        moveToFirst(node);
        return node.value;
    }

    /**
     * 获取元素 命中后将该元素移至对头
     * @param k
     */
    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 == first){
                first = node.next;
            }
            if(node == last){
                last = node.pre;
            }
        }

        return caches.remove(k);
    }

    public void clear(){
        first = null;
        last = null;
        caches.clear();
    }



    private void moveToFirst(CacheNode node){
        if(first == node){
            return;
        }
        if(node.next != null){
            node.next.pre = node.pre;
        }
        if(node.pre != null){
            node.pre.next = node.next;
        }
        if(node == last){
            last= last.pre;
        }
        if(first == null || last == null){
            first = last = node;
            return;
        }

        node.next=first;
        first.pre = node;
        first = node;
        first.pre=null;

    }

    private void removeLast(){
        if(last != null){
            last = last.pre;
            if(last == null){
                first = null;
            }else{
                last.next = null;
            }
        }
    }
    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        CacheNode node = first;
        while(node != null){
            sb.append(String.format("%s:%s ", node.key,node.value));
            node = node.next;
        }

        return sb.toString();
    }

    class CacheNode{
        CacheNode pre;
        CacheNode next;
        Object key;
        Object value;
        public CacheNode(){

        }
    }

    public static void main(String[] args) {
        LRUCache<Integer,String> lru = new LRUCache<Integer,String>(3);
        lru.put(1, "a");    // 1:a
        System.out.println(lru.toString());
        lru.put(2, "b");    // 2:b 1:a 
        lru.put(3, "c");    // 3:c 2:b 1:a 
        lru.put(4, "d");    // 4:d 3:c 2:b  
        lru.put(1, "aa");   // 1:aa 4:d 3:c  
        lru.get(1);         // 1:aa 5:e 2:bb
        lru.remove(12);     // 1:aa 5:e 2:bb
        lru.remove(1);      //5:e 2:bb
    }

}

适用场景:当存在热点数据时,LRU的效率很好,

缺点:

1.命中时将命中元素移到头部,需要遍历链表,找到命中的数据块索引,然后需要将数据移到头部。O(n)

2.非热点数据,偶发性的、周期性的批量操作会导致LRU命中率急剧下降,造成缓存污染。

优化实现

双向链表+哈希表:

1、采用双向链表来实现元素(k-v键值对)的存储

2、同时采用hash表来存储相关的key与value的对应关系。

这样,我们既能在O(1)的时间对key进行操作,同时又能利用Double LinkedList的添加和删除节点的便利性。(get/set都能在O(1)内完成)。