146. LRU缓存机制(lru-cache)——LinkedHashMap实现版超简单

曾经终败给现在 2022-12-11 10:28 224阅读 0赞

# 146. LRU缓存机制 #

运用你所掌握的数据结构，设计和实现一个 `LRU (最近最少使用) 缓存机制`。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 `get(key)` \- 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 `-1`。  
写入数据 `put(key, value)` \- 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
    
    cache.put(1, 1);
    cache.put(2, 2);
    cache.get(1);       // 返回 1
    cache.put(3, 3);    // 该操作会使得关键字 2 作废
    cache.get(2);       // 返回 -1 (未找到)
    cache.put(4, 4);    // 该操作会使得关键字 1 作废
    cache.get(1);       // 返回 -1 (未找到)
    cache.get(3);       // 返回 3
    cache.get(4);       // 返回 4

# 代码1 #

LinkedHashMap内部维护了一个所有的Entity的双向链表

同时构造方法可以设置Iterator的时候,是按照插入的顺序排序还是按照访问的顺序排序

class LRUCache { 
    
        int capacity;
        LinkedHashMap<Integer, Integer> cache;
    
        public LRUCache(int capacity) { 
            this.capacity = capacity;
            cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) { 
                @Override
                protected boolean removeEldestEntry(Map.Entry eldest) { 
                    return cache.size() > capacity;
                }
            };
        }
    
        public int get(int key) { 
            return cache.getOrDefault(key, -1);
        }
    
        public void put(int key, int value) { 
            cache.put(key, value);
        }
    }
    
    /** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */

# LinkedHashMap如何按照访问的顺序来排序 #

默认是按照插入的顺序来排序的,在构造方法里边可以设置按照访问的顺序来排序

![在这里插入图片描述][b937c531cc969437f7b4ddf72169f47c.png_pic_center]  
那究竟按照访问的顺序来排序是什么意思呢?

LinkedHashMap的get(key)方法是自己实现的,并没有从HashMap里边继承,我们看看get(Key)方法的实现是什么样子的  
![在这里插入图片描述][f9660055091b8b827b6df8162466d91a.png_pic_center]  
我们看afterNodeAccess()方法是如何实现的

![在这里插入图片描述][f63bb3c17da3bbdba0d70a6f48f0cd04.png_pic_center]

//本方法的作用：将结点移动到LinkedHashMap维护的双向链表的末尾
        void afterNodeAccess(Node<K,V> e) {  // move node to last
            LinkedHashMap.Entry<K,V> last;
            if (accessOrder && (last = tail) != e) { 
                LinkedHashMap.Entry<K,V> p =
                    (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
                p.after = null;
                if (b == null)
                    head = a;
                else
                    b.after = a;
                if (a != null)
                    a.before = b;
                else
                    last = b;
                if (last == null)
                    head = p;
                else { 
                    p.before = last;
                    last.after = p;
                }
                tail = p;
                ++modCount;
            }
        }

这个方法主要就是移动双向链表的指针,将传入的结点移动到LinkedHashMap维护的双向链表的末尾,这样每次通过get(key)方法访问一个元素,这个元素就会被移动到双向链表的末尾,按照访问的顺序来排序,就是每次通过Iterator来遍历keySet或者是EntrySet的时候,访问过的元素会出现在最后边(因为LinedHashMap的Iterator遍历的时候,遍历的是内部的双向链表,从头结点,遍历到尾结点)

顺着这样的思路,如果在满足一定条件的情况下,移除掉双向链表的头结点,这样就实现了一个LruCahe

其实LinkedHashMap已经为我们提供了这样的方法,LinkedHashMap中有一个方法removeEldestEntry(entry) 我们只需要覆盖这个方法,根据我们自己的需求在一定条件下返回true,这样就实现了LruCache  
改方法的默认实现是返回false  
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) \{  
return false;  
\}

LinkedHashMap的afterNodeInsertion()方法会根据其他条件以及removeEldestEntry的返回值来决定是否删除到双向链表的表头元素

void afterNodeInsertion(boolean evict) {  // possibly remove eldest
            LinkedHashMap.Entry<K,V> first;
            if (evict && (first = head) != null && removeEldestEntry(first)) { 
                K key = first.key;
                removeNode(hash(key), key, null, false, true);
            }
        }

# 参考 #

[LRU缓存机制(lru-cache)采用java版双向链表 + Map实现][LRU_lru-cache_java_ _ Map]

[b937c531cc969437f7b4ddf72169f47c.png_pic_center]: /images/20221123/3bce2751670c476b957a0909af87a75a.png
[f9660055091b8b827b6df8162466d91a.png_pic_center]: /images/20221123/f199f644f38c451891721be8919fc1a4.png
[f63bb3c17da3bbdba0d70a6f48f0cd04.png_pic_center]: /images/20221123/63d912b20cc146d7a87153e72a080602.png
[LRU_lru-cache_java_ _ Map]: https://blog.csdn.net/e891377/article/details/105122711