快捷導(dǎo)航

JavaScript如何實(shí)現(xiàn)LRU緩存淘汰算法

更新時(shí)間：2023年04月26日 10:46:31 作者：雷哥不愛(ài)寫(xiě)代碼

LRU（Least Recently Used）緩存淘汰算法是一種常見(jiàn)的緩存淘汰策略，它的核心思想是優(yōu)先淘汰最近最少使用的緩存數(shù)據(jù)，以保證緩存中的數(shù)據(jù)始終是最熱門(mén)的。本文主要介紹了一些關(guān)于如何實(shí)現(xiàn)LRU緩存淘汰算法的方法，感興趣的小伙伴可以參考一下

如何實(shí)現(xiàn)LRU緩存淘汰算法?

LRU（Least Recently Used）緩存淘汰算法是一種常見(jiàn)的緩存淘汰策略，它的核心思想是優(yōu)先淘汰最近最少使用的緩存數(shù)據(jù)，以保證緩存中的數(shù)據(jù)始終是最熱門(mén)的。下面是一些關(guān)于如何實(shí)現(xiàn)LRU緩存淘汰算法的方法：

使用哈希表和雙向鏈表

LRU緩存淘汰算法的核心在于如何快速定位最近最少使用的緩存數(shù)據(jù)，這可以通過(guò)哈希表和雙向鏈表的結(jié)合來(lái)實(shí)現(xiàn)。具體來(lái)說(shuō)，我們可以使用一個(gè)哈希表來(lái)存儲(chǔ)緩存數(shù)據(jù)的鍵值對(duì)，同時(shí)使用一個(gè)雙向鏈表來(lái)維護(hù)緩存數(shù)據(jù)的訪問(wèn)順序，每次訪問(wèn)緩存時(shí)，我們將訪問(wèn)的數(shù)據(jù)節(jié)點(diǎn)移動(dòng)到鏈表頭，當(dāng)緩存滿(mǎn)時(shí)，淘汰鏈表尾部的節(jié)點(diǎn)即可。

哈希表實(shí)現(xiàn)LRU緩存淘汰算法

下面是一個(gè)使用哈希表實(shí)現(xiàn)LRU緩存淘汰算法的例子，假設(shè)我們要實(shí)現(xiàn)一個(gè)最大容量為3的緩存：

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

class LRUCache<K, V> {
    private int capacity;
    private Map<K, Node<K,V>> cache;
    private Node<K,V> head;
    private Node<K,V> tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new Node<>(null, null);
        this.tail = new Node<>(null, null);
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    public V get(K key) {
        if (!cache.containsKey(key)) {
            return null;
        }
        Node<K,V> node = cache.get(key);
        remove(node);
        addFirst(node);
        return node.value;
    }

    public void put(K key, V value) {
        if (cache.containsKey(key)) {
            Node<K,V> node = cache.get(key);
            node.value = value;
            remove(node);
            addFirst(node);
        } else {
            if (cache.size() == capacity) {
                Node<K,V> node = removeLast();
                cache.remove(node.key);
            }
            Node<K,V> node = new Node<>(key, value);
            cache.put(key, node);
            addFirst(node);
        }
    }

    private void remove(Node<K,V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addFirst(Node<K,V> node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    private Node<K,V> removeLast() {
        Node<K,V> node = tail.prev;
        remove(node);
        return node;
    }

    private static class Node<K, V> {
        K key;
        V value;
        Node<K,V> prev;
        Node<K,V> next;

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

在這個(gè)例子中，我們使用了一個(gè)哈希表cache來(lái)存儲(chǔ)緩存數(shù)據(jù)的鍵值對(duì)，同時(shí)使用了一個(gè)雙向鏈表來(lái)維護(hù)緩存數(shù)據(jù)的訪問(wèn)順序，其中head和tail分別表示鏈表頭和鏈表尾，每次訪問(wèn)緩存時(shí)，我們將訪問(wèn)的數(shù)據(jù)節(jié)點(diǎn)移動(dòng)到鏈表頭，當(dāng)緩存滿(mǎn)時(shí)，淘汰鏈表尾部的節(jié)點(diǎn)即可。

注意，為了方便起見(jiàn)，我們?cè)阪湵眍^和鏈表尾分別添加了一個(gè)哨兵節(jié)點(diǎn)head和tail，這樣就不需要在代碼中處理鏈表為空的情況了。

下面是一個(gè)使用雙向鏈表實(shí)現(xiàn)LRU緩存淘汰算法的例子，假設(shè)我們要實(shí)現(xiàn)一個(gè)最大容量為3的緩存：

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

class LRUCache<K, V> {
    private int capacity;
    private Map<K, Node<K,V>> cache;
    private Node<K,V> head;
    private Node<K,V> tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new Node<>(null, null);
        this.tail = new Node<>(null, null);
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    public V get(K key) {
        if (!cache.containsKey(key)) {
            return null;
        }
        Node<K,V> node = cache.get(key);
        remove(node);
        addFirst(node);
        return node.value;
    }

    public void put(K key, V value) {
        if (cache.containsKey(key)) {
            Node<K,V> node = cache.get(key);
            node.value = value;
            remove(node);
            addFirst(node);
        } else {
            if (cache.size() == capacity) {
                Node<K,V> node = removeLast();
                cache.remove(node.key);
            }
            Node<K,V> node = new Node<>(key, value);
            cache.put(key, node);
            addFirst(node);
        }
    }

    private void remove(Node<K,V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addFirst(Node<K,V> node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    private Node<K,V> removeLast() {
        Node<K,V> node = tail.prev;
        remove(node);
        return node;
    }

    private static class Node<K, V> {
        K key;
        V value;
        Node<K,V> prev;
        Node<K,V> next;

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

在這個(gè)例子中，我們使用了一個(gè)哈希表cache來(lái)存儲(chǔ)緩存數(shù)據(jù)的鍵值對(duì)，同時(shí)使用了一個(gè)雙向鏈表來(lái)維護(hù)緩存數(shù)據(jù)的訪問(wèn)順序，其中head和tail分別表示鏈表頭和鏈表尾，每次訪問(wèn)緩存時(shí)，我們將訪問(wèn)的數(shù)據(jù)節(jié)點(diǎn)移動(dòng)到鏈表頭，當(dāng)緩存滿(mǎn)時(shí)，淘汰鏈表尾部的節(jié)點(diǎn)即可。

注意，為了方便起見(jiàn)，我們?cè)阪湵眍^和鏈表尾分別添加了一個(gè)哨兵節(jié)點(diǎn)head和tail，這樣就不需要在代碼中處理鏈表為空的情況了。

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

您可能感興趣的文章: