快捷導(dǎo)航

基于LinkedHashMap實(shí)現(xiàn)LRU緩存

更新時間：2023年05月05日 11:57:45 作者：JAVA旭陽

LinkedHashMap是Java集合中一個常用的容器，它繼承了HashMap, 是一個有序的Hash表。那么該如何基于LinkedHashMap實(shí)現(xiàn)一個LRU緩存呢？本文將介紹LinkedHashMap的實(shí)現(xiàn)原理，感興趣的同學(xué)可以參考一下

概述

LinkedHashMap是Java集合中一個常用的容器，它繼承了HashMap, 是一個有序的Hash表。那么該如何基于LinkedHashMap實(shí)現(xiàn)一個LRU緩存呢？這也是面試經(jīng)常被問到的題目，主要是考察你對Java集合容器的了解程度以及LinkedHashMap的實(shí)現(xiàn)原理。

分析

什么是LRU?

LRU（Least Recently Used）指的是最近最少使用，是一種緩存淘汰算法，淘汰掉那個最少使用的的數(shù)據(jù)。

LinkedHashMap是有序的，它默認(rèn)通過雙向鏈表維護(hù)元素的插入順序，同時，通過構(gòu)造函數(shù)設(shè)置accessOrder屬性為true的情況，維護(hù)元素的訪問順序，這里的訪問包括插入、修改、查詢等元素，每次操作都會記錄順序，所以LRU緩存其實(shí)是包括訪問的，所以我們需要通過構(gòu)造函數(shù)設(shè)置LinkedHashMap設(shè)置accessOrder為true。
已經(jīng)解決了順序的問題，也就是最近訪問的會在雙向鏈表的尾部，最老的數(shù)據(jù)會在頭部。那么如何刪除頭部的元素呢？其實(shí)LinkedHashMap也提供了一個回調(diào)函數(shù)removeEldestEntry，它也會在添加元素的時候調(diào)用，默認(rèn)返回false，我們可以通過重寫這個方法的邏輯，如果LinkedHashMap大于緩存指定數(shù)量，就進(jìn)行淘汰。

LRU緩存實(shí)現(xiàn)

場景：我們需要設(shè)計一個緩存最多只能存儲10個元素，當(dāng)元素個數(shù)超過10的時候，刪除（淘汰）那些最近最少使用的數(shù)據(jù)，僅保存熱點(diǎn)數(shù)據(jù)。

public class LRUCache<K, V> extends LinkedHashMap<K, V> {

    /**
     * 緩存允許的最大容量
     */
    private final int maxSize;

    public LRUCache(int initialCapacity, int maxSize) {
        // accessOrder必須為true
        super(initialCapacity, 0.75f, true);
        this.maxSize = maxSize;
    }

    // 重寫
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // 當(dāng)鍵值對個數(shù)超過最大容量時，返回true，觸發(fā)刪除操作
        return size() > maxSize;
    }

    public static void main(String[] args) {
        LRUCache<String, String> cache = new LRUCache<>(5, 5);
        cache.put("1", "1");
        cache.put("2", "2");
        cache.put("3", "3");
        cache.put("4", "4");
        // 做一次查詢
        cache.get("1");
        cache.put("5", "5");
        cache.put("6", "6");
        cache.put("7", "7");
        System.out.println(cache);
    }

}

運(yùn)行結(jié)果：

{4=4, 1=1, 5=5, 6=6, 7=7}

因為做了一次cache.get("1")，相當(dāng)于操作了1這個元素，變"新"了，所以只能淘汰3， 4。

總結(jié)

通過本文想必大家對LinkedHashMap有了更深的了解，可以用它來實(shí)現(xiàn)一個LRU緩存，實(shí)際上，通過LinkedHashMap實(shí)現(xiàn)LRU還是挺常見的，比如logback框架的LRUMessageCache。

到此這篇關(guān)于基于LinkedHashMap實(shí)現(xiàn)LRU緩存的文章就介紹到這了,更多相關(guān)LinkedHashMap實(shí)現(xiàn)LRU緩存內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: