LRU算法,LRU算法怎么实现?

KLQ 2020-06-30 15:19:56 java常见问答 5077

下面要给大家介绍的就是和LRU算法有关的内容,你知道LRU算法应该怎样实现吗?实现的方式有哪些呢?一起来了解一下吧。

LRU算法实现

哈希链表结构:

LRU算法怎么实现

package blogSrc;
import java.util.HashMap;
public class LRUCache
{
    private Node head;
    private Node end;
    private HashMap < String, Node > hashMap;
    private int limit; //缓存上限
    public LRUCache(int limit)
    {
        this.limit = limit;
        this.hashMap = new HashMap < String, Node > ();
    }
    //向链表中添加节点
    public void addNode(Node node)
    {
        if (head == null)
        { //空链
            head = node;
        }
        if (end != null)
        { //节点添加到尾部
            end.next = node;
            node.pre = end;
            node.next = null;
        }
        end = node;
    }
    //从链表中移除节点
    public String removeNode(Node node)
    {
        if (head == end && node == head)
        { //链表只有一个节点
            head = null;
            end = null;
        }
        else if (node == end)
        { //node为最后一个节点
            end.pre.next = null;
            end = end.pre;
        }
        else if (node == head)
        { //node为第一个节点
            head.next.pre = null;
            head = head.next;
        }
        else
        { //node为中间节点
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        return node.key;
    }
    //刷新链表,将最近使用的节点放置到链表末尾
    public void refreshNode(Node node)
    {
        if (node == end)
        {
            return;
        }
        removeNode(node); //删除节点
        addNode(node); //添加节点
    }
    //根据节点的key值,获取链表中该节点的value值
    public String get(String key)
    {
        Node node = hashMap.get(key);
        if (node == null)
        {
            return null;
        }
        refreshNode(node);
        return node.value;
    }
    //向链表上添加key-value
    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); //同时需要把节点的key也从hashmap中删除
            }
            node = new Node(key, value);
            addNode(node);
            hashMap.put(key, node);
        }
        else
        {
            node.value = value;
            refreshNode(node);
        }
    }
    //从链表上删除指定key的数据
    public void remove(String key)
    {
        Node node = hashMap.get(key);
        if (node == null)
        {
            return;
        }
        removeNode(node);
        hashMap.remove(key);
    }
    class Node
    {
        public Node next;
        public Node pre;
        public String key;
        public String value;
        Node(String key, String value)
        {
            this.key = key;
            this.value = value;
        }
        public String getNextKey()
        {
            return next.getKey();
        }
        public String getPreKey()
        {
            return pre.getKey();
        }
        public String getKey()
        {
            return key;
        }
        public String getValue()
        {
            return value;
        }
    }
    public static void main(String[] args)
    {
        LRUCache lruCache = new LRUCache(10);
        lruCache.put("001", "用户1信息");
        lruCache.put("002", "用户2信息");
        lruCache.put("003", "用户3信息");
        lruCache.put("004", "用户4信息");
        lruCache.get("003");
        System.out.println("Now End Node Key is: " + lruCache.end.getKey() + ",Value is: " + lruCache.end.getValue());
        lruCache.put("002", "用户2信息更新");
        System.out.println("Now End Node Key is: " + lruCache.end.getKey() + ",Value is: " + lruCache.end.getValue());
        lruCache.put("006", "用户6信息");
        System.out.println("Now End Node Key is: " + lruCache.end.getKey() + ",Value is: " + lruCache.end.getValue());
    }
}

这里的话要注意一下,在将节点删除的同时,一定要记得将节点的key从hashMap当中删除掉。

LRU算法如何实现的问题你知道了吗?希望上面的内容可以对大家有所帮助哦!

奇Q工具网专门为大家带来java常见问题及解决方法方面的内容,假如你有这方面的疑问的话,可以继续的通过本站来进行了解呢。

推荐阅读:

RSA算法的安全性基于什么?RSA加密原理

cas算法是指什么?有何优缺点?

进程调度的算法是指什么?有何作用?