Java教程

Java 实现 LRU 算法

本文主要是介绍Java 实现 LRU 算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

力扣题目:146. LRU 缓存

LRU 是什么?

最近最少使用算法。一个队列,将最近使用的元素放到队列的头部,当队列长度不够时,移除队列的最后一个元素,也就是最近最少使用的元素


解法 1:继承 LinkedHashMap

投机取巧解法(最好还是自己实现),利用 JavaLinkedHashMap 已经实现好的方法,所以直接继承 LinkedHashMap 为父类即可。

有兴趣可以自己阅读 LinkedHashMap 源码。重点关注这三个方法:

  • afterNodeAccess():访问元素之后,将元素放到双向链表的尾部
  • afterNodeRemoval():删除元素之后,同时将元素也从双向链表中删除
  • afterNodeInsertion():插入元素之后,是否需要移除最近最少使用的元素
/**
 * 继承 LinkedHashMap
 */
class LRUCache extends LinkedHashMap {

    /**
     * 容量
     */
    private int capacity;

    /**
     * 调用父类的构造方法
     * capacity:容量
     * 0.75F:负载因子
     * true:开启 LRU 缓存算法
     */
    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }
    
    /**
     * 获取元素,调用父类的构造方法
     * 原理:
     * 	(1)首先将这个元素从队列中移除
     *	(2)然后再将这个元素添加到队列的头部
     */
    public int get(int key) {
        return (int) super.getOrDefault(key, -1);
    }
    
    /**
     * 得到元素,调用父类的构造方法
     * 原理:
     * 	(1)首先判断 key 所代表的元素是否已经在队列中
     * 	(2)如果在队列中,则直接覆盖元素的值即可
     *	(3)覆盖之后则从队列中移除,然后再添加到队列头部
     * 	(4)此时操作完成
     * 	(5)如果不在队列中,则判断容量是否足够
     * 	(6)如果容量足够,则直接添加到队列头部,此时操作完成
     *	(7)如果容量不足够,则移除队列最后一个元素
     * 	(8)并且将要添加的元素添加到队列的头部,此时操作完成
     */
    public void put(int key, int value) {
        super.put(key, value);
    }

    /**
     * 移除元素条件方法,因为在 LinkedHashMap 中是空方法
     * 所以我们需要重写方法,定义自己的逻辑
     * 这里就是当容量不够时进行移除元素
     */
    @Override
    public boolean removeEldestEntry(Map.Entry eldest) {
        return super.size() > capacity;
    }
}

解法 2:哈希表 + 双向链表

很重要,面试官需要你写出来的是这个,要能够手写!

class LRUCache {

    /**
     * 双向链表长度
     */
    private int size;

    /**
     * 最大容量
     */
    private int capacity;

    /**
     * 哈希表,存储数据
     */
    private Map<Integer, DoubleLinkedNode> cache;

    /**
     * 双向链表头节点,不存储任何值,标识作用
     */
    private DoubleLinkedNode head;

    /**
     * 双向链表尾节点,不存储任何值,标识作用
     */
    private DoubleLinkedNode tail;

    /**
     * 构造方法
     */
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new DoubleLinkedNode();
        this.tail = new DoubleLinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    
    /**
     * 获取元素
     */
    public int get(int key) {
        DoubleLinkedNode node = this.cache.get(key);

        // 如果要获取的节点不存在
        if (node == null) {
            return -1;
        }
        // 移动到双向链表头部
        moveToHead(node);
        // 返回值
        return node.value;
    }
    
    /**
     * 添加元素
     */
    public void put(int key, int value) {
        DoubleLinkedNode node = cache.get(key);
        // 如果元素不存在
        if (node == null) {
            node = new DoubleLinkedNode(key, value);
            // 添加到哈希表中
            cache.put(key, node);
            // 双向链表长度加 1
            size++;
            // 添加到双向链表头部
            addToHead(node);
            // 如果长度大于容量,说明要删除元素了
            if (size > capacity) {
                // 从双向链表中删除最后一个元素
                DoubleLinkedNode tail = removeTail();
                // 同时从哈希表中删除对应的元素
                cache.remove(tail.key);
                // 长度减 1
                size--;
            }
        // 如果元素存在
        } else {
            // 修改值
            node.value = value;
            // 移动到双向链表头部
            moveToHead(node);
        }
    }

    /**
     * 自己构造一个双向链表节点
     */
    class DoubleLinkedNode {

        /**
         * 键
         */
        int key;

        /**
         * 值
         */
        int value;

        /**
         * 前驱节点
         */
        DoubleLinkedNode prev;

        /**
         * 后继节点
         */
        DoubleLinkedNode next;

        /**
         * 构造方法
         */
        public DoubleLinkedNode() {}
        public DoubleLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    /**
     * 添加一个节点到双向链表头部
     */
    private void addToHead(DoubleLinkedNode node) {
        node.next = head.next;
        node.prev = head;
        node.next.prev = node;
        head.next = node;
    }

    /**
     * 从双向链表中删除一个节点
     */
    private void removeNode(DoubleLinkedNode node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
        node.prev = null;
        node.next = null;
    }

    /**
     * 将双向链表中一个节点移动双向链表到头部
     */
    private void moveToHead(DoubleLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    /**
     * 移除双向链表中最后一个节点
     */
    private DoubleLinkedNode removeTail() {
        DoubleLinkedNode node = this.tail.prev;
        removeNode(node);
        return node;
    }
}
这篇关于Java 实现 LRU 算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!