LRU算法模拟实现

LRU （移除最少使用内存）

模拟算法

语言：JAVA

数据结构：HASH+双向链表

原则：

 1)最少使用的是链表头（removeLRUNode）

 2)最近使用的放在链表尾（get）

 3)最近添加或更新值放在链表尾（add）

 4)节点有变化，节点的前后节点互联

 

 

package test.lrucache;

import java.util.HashMap;

public class LRUCache {

    private HashMap<String, LinkedNode> nodeMap = new HashMap<>();

    private LinkedNode rootNode;
    private LinkedNode bottomNode;

    /**
     * 添加一个新节点，如果节点已存在，则覆盖值并移至链表最后
     * @param key
     * @param value
     */
    public void add(String key, Object value) {
        LinkedNode node = get(key);
        if (node != null) {
            nodeMap.get(key).setValue(value);
        } else {
            if (bottomNode == null) {
                rootNode = bottomNode = new LinkedNode(key, value, null, null);
            } else {
                node = new LinkedNode(key, value, bottomNode, null);
                bottomNode.setAftNode(node);
                bottomNode = node;
            }
            nodeMap.put(key, bottomNode);
        }
    }

    /**
     * 获取一个节点，并移至链表最后
     * @param key
     * @return
     */
    public LinkedNode get(String key) {
        LinkedNode node = nodeMap.get(key);
        if (node != null) {
            if (rootNode != bottomNode && node != bottomNode) {
                updatePreAndAftNode(node);
                node.setPreNode(bottomNode);
                node.setAftNode(null);
                bottomNode.setAftNode(node);
                bottomNode = node;
            }
        }
        return node;
    }


    /**
     * 删除指定节点
     * @param key
     * @return
     */
    public LinkedNode remove(String key) {
        LinkedNode node = nodeMap.remove(key);
        if (node != null) {
            updatePreAndAftNode(node);
            if (node.isRootNode()) {
                rootNode = node.getAftNode();
            }
            if (node.isBottomNode()) {
                bottomNode = node.getPreNode();
            }
        }
        return node;
    }

    /**
     * 删除最少使用的节点
     */
    public void removeLRUNode() {
        remove(rootNode.getKey());
    }

    /**
     * 打印链表
     */
    public void printAllNode() {
        if (rootNode == null)
            return;
        LinkedNode curNode = rootNode;
        System.out.print(curNode.getValue() + "\t");
        while ((curNode = curNode.getAftNode()) != null) {
            System.out.print(curNode.getValue() + "\t");
        }
        System.out.println();
    }

    /**
     * 反转打印链表
     */
    public void revePrintAllNode() {
        if (bottomNode == null)
            return;
        LinkedNode curNode = bottomNode;
        System.out.print(curNode.getValue() + "\t");
        while ((curNode = curNode.getPreNode()) != null) {
            System.out.print(curNode.getValue() + "\t");
        }
        System.out.println();
    }

    /**
     * 对节点的前后节点创建连线
     * @param node
     */
    private void updatePreAndAftNode(LinkedNode node) {
        //整个链表只有一个节点
        if (node.isSingleNode()){
            return;
        }
        //是根节点
        if (node.isRootNode()) {
            node.getAftNode().setPreNode(null);
            rootNode = node.getAftNode();
        }
        //是尾节点
        else if(node.isBottomNode()) {
            node.getPreNode().setAftNode(null);
            bottomNode = node.getPreNode();
        }
        //是中间节点
        else{
            node.getPreNode().setAftNode(node.getAftNode());
            node.getAftNode().setPreNode(node.getPreNode());
        }

    }


    public static void main(String[] args) {
        LRUCache cache = new LRUCache();
        for (int i = 0; i < 10; i++) {
            cache.add("key" + i, i);
        }
        System.out.println("初始化节点key0-9");
        cache.printAllNode();

        System.out.println("删除尾节点key9");
        cache.remove("key9");
        cache.printAllNode();

        System.out.println("删除不存在的节点key10,链表不变");
        cache.remove("key10");
        cache.printAllNode();

        System.out.println("删除根节点key0");
        cache.removeLRUNode();
        cache.printAllNode();

        System.out.println("添加key10=10");
        cache.add("key10", 10);
        cache.printAllNode();

        System.out.println("使用key5，key5移到最后");
        cache.get("key5");
        cache.printAllNode();

        System.out.println("添加存的节点key10=-10,覆盖原值，并且移到最后");
        cache.add("key10", -10);
        cache.printAllNode();


        System.out.println("使用根节点key1，key1移到最后");
        cache.get("key1");
        cache.printAllNode();

        System.out.println("删除中间节点key7");
        cache.remove("key7");
        cache.printAllNode();

        System.out.println("反转打印链表");
        cache.revePrintAllNode();

        System.out.println("只保留8节点");
        cache.remove("key2");
        cache.remove("key3");
        cache.remove("key4");
        cache.remove("key6");
        cache.remove("key5");
        cache.remove("key10");
        cache.remove("key1");
        cache.printAllNode();
        cache.revePrintAllNode();

        System.out.println("8节点也删除");
        cache.remove("key8");
        cache.printAllNode();
        cache.revePrintAllNode();

    }


}

 

 

package test.lrucache;


public class LinkedNode {
    private String key;
    private Object value;
    private LinkedNode preNode;
    private LinkedNode aftNode;

    public LinkedNode(String key, Object value, LinkedNode preNode, LinkedNode aftNode) {
        this.key = key;
        this.value = value;
        this.preNode = preNode;
        this.aftNode = aftNode;
    }

    public String getKey() {
        return key;
    }

    public void setKey(String key) {
        this.key = key;
    }

    public Object getValue() {
        return value;
    }

    public void setValue(Object value) {
        this.value = value;
    }

    public LinkedNode getPreNode() {
        return preNode;
    }

    public void setPreNode(LinkedNode preNode) {
        this.preNode = preNode;
    }

    public LinkedNode getAftNode() {
        return aftNode;
    }

    public void setAftNode(LinkedNode aftNode) {
        this.aftNode = aftNode;
    }

    public boolean isRootNode() {
        return this.preNode == null;
    }

    public boolean isBottomNode(){
        return this.aftNode == null;
    }

    public boolean isSingleNode() {
        return isRootNode() && isBottomNode();
    }

    public void clear() {
        setAftNode(null);
        setPreNode(null);
        setValue(null);
    }


}

 

控制台：
-------------------------------------------------------------
初始化节点key0-9
0	1	2	3	4	5	6	7	8	9	
删除尾节点key9
0	1	2	3	4	5	6	7	8	
删除不存在的节点key10,链表不变
0	1	2	3	4	5	6	7	8	
删除根节点key0
1	2	3	4	5	6	7	8	
添加key10=10
1	2	3	4	5	6	7	8	10	
使用key5，key5移到最后
1	2	3	4	6	7	8	10	5	
添加存的节点key10=-10,覆盖原值，并且移到最后
1	2	3	4	6	7	8	5	-10	
使用根节点key1，key1移到最后
2	3	4	6	7	8	5	-10	1	
删除中间节点key7
2	3	4	6	8	5	-10	1	
反转打印链表
1	-10	5	8	6	4	3	2	
只保留8节点
8	
8	
8节点也删除

	

Process finished with exit code 0