欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LRU-最近最久未使用算法

程序员文章站 2024-03-18 13:01:16
...
import java.util.HashMap;
import java.util.Map;

/**
 * @author caisebei
 */
public class LRUCache {


    private Node head;

    private Node end;

    private int limit;

    private Map<String,Node> hashMap;

    public LRUCache(int limit) {
        this.limit = limit;
        this.hashMap = new HashMap<>();
    }

    public Node get(String key) {
        Node node = hashMap.get(key);
        if(node == null) {
            return null;
        }
        refreshNode(node);
        return node;
    }

    public void put(String key, String value) {
        Node node = hashMap.get(key);
        if(node == null) {
            if(hashMap.size() >= limit) {
                String oldKey = removeNode(head);
                hashMap.remove(oldKey);
            }

            node = new Node(key, value);
            addNode(node);
            hashMap.put(key, node);
        } else {
            node.value = value;
            refreshNode(node);
        }
    }

    public void remove(String key) {
        Node node = hashMap.get(key);
        removeNode(node);
        hashMap.remove(key);
    }
    
    
    /**
     *  
     * 添加节点
     **/
    private void addNode(Node node) {
        if(end != null) {
            end.next = node;
            node.pre = end;
        }
        end = node;
        if(head == null) {
            head = node;
        }
    }

    
    
    /**
     * 刷新被访问的节点位置
     **/
    private void refreshNode(Node node) {
        
        if(node == end) {
            return ;
        }
        
        removeNode(node);
        addNode(node);
    }

    
    /**
     * 删除节点
     * @return java.lang.String
     **/
    private String removeNode(Node node) {
        if(node == head && node == end) {  //移除唯一节点
            head = null;
            end = null;
        }else if (node == end) {  //移除尾节点
            end = end.pre;
            end.next = null;
        }else if(node == head) { // 移除头节点
            head = head.next;
            head.pre = null;
        }else {                  // 移除中间节点
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        return node.key;
    }


    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(5);
        lruCache.put("001", "用户1");
        lruCache.put("002", "用户2");
        lruCache.put("003", "用户3");
        lruCache.put("004", "用户4");
        lruCache.put("005", "用户5");
        lruCache.get("002");
        lruCache.put("006", "用户6");
    }
    


    class Node {

        public Node pre;
        public Node next;
        public String key;
        public String value;

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

    
}

from: 《漫画算法》1