首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >实现LRU算法

实现LRU算法

作者头像
Defu Li
发布2020-09-08 21:02:33
8090
发布2020-09-08 21:02:33
举报
文章被收录于专栏:斜述视角斜述视角

LRU算法是一种缓存淘汰机制策略。

计算机的缓存容量有限,如果缓存满了就要删除一些内容给新的内容腾出位置,而删除哪些内容,就有不同的策略,LRU算法是其中一种策略。

LRU算法删除的是最近一段时间最少使用的内容。

代码中的capacity代表缓存的容量,使用Hash表 + 链表实现LRU算法。

基本思路

使用链表维护使用内容的先后顺序,比如最近使用了内容1,那么将内容1插入到链表的尾端。

使用Hash表可以根据key找到value。

package leetcode;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class LRUCache {
    Map<Integer, Integer> map;
    LinkedList<Integer> list;
    Integer capacity;
    public LRUCache(int capacity) {
        map = new HashMap();
        list = new LinkedList<>();
        this.capacity = capacity;
    }

    public int get(int key) {
        if(map.containsKey(key)) {
            list.remove(new Integer(key));
            list.addLast(key);
            return map.get(key);
        } else return -1;
    }

    public void put(int key, int value) {
        if(map.containsKey(key)) {
            list.remove(new Integer(key));
            list.addLast(key);
            map.put(key, value);
        }else {
            if(map.size() == capacity) {
                // lru清除一个缓存
                lruClear(key, value);
            }else {
                list.addLast(key);
                map.put(key, value);
            }
        }
    }

    private void lruClear(int key, int value) {
        Integer first = list.removeFirst();
        list.addLast(key);
        map.remove(first);
        map.put(key ,value);
    }
    // 测试
    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1,1);
        lruCache.put(2,2);
        System.out.println(lruCache.get(1));
        lruCache.put(3,3);
        System.out.println(lruCache.get(2));
        lruCache.put(4,4);
        System.out.println(lruCache.get(1));
        System.out.println(lruCache.get(3));
        System.out.println(lruCache.get(4));
    }
}

时间复杂度分析

get方法O(n)

put方法O(n)

之所以get和put方法的时间复杂度都是O(n),在于对链表节点的删除操作。

那么有没有方法可以将get和put方法的时间复杂度降到O(1)?

有的。

可以先自己实现一个双向链表,链表中的节点自己定义。Hash表中存储的value为链表中的节点对象,在对链表节点进行删除操作时可以将时间复杂度降到O(1)。

package leetcode;

import java.util.HashMap;
import java.util.Map;

public class LRUCacheII {

    // 自定义链表节点
    class Node {
        Node pre;
        Node next;
        int key;
        int value;

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

    Map<Integer, Node> map;
    Node head;
    Node tail;
    int capacity;

    LRUCacheII(int capacity) {
        map = new HashMap<>();
        head = new Node(Integer.MIN_VALUE, Integer.MIN_VALUE);
        tail = new Node(Integer.MAX_VALUE, Integer.MAX_VALUE);
        head.next = tail;
        tail.pre = head;
        this.capacity = capacity;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            moveToLast(node);
            return node.value;
        } else return -1;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            // 删除并移动最后
            if(map.get(key).value != value) {
                map.get(key).value = value;
            }
            Node node = map.get(key);
            moveToLast(node);
            map.put(key, node);
        } else {
            Node node = new Node(key, value);
            if (map.size() == capacity) {
                // lru清除一个
                int keyFirst = deleteFirst();
                addLast(node);
                map.remove(keyFirst);
                map.put(key, node);
            } else {
                addLast(node);
                map.put(key ,node);
            }
        }
    }

    public void moveToLast(Node node) {
        if (node.next == tail) {
            return;
        } else {
            Node temp = node.next;
            node.pre.next = temp;
            temp.pre = node.pre;

            tail.pre.next = node;
            node.pre = tail.pre;
            tail.pre = node;
            node.next = tail;
        }
    }

    public int deleteFirst() {
        int res = head.next.key;
        head.next = head.next.next;
        head.next.pre = head;
        return res;
    }

    public void addLast(Node node) {
        tail.pre.next = node;
        node.pre = tail.pre;
        node.next = tail;
        tail.pre = node;
    }

    public static void main(String[] args) {
        LRUCacheII lruCache = new LRUCacheII(2);
        lruCache.put(2,1);
        lruCache.put(2,2);
        System.out.println(lruCache.get(2));
        lruCache.put(1,1);
        lruCache.put(4,1);
        System.out.println(lruCache.get(2));
    }
}
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-09-04,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 斜述视角 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档