设计实现一个LRU Cache

  1. 云栖社区>
  2. 博客>
  3. 正文

设计实现一个LRU Cache

javaedge 2018-04-13 01:40:00 浏览534
展开阅读全文

1 什么是LRU Cache

在LeetCode上有一个LRU Cache实现的题目

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

  • 解题思路:题目让设计一个LRU Cache,即根据LRU算法设计一个缓存。在这之前需要弄清楚LRU算法的核心思想,LRU全称是Least

Recently Used,即最近最久未使用。
在操作系统的内存管理中,有一类很重要的算法就是内存页面置换算法(包括FIFO,LRU,LFU等几种常见页面置换算法)。
事实上,Cache算法和内存页面置换算法的核心思想是一样的:都是在给定一个限定大小的空间的前提下,设计一个原则如何来更新和访问其中的元素。

  • LRU算法的设计原则
    如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也很小
    也就是说,当限定的空间已存满数据时,应当把最久没有被访问到的数据淘汰

  • 而用什么数据结构来实现LRU算法呢?
    可能大多数人都会想到:用一个数组来存储数据,给每一个数据项标记一个访问时间戳,每次插入新数据项的时候,先把数组中存在的数据项的时间戳自增,并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候,将被访问的数据项的时间戳置为0。当数组空间已满时,将时间戳最大的数据项淘汰。
    这种实现思路很简单,但是有什么缺陷呢?需要不停地维护数据项的访问时间戳,另外,在插入数据、删除数据以及访问数据时,时间复杂度都是O(n),数组的缺陷凸显无疑

  • 那么有没有更好的实现办法呢?
    那就是利用链表和HashMap。当需要插入新数据项,在链表中

    • 命中,则把该节点移到链表头部
    • 不存在,则新建一个节点,放在链表头部,若缓存满,则把链表最后一个节点删除即可。

在访问数据时,若数据项在链表中存在,则把该节点移到链表头部,否则返回-1
这样一来在链表尾部的节点就是最近最久未访问的数据项。

1)set(key,value)

  • 若key在hashmap中存在,则先重置value,然后获取对应节点cur,将其从链表删除,并移到链表头
  • 不存在,则新建一个节点,并将节点放到链表的头部。

当Cache满,删除链表最后一个节点

2)get(key)

  • 若key在hashmap中存在,把对应的节点放到链表头,并返回对应value
  • 若不存在,则返回-1

即保证基本的get/set同时,还要保证最近访问(get或put)的节点保持在限定容量的Cache中,如果超过容量则应该把LRU(近期最少使用)的节点删除掉。

当我们在get/set一个节点时都会把操作的这个节点移动到tail节点处,代表最新操作的节点,head节点永远指向最老的节点,当超过设定的容量时,我们就删除head节点指向的最老节点

就像是个LinkedHashMap,这样做的好处是,get/set在不冲突情况下可保证O(1)复杂度
也可通过双向链表保证LRU的删除/更新O(1)复杂度

当然可简化head和tail变成一个head节点,成环,这样head的next指向最旧的节点,prev指向最新的节点。

2 实现思路

在学习了HashMap和LinkedHashMap后,是不是觉得这俩数据结构简直太适合做LRU Cache了!那么动手实现一下:

基于HashMap和双向链表的实现

/**
 LRU Cache
 题目描述:
 Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
  
 get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
 put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
 Follow up:
 Could you do both operations in O(1) time complexity?
  
 思路:
 双向链表和hashmap。
 1.当需要插入新的数据项的时候,如果新数据项在链表中存在(一般称为命中),则把该节点移到链表头部,
 如果不存在,则新建一个节点,放到链表头部
 若缓存满了,则把链表最后一个节点删除即可。
 2.在访问数据的时候,如果数据项在链表中存在,则把该节点移到链表头部,否则返回-1。
 这样一来在链表尾部的节点就是最近最久未访问的数据项。
  
 */
public class LRUCache<K , V> {

    class Node<K,V> {
        Node pre;
        Node next;
        private final K key;
        V val;

        Node(K k, V v) {
            key = k;
            val = v;
        }
    }

    Map<K, Node> map = new HashMap<K, Node>();

    // The head (eldest) of the doubly linked list.
    Node head;
    // The tail (youngest) of the doubly linked list.
    Node tail;

    int cap;

    public LRUCache(int capacity) {
        cap = capacity;
        head = new Node(null, null);
        tail = new Node(null, null);
        head.next = tail;
        tail.pre = head;
    }

    public V get(K key) {
        Node n = map.get(key);
        if(n!=null) {
            removeNode(n);
            appendTail(n);
            return (V) n.val;
        }
        return null;
    }

    public void set(K key, V value) {
        Node n = map.get(key);
        // existed
        if(n!=null) {
            n.val = value;
            map.put(key, n);
            removeNode(n);
            appendTail(n);
            return;
        }

        if(map.size() == cap) {
           removeLast();
        }
        n = new Node(key, value);
        // youngest node append tail
        appendTail(n);
        map.put(key, n);
    }

    //移除最近最少使用的节点,注意此节点就是head.next指向的节点
    public void removeLast() {
        Node tmp = head.next;
        removeNode(tmp);
        map.remove(tmp.key);
    }

    //移除某个节点,并将此节点的前后节点连接起来
    private void removeNode(Node n){
        n.pre.next = n.next;
        n.next.pre = n.pre;
    }

    //将节点加入到队列的尾部,尾部代表最近使用的节点
    private void appendTail(Node n) {
        n.next = tail;
        n.pre = tail.pre;
        tail.pre.next = n;
        tail.pre = n;
    }
}

基于LinkedHashMap的实现

public class LRUCache<K , V> {

    private int capacity;
    private Map<K, V> cache;

    public LRUCache(final int capacity) {
        this.capacity = capacity;
        this.cache = new java.util.LinkedHashMap<K, V> (capacity, 0.75f, true) {
            // 定义put后的移除规则,大于容量就删除eldest
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > capacity;
            }
        };
    }

    public V get(K key) {
        if (cache.containsKey(key)) {
            return cache.get(key);
        } else
            return null;
    }

    public void set(K key, V value) {
        cache.put(key, value);
    }
}

网友评论

登录后评论
0/500
评论
javaedge
+ 关注