逐步解析力扣146. LRU算法(哈希表+双向链表,LinkedHashMap源码解析,Redis内存淘汰机制)

2022/1/27 19:07:12

本文主要是介绍逐步解析力扣146. LRU算法(哈希表+双向链表,LinkedHashMap源码解析,Redis内存淘汰机制),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

LRU

LRU(Least Recently Used,最近最久未使用)是一种常见的页面置换算法,在计算中,所有的文件操作都要放在内存中进行,然而计算机内存大小是固定的,所以我们不可能把所有的文件都加载到内存,因此我们需要制定一种策略对加入到内存中的文件进项选择。

LRU的设计原理就是,当数据在最近一段时间经常被访问,那么它在以后也会经常被访问。这就意味着,如果经常访问的数据,我们需要然其能够快速命中,而不常访问的数据,我们在容量超出限制内,要将其淘汰。

实现自己的lru算法:
leetcode 146. LRU 缓存

哈希表 + 双向链表

图解原理:

1.先给双向链表设置头尾节点dummy head/dummy tail,因为链表长度capacity是2,接着往缓存里放两个kv塞满
在这里插入图片描述

2.每次get操作代表该数据最近被使用过,这里做了get(1)操作,所以要把1节点放到链表头部
在这里插入图片描述
3.这时候再put数据,这么尾部的节点就被删除,put进来的节点放到头部

在这里插入图片描述

代码:

public class LRUCache {
        class DLinkedNode {
            int key;
            int value;
            DLinkedNode prev;
            DLinkedNode next;
            public DLinkedNode() {}
            public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
        }

        private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
        private int size;
        private int capacity;
        private DLinkedNode head, tail;

        public LRUCache(int capacity) {
            this.size = 0;
            this.capacity = capacity;
            // 使用伪头部和伪尾部节点
            head = new DLinkedNode();
            tail = new DLinkedNode();
            head.next = tail;
            tail.prev = head;
        }

        public int get(int key) {
            DLinkedNode node = cache.get(key);
            if (node == null) {
                return -1;
            }
            // 如果 key 存在,先通过哈希表定位,再移到头部
            moveToHead(node);
            return node.value;
        }

        public void put(int key, int value) {
            DLinkedNode node = cache.get(key);
            if (node == null) {
                // 如果 key 不存在,创建一个新的节点
                DLinkedNode newNode = new DLinkedNode(key, value);
                // 添加进哈希表
                cache.put(key, newNode);
                // 添加至双向链表的头部
                addToHead(newNode);
                ++size;
                if (size > capacity) {
                    // 如果超出容量,删除双向链表的尾部节点
                    DLinkedNode tail = removeTail();
                    // 删除哈希表中对应的项
                    cache.remove(tail.key);
                    --size;
                }
            }
            else {
                // 如果 key 存在,先通过哈希表定位,再修改 value,并移到头部
                node.value = value;
                moveToHead(node);
            }
        }

        private void addToHead(DLinkedNode node) {
            node.prev = head;
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
        }

        private void removeNode(DLinkedNode node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        private void moveToHead(DLinkedNode node) {
            removeNode(node);
            addToHead(node);
        }

        private DLinkedNode removeTail() {
            DLinkedNode res = tail.prev;
            removeNode(res);
            return res;
        }
    }

因为是双向链表,节点类就要设置prev/next
在这里插入图片描述
其他字段:

  • 缓存cache用哈希表,注意这里的kv,value存的是节点类
  • 容量capacity表示最大容量,size表示插入时候的大小,用来与capacity进行比较
  • 默认的头尾节点head/tail

然后构造函数没啥好说的
在这里插入图片描述
get操作:就是简单的取map,但是LRU多了两个步骤:1.删除当前节点,2.移动该节点到链表头部。

复习下链表的增删节点:其实就是把prev和next的指针分别指向新的节点,removeNode方法把当前节点的prev节点的next指针指向tail节点,把当前节点的next节点的prev指针指向当前节点的prev节点,addToHead同理
在这里插入图片描述

put操作:先判断存不存在,存在就覆盖+移节点至头部;不存在就新增+移节点至头部+判断长度,长度超容量了就删尾部节点
在这里插入图片描述

LinkedHashMap源码解析

java中LinkedHashMap直接实现了LRU,需要看源码来了解其实现机制
在这里插入图片描述

众所周知 HashMap 底层是数组+红黑树+链表,是无序的,而 LinkedHashMap 刚好就比 HashMap 多这一个功能,可以按两种顺序排列:

  • 按照插入的顺序
  • 按照读取的顺序

其内部基于LRU,也是建立双向链表来维护顺序

每次插入/删除后,都会调用下图这三个函数来进行双向链表的维护
在这里插入图片描述

Redis内存淘汰机制

在这里插入图片描述
在这里插入图片描述
可以看出redis也是基于LRU的改动来实现内存淘汰



这篇关于逐步解析力扣146. LRU算法(哈希表+双向链表,LinkedHashMap源码解析,Redis内存淘汰机制)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程