LRU算法

LRU(Least Recently Used)，即最近最少使用算法。常用于實現(xiàn)一個簡單的緩存功能，就是把很久未使用的直接移除掉，只保留最近使用的。

LRU主要功能

LRU主要需要實現(xiàn)兩個功能

• 添加緩存(涉及到刪除緩存)
• 獲取緩存

實現(xiàn)原理

其實用一個單鏈表就能實現(xiàn)簡單的LRU算法，但是鏈表的查找時間復雜度比較高了，是O(n)。其實用一個散列表+雙鏈表就可以實現(xiàn)一個O(1)復雜度的LRU算法。用散列表就可以直接定位某個緩存，時間復雜度O(1)，但是散列表插入緩存之后，就沒有了順序，所以才需要一個鏈表來維護這個緩存的順序，這樣才能知道哪些緩存一直未使用，超過緩存最大容量之后需要刪除未使用的緩存。而如果單鏈表刪除某個緩存的話，又需要先遍歷這個元素（時間復雜度O(n)）才行。所以這里用雙鏈表，那么就可以通過散列表直接定位到這個緩存節(jié)點，然后知道這個緩存節(jié)點的前驅(qū)和后繼節(jié)點就可以在O(1)時間復雜度內(nèi)刪除這個緩存了。

show me your code

package com.program;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * LRUCache算法：最近最少使用算法
 * 核心算法實現(xiàn)：散列表+雙向鏈表
 * 算法核心功能：
 * 1.添加緩存(先判斷散列表中是否存在該緩存，如果存在，則將該緩存移動到鏈尾。
 * 如果不存在，則先判斷鏈表是否已經(jīng)滿了，如果滿了則先把頭結點刪除，未滿則直接插到鏈尾)
 * 2.查找緩存(因為是散列表，所以時間復雜度，接近O(1))
 * 3.刪除緩存
 */
public class LRUCache {
    private int cacheSize = 10;
    private HashMap<String, Node> map = new HashMap<>();
    private Node head;
    private Node tail;

    public void LRUCache(int cacheSize) {
        this.cacheSize = cacheSize;
    }

    /**
     * 添加緩存
     * 先判斷是否已有該緩存，如果有則直接放到鏈尾取出，
     * 如果沒有，則判斷是否已滿，如果滿了，刪除鏈頭數(shù)據(jù)，否則直接插到鏈尾
     */
    public void addCache(String key, String value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            if (node.next != null) {
                if (node.pre == null) {
                    head = node.next;
                } else {
                    node.pre.next = node.next;
                    node.next.pre = node.pre;
                }
                tail.next = node;
                node.pre = tail;
                node.next = null;
                tail = node;
            }
        } else {
            Node node = new Node(key, value);
            if (map.size() == cacheSize) {
                Node temp = head;
                head = head.next;
                map.remove(temp.key);
                node.pre = tail;
                tail.next = node;
                tail = node;
            } else {
                if (head == null) {
                    head = node;
                    tail = node;
                } else {
                    node.pre = tail;
                    tail.next = node;
                    tail = node;
                }
            }
            map.put(key, node);
        }
    }

    /**
     * 獲取緩存
     * 先判斷是否有緩存，如果有，需要把該緩存移動到鏈尾返回
     */
    public String getCache(String key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            if (node.next == null) {
                return node.value;
            }
            if (node.pre == null) {
                head = node.next;
            } else {
                node.pre.next = node.next;
                node.next.pre = node.pre;
            }
            tail.next = node;
            node.pre = tail;
            node.next = null;
            tail = node;
            return node.value;
        } else {
            return null;
        }
    }

    public void test() {
        Iterator<Map.Entry<String, Node>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<String, Node> entry = iterator.next();
            System.out.println(entry.getKey() + "--" + entry.getValue().value);
        }
    }

    public void test2() {
        Node temp = head;
        while (temp != null) {
            System.out.println(temp.key);
            temp = temp.next;
        }
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache();
        cache.addCache("key0", "value0");
        cache.addCache("key1", "value1");
        cache.addCache("key2", "value2");
        cache.addCache("key3", "value3");
        cache.addCache("key4", "value4");
        cache.addCache("key5", "value5");
        cache.addCache("key6", "value6");
        cache.addCache("key7", "value7");
        cache.addCache("key8", "value8");
        cache.addCache("key9", "value9");
        cache.getCache("key9");
        cache.test2();
    }

    class Node {
        String key;
        String value;
        Node pre;
        Node next;

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

免責聲明：代碼未經(jīng)充分測試，如果發(fā)現(xiàn)問題還請不吝賜教，謝謝。