1.概念

創新互聯專注于孝義網站建設服務及定制，我們擁有豐富的企業做網站經驗。 熱誠為您提供孝義營銷型網站建設，孝義網站制作、孝義網頁設計、孝義網站官網定制、微信平臺小程序開發服務，打造孝義網絡公司原創品牌,更為您提供孝義網站排名全網營銷落地服務。

LRU是Least Recently Used的縮寫，意思是最近最少使用，它是一種Cache替換算法。
Cache的容量有限，因此當Cache的容量用完后，而又有新的內容需要添加進來時， 就需要挑選并舍棄原有的部分內容，從而騰出空間來放新內容。LRU Cache 的替換原則就是將最近最少使用的內容替換掉。其實，LRU譯成最久未使用會更形象， 因為該算法每次替換掉的就是一段時間內最久沒有使用過的內容。

2.LRUCache的實現原理

實現LRU Cache的方法和思路很多，但是要保持高效實現O(1)的put和get，那么使用雙向鏈表和哈希表的搭配是最高效和經典的。

使用雙向鏈表是因為雙向鏈表可以實現任意位置O(1)的插入和刪除，

使用哈希表是因為哈希表的增刪查改也是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++;
            //檢查當前雙向鏈表的有效數據個數 是不是超過了capacity
            if (usedsize >capacity) {
                Node removeNode = removeHead();
                cache.remove(removeNode.key);
                usedsize--;
            }
            printNodes("put");
        } else {
            //更新val的值，其實沒必要
            node.val = val;
            moveTotail(node);
        }
    }

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

    //移動當前節點到尾巴節點
    public void moveTotail(Node node) {
        removeNode(node);
        addToTail(node);
    }

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

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

    //訪問當前的key 把你訪問的節點放到尾巴
    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("存放元素，會刪除頭結點，因為頭節點是最近最少使用的");
        myLRUCache.put(999, 9);
    }
}

3.jdk當中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("存放元素,會刪除頭結點，因為頭結點是最近最少使用的");
        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);//把常用的數據放到了尾巴 不常用的放在頭部便于刪除
    }

    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++;
            //檢查當前雙向鏈表的有效數據個數 是不是超過了capacity
            if (usedsize >capacity) {
                Node removeNode = removeHead();
                cache.remove(removeNode.key);
                usedsize--;
            }
        } else {
            //更新val的值，其實沒必要
            node.val = val;
            moveTotail(node);
        }
    }

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

    //移動當前節點到尾巴節點
    public void moveTotail(Node node) {
        removeNode(node);
        addToTail(node);
    }

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

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

    //訪問當前的key 把你訪問的節點放到尾巴
    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();
    }
}

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

網頁題目：LRUCache詳解-創新互聯
標題URL：http://vcdvsql.cn/article4/dsdjie.html

成都網站建設公司_創新互聯，為您提供軟件開發、自適應網站、品牌網站建設、網站營銷、網站導航、云服務器

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