概述

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

分析

什么是LRU?

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

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

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

場(chǎng)景：我們需要設(shè)計(jì)一個(gè)緩存最多只能存儲(chǔ)10個(gè)元素，當(dāng)元素個(gè)數(shù)超過(guò)10的時(shí)候，刪除（淘汰）那些最近最少使用的數(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)鍵值對(duì)個(gè)數(shù)超過(guò)最大容量時(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}

因?yàn)樽隽艘淮?code>cache.get("1")，相當(dāng)于操作了1這個(gè)元素，變"新"了，所以只能淘汰3， 4。

總結(jié)

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

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

最新評(píng)論