LRUCache詳解-創(chuàng)新互聯(lián)

1.概念

創(chuàng)新互聯(lián)專注于孝義網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。熱誠為您提供孝義營銷型網(wǎng)站建設(shè)，孝義網(wǎng)站制作、孝義網(wǎng)頁設(shè)計(jì)、孝義網(wǎng)站官網(wǎng)定制、微信平臺(tái)小程序開發(fā)服務(wù)，打造孝義網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供孝義網(wǎng)站排名全網(wǎng)營銷落地服務(wù)。

LRU是Least Recently Used的縮寫，意思是最近最少使用，它是一種Cache替換算法。
Cache的容量有限，因此當(dāng)Cache的容量用完后，而又有新的內(nèi)容需要添加進(jìn)來時(shí)，就需要挑選并舍棄原有的部分內(nèi)容，從而騰出空間來放新內(nèi)容。LRU Cache 的替換原則就是將最近最少使用的內(nèi)容替換掉。其實(shí)，LRU譯成最久未使用會(huì)更形象，因?yàn)樵撍惴看翁鎿Q掉的就是一段時(shí)間內(nèi)最久沒有使用過的內(nèi)容。

2.LRUCache的實(shí)現(xiàn)原理

實(shí)現(xiàn)LRU Cache的方法和思路很多，但是要保持高效實(shí)現(xiàn)O(1)的put和get，那么使用雙向鏈表和哈希表的搭配是最高效和經(jīng)典的。
使用雙向鏈表是因?yàn)殡p向鏈表可以實(shí)現(xiàn)任意位置O(1)的插入和刪除，
使用哈希表是因?yàn)楣１淼脑鰟h查改也是O(1)。

package test;

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

class Node {
    public int key;
    public int val;

    public Node prev;

    public Node next;

    public Node() {

    }

    public Node(int key, int val) {
        this.key = key;
        this.val = val;
    }

    @Override
    public String toString() {
        return "Node{" +
                "key=" + key +
                ", val=" + val +
                '}';
    }
}

public class MyLRUCache {
    public Node head;
    public Node tail;

    public int usedsize;
    public Mapcache;
    public int capacity;

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

    //插入元素
    public void put(int key, int val) {
        Node node = cache.get(key);
        if (node == null) {
            Node newnode = new Node(key, val);
            cache.put(key, newnode);
            addToTail(newnode);
            usedsize++;
            //檢查當(dāng)前雙向鏈表的有效數(shù)據(jù)個(gè)數(shù) 是不是超過了capacity
            if (usedsize >capacity) {
                Node removeNode = removeHead();
                cache.remove(removeNode.key);
                usedsize--;
            }
            printNodes("put");
        } else {
            //更新val的值，其實(shí)沒必要
            node.val = val;
            moveTotail(node);
        }
    }

    //刪除指定節(jié)點(diǎn)
    public void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    //移動(dòng)當(dāng)前節(jié)點(diǎn)到尾巴節(jié)點(diǎn)
    public void moveTotail(Node node) {
        removeNode(node);
        addToTail(node);
    }

    //添加到尾巴節(jié)點(diǎn)
    public void addToTail(Node node) {
        tail.prev.next = node;
        node.prev = tail.prev;
        node.next = tail;
        tail.prev = node;
    }

    //刪除最近沒使用的頭結(jié)點(diǎn)
    public Node removeHead() {
        Node del = head.next;
        head.next = del.next;
        del.next.prev = head;
        return del;
    }

    //訪問當(dāng)前的key 把你訪問的節(jié)點(diǎn)放到尾巴
    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        //把最近使用的放到了尾巴
        moveTotail(node);
        printNodes("get");
        return node.val;
    }

    public void printNodes(String str) {
        System.out.println(str + " ");
        Node cur = head.next;
        while (cur != tail) {
            System.out.print(cur + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        MyLRUCache myLRUCache = new MyLRUCache(3);
        myLRUCache.put(100, 1);
        myLRUCache.put(200, 2);
        myLRUCache.put(300, 3);
        System.out.println("獲取元素");
        myLRUCache.get(200);
        myLRUCache.get(100);
        System.out.println("存放元素，會(huì)刪除頭結(jié)點(diǎn)，因?yàn)轭^節(jié)點(diǎn)是最近最少使用的");
        myLRUCache.put(999, 9);
    }
}

3.jdk當(dāng)中LRUCache被封裝到了LinkedHashMap

package test;


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

public class LRUCache extends LinkedHashMap{
    public int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    public Integer get(Object key) {
        return super.getOrDefault(key, -1);
    }

    @Override
    public Integer put(String key, Integer value) {
        return super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entryeldest) {
        return size() >capacity;
    }

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(3);
        lruCache.put("a", 1);
        lruCache.put("b", 2);
        lruCache.put("c", 3);
        System.out.println(lruCache);
        System.out.println("獲取元素");
        System.out.println(lruCache.get("b"));
        System.out.println(lruCache);
        System.out.println(lruCache.get("a"));
        System.out.println(lruCache);
        System.out.println("存放元素,會(huì)刪除頭結(jié)點(diǎn)，因?yàn)轭^結(jié)點(diǎn)是最近最少使用的");
        lruCache.put("d", 4);
        System.out.println(lruCache);
    }

    public static void main2(String[] args) {
        LinkedHashMaplinkedHashMap =
                new LinkedHashMap(16, 0.7f, true);
        linkedHashMap.put("a", 1);
        linkedHashMap.put("b", 2);
        linkedHashMap.put("c", 3);
        System.out.println(linkedHashMap);
        System.out.println("獲取元素");
        System.out.println(linkedHashMap.get("a"));
        System.out.println(linkedHashMap);
        System.out.println(linkedHashMap.get("b"));
        System.out.println(linkedHashMap);
        System.out.println(linkedHashMap.get("c"));
        System.out.println(linkedHashMap);//把常用的數(shù)據(jù)放到了尾巴 不常用的放在頭部便于刪除
    }

    public static void main1(String[] args) {
        LinkedHashMaplinkedHashMap =
                new LinkedHashMap(16, 0.7f, false);
        linkedHashMap.put("a", 1);
        linkedHashMap.put("b", 2);
        linkedHashMap.put("c", 3);
        System.out.println(linkedHashMap);
        System.out.println("獲取元素");
        System.out.println(linkedHashMap.get("a"));
        System.out.println(linkedHashMap);
    }
}

4.LRU緩存

class Node {
    public int key;
    public int val;

    public Node prev;

    public Node next;

    public Node() {

    }

    public Node(int key, int val) {
        this.key = key;
        this.val = val;
    }

    @Override
    public String toString() {
        return "Node{" +
                "key=" + key +
                ", val=" + val +
                '}';
    }
}

public class LRUCache {
    public Node head;
    public Node tail;

    public int usedsize;
    public Mapcache;
    public int capacity;

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

    //插入元素
    public void put(int key, int val) {
        Node node = cache.get(key);
        if (node == null) {
            Node newnode = new Node(key, val);
            cache.put(key, newnode);
            addToTail(newnode);
            usedsize++;
            //檢查當(dāng)前雙向鏈表的有效數(shù)據(jù)個(gè)數(shù) 是不是超過了capacity
            if (usedsize >capacity) {
                Node removeNode = removeHead();
                cache.remove(removeNode.key);
                usedsize--;
            }
        } else {
            //更新val的值，其實(shí)沒必要
            node.val = val;
            moveTotail(node);
        }
    }

    //刪除指定節(jié)點(diǎn)
    public void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    //移動(dòng)當(dāng)前節(jié)點(diǎn)到尾巴節(jié)點(diǎn)
    public void moveTotail(Node node) {
        removeNode(node);
        addToTail(node);
    }

    //添加到尾巴節(jié)點(diǎn)
    public void addToTail(Node node) {
        tail.prev.next = node;
        node.prev = tail.prev;
        node.next = tail;
        tail.prev = node;
    }

    //刪除最近沒使用的頭結(jié)點(diǎn)
    public Node removeHead() {
        Node del = head.next;
        head.next = del.next;
        del.next.prev = head;
        return del;
    }

    //訪問當(dāng)前的key 把你訪問的節(jié)點(diǎn)放到尾巴
    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        //把最近使用的放到了尾巴
        moveTotail(node);
        return node.val;
    }

    public void printNodes(String str) {
        System.out.println(str + " ");
        Node cur = head.next;
        while (cur != tail) {
            System.out.print(cur + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁題目：LRUCache詳解-創(chuàng)新互聯(lián)
標(biāo)題URL：http://bm7419.com/article4/dsdjie.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供軟件開發(fā)、自適應(yīng)網(wǎng)站、品牌網(wǎng)站建設(shè)、網(wǎng)站營銷、網(wǎng)站導(dǎo)航、云服務(wù)器

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容