欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時(shí)間:2023年05月05日 11:57:45   作者:JAVA旭陽  
LinkedHashMap是Java集合中一個(gè)常用的容器,它繼承了HashMap, 是一個(gè)有序的Hash表。那么該如何基于LinkedHashMap實(shí)現(xiàn)一個(gè)LRU緩存呢?本文將介紹LinkedHashMap的實(shí)現(xiàn)原理,感興趣的同學(xué)可以參考一下

概述

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

分析

什么是LRU?

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

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

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

場(chǎng)景:我們需要設(shè)計(jì)一個(gè)緩存最多只能存儲(chǔ)10個(gè)元素,當(dāng)元素個(gè)數(shù)超過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ù)超過最大容量時(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é)

通過本文想必大家對(duì)LinkedHashMap有了更深的了解,可以用它來實(shí)現(xiàn)一個(gè)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)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

最新評(píng)論