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

Java實(shí)現(xiàn)常用緩存淘汰算法:FIFO、LRU、LFU

 更新時(shí)間:2021年12月22日 09:43:07   作者:萬(wàn)貓學(xué)社  
在高并發(fā)、高性能的質(zhì)量要求不斷提高時(shí),我們首先會(huì)想到的就是利用緩存予以應(yīng)對(duì)。而常用的幾個(gè)緩存淘汰算法有:FIFO、LRU和LFU,本文將為大家詳細(xì)介紹一下這三個(gè)算法并用java實(shí)現(xiàn),感興趣的可以跟隨小編一起學(xué)習(xí)一下

緩存淘汰算法

在高并發(fā)、高性能的質(zhì)量要求不斷提高時(shí),我們首先會(huì)想到的就是利用緩存予以應(yīng)對(duì)。

第一次請(qǐng)求時(shí)把計(jì)算好的結(jié)果存放在緩存中,下次遇到同樣的請(qǐng)求時(shí),把之前保存在緩存中的數(shù)據(jù)直接拿來(lái)使用。

但是,緩存的空間一般都是有限,不可能把所有的結(jié)果全部保存下來(lái)。那么,當(dāng)緩存空間全部被占滿再有新的數(shù)據(jù)需要被保存,就要決定刪除原來(lái)的哪些數(shù)據(jù)。如何做這樣決定需要使用緩存淘汰算法。

常用的緩存淘汰算法有:FIFO、LRU、LFU,下面我們就逐一介紹一下。

FIFO

FIFO,F(xiàn)irst In First Out,先進(jìn)先出算法。判斷被存儲(chǔ)的時(shí)間,離目前最遠(yuǎn)的數(shù)據(jù)優(yōu)先被淘汰。簡(jiǎn)單地說(shuō),先存入緩存的數(shù)據(jù),先被淘汰。

最早存入緩存的數(shù)據(jù),其不再被使用的可能性比剛存入緩存的可能性大。建立一個(gè)FIFO隊(duì)列,記錄所有在緩存中的數(shù)據(jù)。當(dāng)一條數(shù)據(jù)被存入緩存時(shí),就把它插在隊(duì)尾上。需要被淘汰的數(shù)據(jù)一直在隊(duì)列頭。這種算法只是在按線性順序訪問(wèn)數(shù)據(jù)時(shí)才是理想的,否則效率不高。因?yàn)槟切┏1辉L問(wèn)的數(shù)據(jù),往往在緩存中也停留得最久,結(jié)果它們卻因變“老”而不得不被淘汰出去。

FIFO算法用隊(duì)列實(shí)現(xiàn)就可以了,這里就不做代碼實(shí)現(xiàn)了。

LRU

LRU,Least Recently Used,最近最少使用算法。判斷最近被使用的時(shí)間,目前最遠(yuǎn)的數(shù)據(jù)優(yōu)先被淘汰。簡(jiǎn)單地說(shuō),LRU 的淘汰規(guī)則是基于訪問(wèn)時(shí)間。

如果一個(gè)數(shù)據(jù)在最近一段時(shí)間沒(méi)有被使用到,那么可以認(rèn)為在將來(lái)它被使用的可能性也很小。因此,當(dāng)緩存空間滿時(shí),最久沒(méi)有使用的數(shù)據(jù)最先被淘汰。

在Java中,其實(shí)LinkedHashMap已經(jīng)實(shí)現(xiàn)了LRU緩存淘汰算法,需要在構(gòu)造函數(shù)第三個(gè)參數(shù)傳入true,表示按照時(shí)間順序訪問(wèn)??梢灾苯永^承LinkedHashMap來(lái)實(shí)現(xiàn)。

