LRU算法,用于手撸的簡單版本

LRU全稱是Least Recently Used 最近最少使用.

設計原則：如果一個資料在最近一段時間沒有被通路到，那麼在将來它被通路的可能性也很小。那麼當限定的空間已存滿資料時，應當把最久沒有被通路到的資料淘汰。

常被用于記憶體淘汰機制,redis,memcached,ehcache,mongodb等等都有采用此算法.意思就是存放資料的緩存滿了,現在要根據一些條件删除掉一些資料,條件就是最近一段時間周期内的資料使用次數最少的一些會被篩選出來然後删掉.

先來一個簡單實作,感受一下

package com.cn.demo;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * 繼承的LinkedHashMap 繼承自 HashMap，是以它的底層仍然是基于拉鍊式散列結構。
 * 該結構由數組和連結清單+紅黑樹，在此基礎上LinkedHashMap 增加了一條雙向連結清單，
 * 保持周遊順序和插入順序一緻的問題
 * @param <k>
 * @param <v>
 */
public class LRUCache<k,v> extends LinkedHashMap<k,v> {

    private final int cache_size;//緩存大小

    /**
     * @param initialSize 初始數組長度
     * @param accessOrder false：基于插入順序(預設) true：基于通路順序
     */
    public LRUCache(int initialSize,boolean accessOrder){
        //loadFactor裝載因子預設值0.75F,表示數組的數組長度超過這個比例，數組就要擴容,
        //這個比例越大,存放的資料越多,空間使用率越高,但沖突的機會加大了.
        //反之,比例越小,存放的元素越少,沖突的機會減小,但空間浪費多了.
        //沖突的機會越大,查找的成本越高.反之,查找的成本越小.
        //是以,必須在 "出現沖突的機會"和"空間使用率"之間尋找平衡是以使用了折中的想法。
        //但是指定了初始數組長度這個裝載因子就沒作用了哦
        super(initialSize,0.75F,accessOrder);
        this.cache_size=initialSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<k, v> eldest) {
        //意思就是當這個傳遞進來的map中的資料量大于指定的緩存資料的數量,就自動删除最老的資料.
        if(size()>cache_size){
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        //accessOrder true表示按照通路順序進行排序,
        //使用LinkedHashMap的get和put方法會執行它的afterNodeAccess方法,将節點移動到最後
        LRUCache lruCache=new LRUCache<String,Object>(6,true);
        lruCache.put("1","一");
        lruCache.put("2","二");
        lruCache.put("3","三");
        lruCache.put("4","四");
        lruCache.put("5","五");
        lruCache.put("6","六");

        for (Object item:lruCache.keySet()) {
            System.out.printf(item.toString());//123456
        }
        lruCache.get("1");

        System.out.println("");
        for (Object item:lruCache.keySet()) {
            System.out.print(item.toString());//234561
        }

        System.out.println("");
        lruCache.put("7","七");
        for (Object item:lruCache.keySet()) {
            System.out.print(item.toString());//345617
        }
        //觀察上述列印的注釋,代入場景,初始化緩存的時候給的記憶體大小是6,可以存放6條資料,
        //當一條資料被通路過後,它就不是最老和使用次數最少的資料了,是以被移動到了底部.
        //當新插入一條資料的時候,也會被放入底部,因為是新資料.
        //但這個時候要注意,第三次列印的時候元素2不在了,原因是記憶體隻容許放6條資料,
        //超出的部分要被删除掉,那麼就隻能删除早早被寫入但又沒人使用的資料,
        
    }
}
           

這邊debug帶大家看一下  lruCache.put("7","七"); 這一行put添加的代碼是怎麼執行完後就把"最少使用的"資料删除掉了

HashMap類裡的put方法,在結尾有個方法叫 afterNodeInsertion ,意思就是插入新節點但是可能删除最大節點,

隻要符合條件就會删除,前面咱們重寫的removeEldestEntry裡面的邏輯就是用來判斷是否需要進行删除

進到方法裡判斷時候會發現目前map的size大于指定的數量,是以傳回true,最後會執行removeNode方法把first裡的節點元素删除掉

ps:想了解LinkedHashMap更底層的實作,請看隔壁文章.