java實(shí)現(xiàn)LRU緩存淘汰算法的方法

更新時(shí)間：2021年11月04日 10:03:25 作者：西涼的悲傷

LRU（Least recently used，最近最少使用）算法根據(jù)數(shù)據(jù)的歷史訪問記錄來進(jìn)行淘汰數(shù)據(jù)，其核心思想是“如果數(shù)據(jù)最近被訪問過，那么將來被訪問的幾率也更高”。下面看下java實(shí)現(xiàn)LRU緩存淘汰算法的方法，一起看看吧

LRU算法：最近最少使用淘汰算法（Least Recently Used）。LRU是淘汰最長(zhǎng)時(shí)間沒有被使用的緩存（即使該緩存被訪問的次數(shù)最多）。

如何實(shí)現(xiàn)LRU緩存淘汰算法
場(chǎng)景：

我們現(xiàn)在有這么個(gè)真實(shí)場(chǎng)景，我在爬取某個(gè)網(wǎng)站時(shí)，控制該網(wǎng)站的代理IP并發(fā)數(shù)，太多會(huì)搞垮對(duì)方網(wǎng)站的對(duì)吧，要蹲號(hào)子的呢。這里我需要維護(hù)一個(gè)代理IP代理池，而且這些IP肯定不是一直都很穩(wěn)定的，但是又不能取一個(gè)就丟一個(gè)，這樣太浪費(fèi)資源。所以我會(huì)將這些IP緩存起來，進(jìn)行按需提取，采用LRU最近最少使用的策略去管理代理IP。

代碼如下：

import java.util.*;

public class LRUCache {

    int cap;//最大緩存的數(shù)量
    Map<String, String> values;//緩存
    Set<String> position;//緩存的key,按照存入的順序存儲(chǔ)

    public LRUCache(int cap) {
        this.cap = cap;
        values = new HashMap<>(cap);
        position = new LinkedHashSet<>(cap);
    }

    /**
     * 從緩存中獲取值，緩存中沒有則返回null
     */
    public String get(String key) {
        String value = null;
        if (values.containsKey(key)) {
            value = values.get(key);
            position.remove(key);
            position.add(key);
        }
        return value;
    }

    /**
     * 將值放入緩存中
     */
    public void put(String key, String value) {
        if (position.size() == cap) {
            //若達(dá)到緩存上限則將距今最久的緩存刪除
            String firstKey = position.iterator().next();
            position.remove(firstKey);
            values.remove(firstKey);
        }
        position.add(key);
        values.put(key, value);
    }

    public Map<String, String> getValues() {
        return values;
    }

    public Set<String> getPosition() {
        return position;
    }
}

測(cè)試：

        LRUCache lruCache = new LRUCache(4);
        lruCache.put("a","a");
        lruCache.put("b","b");
        lruCache.put("c","c");
        lruCache.put("d","d");
        System.out.println("position:"+lruCache.getPosition());
        System.out.println("values:"+lruCache.getValues());

        //a將被淘汰
        lruCache.put("e","e");
        System.out.println("position:"+lruCache.getPosition());
        System.out.println("values:"+lruCache.getValues());

輸出：