package one.more;

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

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

    /**
     * 容量限制
     */
    private int capacity;

    LruCache(int capacity) {
        // 初始大小,0.75是裝載因子,true是表示按照訪問(wèn)時(shí)間排序
        super(capacity, 0.75f, true);
        //緩存最大容量
        this.capacity = capacity;
    }

    /**
     * 重寫removeEldestEntry方法,如果緩存滿了,則把鏈表頭部第一個(gè)節(jié)點(diǎn)和對(duì)應(yīng)的數(shù)據(jù)刪除。
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

我寫一個(gè)簡(jiǎn)單的程序測(cè)試一下:

package one.more;

public class TestApp {

    public static void main(String[] args) {
        LruCache<String, String> cache = new LruCache(3);
        cache.put("keyA", "valueA");
        System.out.println("put keyA");
        System.out.println(cache);
        System.out.println("=========================");

        cache.put("keyB", "valueB");
        System.out.println("put keyB");
        System.out.println(cache);
        System.out.println("=========================");

        cache.put("keyC", "valueC");
        System.out.println("put keyC");
        System.out.println(cache);
        System.out.println("=========================");

        cache.get("keyA");
        System.out.println("get keyA");
        System.out.println(cache);
        System.out.println("=========================");

        cache.put("keyD", "valueD");
        System.out.println("put keyD");
        System.out.println(cache);
    }
}

運(yùn)行結(jié)果如下:

put keyA

{keyA=valueA}

=========================

put keyB

{keyA=valueA, keyB=valueB}

=========================

put keyC

{keyA=valueA, keyB=valueB, keyC=valueC}

=========================

get keyA

{keyB=valueB, keyC=valueC, keyA=valueA}

=========================

put keyD

{keyC=valueC, keyA=valueA, keyD=valueD}

當(dāng)然,這個(gè)不是面試官想要的,也不是我們想要的。我們可以使用雙向鏈表和哈希表進(jìn)行實(shí)現(xiàn),哈希表用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù),雙向鏈表用于數(shù)據(jù)被使用的時(shí)間先后順序。

在訪問(wèn)數(shù)據(jù)時(shí),如果數(shù)據(jù)已存在緩存中,則把該數(shù)據(jù)的對(duì)應(yīng)節(jié)點(diǎn)移到鏈表尾部。如此操作,在鏈表頭部的節(jié)點(diǎn)則是最近最少使用的數(shù)據(jù)。

當(dāng)需要添加新的數(shù)據(jù)到緩存時(shí),如果該數(shù)據(jù)已存在緩存中,則把該數(shù)據(jù)對(duì)應(yīng)的節(jié)點(diǎn)移到鏈表尾部;如果不存在,則新建一個(gè)對(duì)應(yīng)的節(jié)點(diǎn),放到鏈表尾部;如果緩存滿了,則把鏈表頭部第一個(gè)節(jié)點(diǎn)和對(duì)應(yīng)的數(shù)據(jù)刪除。

package one.more;

import java.util.HashMap;
import java.util.Map;

public class LruCache<K, V> {

    /**
     * 頭結(jié)點(diǎn)
     */
    private Node head;
    /**
     * 尾結(jié)點(diǎn)
     */
    private Node tail;
    /**
     * 容量限制
     */
    private int capacity;
    /**
     * key和數(shù)據(jù)的映射
     */
    private Map<K, Node> map;

    LruCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
    }

    public V put(K key, V value) {
        Node node = map.get(key);
        // 數(shù)據(jù)存在,將節(jié)點(diǎn)移動(dòng)到隊(duì)尾
        if (node != null) {
            V oldValue = node.value;
            //更新數(shù)據(jù)
            node.value = value;
            moveToTail(node);
            return oldValue;
        } else {
            Node newNode = new Node(key, value);
            // 數(shù)據(jù)不存在,判斷鏈表是否滿
            if (map.size() == capacity) {
                // 如果滿,則刪除隊(duì)首節(jié)點(diǎn),更新哈希表
                map.remove(removeHead().key);
            }
            // 放入隊(duì)尾節(jié)點(diǎn)
            addToTail(newNode);
            map.put(key, newNode);
            return null;
        }
    }

    public V get(K key) {
        Node node = map.get(key);
        if (node != null) {
            moveToTail(node);
            return node.value;
        }
        return null;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("LruCache{");
        Node curr = this.head;
        while (curr != null) {
            if(curr != this.head){
                sb.append(',').append(' ');
            }
            sb.append(curr.key);
            sb.append('=');
            sb.append(curr.value);
            curr = curr.next;
        }
        return sb.append('}').toString();
    }

    private void addToTail(Node newNode) {
        if (newNode == null) {
            return;
        }
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            //連接新節(jié)點(diǎn)
            tail.next = newNode;
            newNode.pre = tail;
            //更新尾節(jié)點(diǎn)指針為新節(jié)點(diǎn)
            tail = newNode;
        }
    }

    private void moveToTail(Node node) {
        if (tail == node) {
            return;
        }
        if (head == node) {
            head = node.next;
            head.pre = null;
        } else {
            //調(diào)整雙向鏈表指針
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        node.pre = tail;
        node.next = null;
        tail.next = node;
        tail = node;
    }

    private Node removeHead() {
        if (head == null) {
            return null;
        }
        Node res = head;
        if (head == tail) {
            head = null;
            tail = null;
        } else {
            head = res.next;
            head.pre = null;
            res.next = null;
        }
        return res;
    }

    class Node {
        K key;
        V value;
        Node pre;
        Node next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}

再次運(yùn)行測(cè)試程序,結(jié)果如下:

put keyA

LruCache{keyA=valueA}

=========================

put keyB

LruCache{keyA=valueA, keyB=valueB}

=========================

put keyC

LruCache{keyA=valueA, keyB=valueB, keyC=valueC}

=========================

get keyA

LruCache{keyB=valueB, keyC=valueC, keyA=valueA}

=========================

put keyD

LruCache{keyC=valueC, keyA=valueA, keyD=valueD}

LFU

LFU,Least Frequently Used,最不經(jīng)常使用算法,在一段時(shí)間內(nèi),數(shù)據(jù)被使用次數(shù)最少的,優(yōu)先被淘汰。簡(jiǎn)單地說(shuō),LFU 的淘汰規(guī)則是基于訪問(wèn)次數(shù)。

如果一個(gè)數(shù)據(jù)在最近一段時(shí)間很少被使用到,那么可以認(rèn)為在將來(lái)它被使用的可能性也很小。因此,當(dāng)空間滿時(shí),最小頻率使用的數(shù)據(jù)最先被淘汰。

我們可以使用雙哈希表進(jìn)行實(shí)現(xiàn),一個(gè)哈希表用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù),另一個(gè)哈希表用于存儲(chǔ)數(shù)據(jù)被使用次數(shù)和對(duì)應(yīng)的數(shù)據(jù)。

package one.more;

import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class LfuCache<K, V> {

    /**
     * 容量限制
     */
    private int capacity;

    /**
     * 當(dāng)前最小使用次數(shù)
     */
    private int minUsedCount;

    /**
     * key和數(shù)據(jù)的映射
     */
    private Map<K, Node> map;
    /**
     * 數(shù)據(jù)頻率和對(duì)應(yīng)數(shù)據(jù)組成的鏈表
     */
    private Map<Integer, List<Node>> usedCountMap;

    public LfuCache(int capacity) {
        this.capacity = capacity;
        this.minUsedCount = 1;
        this.map = new HashMap<>();
        this.usedCountMap = new HashMap<>();
    }

    public V get(K key) {

        Node node = map.get(key);
        if (node == null) {
            return null;
        }
        // 增加數(shù)據(jù)的訪問(wèn)頻率
        addUsedCount(node);
        return node.value;
    }

    public V put(K key, V value) {
        Node node = map.get(key);
        if (node != null) {
            // 如果存在則增加該數(shù)據(jù)的訪問(wèn)頻次
            V oldValue = node.value;
            node.value = value;
            addUsedCount(node);
            return oldValue;
        } else {
            // 數(shù)據(jù)不存在,判斷鏈表是否滿
            if (map.size() == capacity) {
                // 如果滿,則刪除隊(duì)首節(jié)點(diǎn),更新哈希表
                List<Node> list = usedCountMap.get(minUsedCount);
                Node delNode = list.get(0);
                list.remove(delNode);
                map.remove(delNode.key);
            }
            // 新增數(shù)據(jù)并放到數(shù)據(jù)頻率為1的數(shù)據(jù)鏈表中
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            List<Node> list = usedCountMap.get(1);
            if (list == null) {
                list = new LinkedList<>();
                usedCountMap.put(1, list);
            }

            list.add(newNode);
            minUsedCount = 1;
            return null;
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("LfuCache{");
        List<Integer> usedCountList = this.usedCountMap.keySet().stream().collect(Collectors.toList());
        usedCountList.sort(Comparator.comparingInt(i -> i));
        int count = 0;
        for (int usedCount : usedCountList) {
            List<Node> list = this.usedCountMap.get(usedCount);
            if (list == null) {
                continue;
            }
            for (Node node : list) {
                if (count > 0) {
                    sb.append(',').append(' ');
                }
                sb.append(node.key);
                sb.append('=');
                sb.append(node.value);
                sb.append("(UsedCount:");
                sb.append(node.usedCount);
                sb.append(')');
                count++;
            }
        }
        return sb.append('}').toString();
    }

    private void addUsedCount(Node node) {
        List<Node> oldList = usedCountMap.get(node.usedCount);
        oldList.remove(node);

        // 更新最小數(shù)據(jù)頻率
        if (minUsedCount == node.usedCount && oldList.isEmpty()) {
            minUsedCount++;
        }

        node.usedCount++;
        List<Node> set = usedCountMap.get(node.usedCount);
        if (set == null) {
            set = new LinkedList<>();
            usedCountMap.put(node.usedCount, set);
        }
        set.add(node);
    }

    class Node {

        K key;
        V value;
        int usedCount = 1;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}

再次運(yùn)行測(cè)試程序,結(jié)果如下:

put keyA

LfuCache{keyA=valueA(UsedCount:1)}

=========================

put keyB

LfuCache{keyA=valueA(UsedCount:1), keyB=valueB(UsedCount:1)}

=========================

put keyC

LfuCache{keyA=valueA(UsedCount:1), keyB=valueB(UsedCount:1), keyC=valueC(UsedCount:1)}

=========================

get keyA

LfuCache{keyB=valueB(UsedCount:1), keyC=valueC(UsedCount:1), keyA=valueA(UsedCount:2)}

=========================

put keyD

LfuCache{keyC=valueC(UsedCount:1), keyD=valueD(UsedCount:1), keyA=valueA(UsedCount:2)}

總結(jié)

看到這里,你已經(jīng)超越了大多數(shù)人!

FIFO,F(xiàn)irst In First Out,先進(jìn)先出算法。判斷被存儲(chǔ)的時(shí)間,離目前最遠(yuǎn)的數(shù)據(jù)優(yōu)先被淘汰,可以使用隊(duì)列實(shí)現(xiàn)。

LRU,Least Recently Used,最近最少使用算法。判斷最近被使用的時(shí)間,目前最遠(yuǎn)的數(shù)據(jù)優(yōu)先被淘汰,可以使用雙向鏈表和哈希表實(shí)現(xiàn)。

LFU,Least Frequently Used,最不經(jīng)常使用算法,在一段時(shí)間內(nèi),數(shù)據(jù)被使用次數(shù)最少的,優(yōu)先被淘汰,可以使用雙哈希表實(shí)現(xiàn)。

以上就是Java實(shí)現(xiàn)常用緩存淘汰算法:FIFO、LRU、LFU的詳細(xì)內(nèi)容,更多關(guān)于Java緩存淘汰算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • Java介紹多線程計(jì)算階乘實(shí)現(xiàn)方法

    Java介紹多線程計(jì)算階乘實(shí)現(xiàn)方法

    這篇文章主要為大家詳細(xì)介紹了Java多線程計(jì)算階乘的實(shí)現(xiàn),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-06-06
  • Java實(shí)現(xiàn)SSH模式加密

    Java實(shí)現(xiàn)SSH模式加密

    這篇文章主要介紹了Java實(shí)現(xiàn)SSH模式加密的相關(guān)資料,需要的朋友可以參考下
    2016-01-01
  • Java 實(shí)現(xiàn)簡(jiǎn)單靜態(tài)資源Web服務(wù)器的示例

    Java 實(shí)現(xiàn)簡(jiǎn)單靜態(tài)資源Web服務(wù)器的示例

    這篇文章主要介紹了Java 實(shí)現(xiàn)簡(jiǎn)單靜態(tài)資源Web服務(wù)器的示例,幫助大家更好的理解和使用Java,感興趣的朋友可以了解下
    2020-11-11
  • 深入了解Java SpringBoot自動(dòng)裝配原理

    深入了解Java SpringBoot自動(dòng)裝配原理

    在使用springboot時(shí),很多配置我們都沒(méi)有做,都是springboot在幫我們完成,這很大一部分歸功于springboot自動(dòng)裝配。本文將詳細(xì)為大家講解SpringBoot的自動(dòng)裝配原理,需要的可以參考一下
    2022-03-03
  • 解決ResourceBundle.getBundle文件路徑問(wèn)題

    解決ResourceBundle.getBundle文件路徑問(wèn)題

    這篇文章主要介紹了解決ResourceBundle.getBundle文件路徑問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2024-01-01
  • Java中byte、byte數(shù)組與int、long的轉(zhuǎn)換詳解

    Java中byte、byte數(shù)組與int、long的轉(zhuǎn)換詳解

    這篇文章分別給大家介紹了Java中byte和int之間的轉(zhuǎn)換、Java中 byte數(shù)組和int之間的轉(zhuǎn)換、Java中byte數(shù)組和long之間的轉(zhuǎn)換以及整理了整體工具類的源碼,需要的朋友可以參考借鑒,下面來(lái)一起看看吧。
    2017-02-02
  • java加密解密示例分享

    java加密解密示例分享

    想要?jiǎng)?chuàng)造一個(gè)只有自己能看懂的文件嗎?那就是對(duì)數(shù)據(jù)加密吧,下面分享一個(gè)java的數(shù)據(jù)加密與解密示例
    2014-01-01
  • ResultSet如何動(dòng)態(tài)獲取列名和值

    ResultSet如何動(dòng)態(tài)獲取列名和值

    這篇文章主要介紹了ResultSet如何動(dòng)態(tài)獲取列名和值問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-12-12
  • Spring Boot接口限流的常用算法及特點(diǎn)

    Spring Boot接口限流的常用算法及特點(diǎn)

    這篇文章主要給大家介紹了關(guān)于Spring Boot接口限流的常用算法及特點(diǎn)的相關(guān)資料,文中通過(guò)圖文介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2021-02-02
  • java中PriorityBlockingQueue的入隊(duì)知識(shí)點(diǎn)總結(jié)

    java中PriorityBlockingQueue的入隊(duì)知識(shí)點(diǎn)總結(jié)

    在本篇文章里小編給大家整理一篇關(guān)于java中PriorityBlockingQueue的入隊(duì)知識(shí)點(diǎn)總結(jié)內(nèi)容,有需要的朋友們可以學(xué)習(xí)下。
    2021-01-01

最新評(píng)論