剑指 Offer II 031. 最近最少使用缓存

OrderedDict() / LinkedHashMap

python3: OrderedDict() 有序是指按插入的顺序。
java: LinkedHashMap<>() 取第一个元素的迭代器指向的 key：linked_map.entrySet().iterator().next().getKey()

from collections import OrderedDict as OD
class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.od = OD()

    def get(self, key: int) -> int:
        if key in self.od: self.od.move_to_end(key)
        return self.od.get(key, -1)

    def put(self, key: int, value: int) -> None:
        if key in self.od: del self.od[key]
        if len(self.od) + 1 > self.capacity:
            self.od.popitem(last = False)
        self.od[key] = value
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class LRUCache {
    Map<Integer, Integer> map = new LinkedHashMap<>();
    int capacity;

    public LRUCache(int capacity) {        
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if(!map.containsKey(key)) return -1;
        int val = map.remove(key);
        map.put(key, val);
        return val;
    }
    
    public void put(int key, int value) {
        if(map.containsKey(key)) map.remove(key);
        else if(map.size() + 1 > capacity) map.remove(map.entrySet().iterator().next().getKey());
        map.put(key, value);
    }
}

class LRUCache extends LinkedHashMap<Integer, Integer>{
    private int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

双向链表 + 哈希表

LRU 缓存机制可以通过哈希表辅以双向链表实现。

双向链表按照被使用的顺序存储键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。

哈希表（HashMap），通过缓存数据的键映射到其在双向链表中的位置。

首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O(1) 的时间内完成 get 或者 put 操作。具体的方法如下：

对于 get 操作，首先判断 key 是否存在：
如果 key 不存在，则返回 -1；
如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。

对于 put 操作，首先判断 key 是否存在：
如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；

如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。

上述各项操作中，访问哈希表的时间复杂度为 O(1)，在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 O(1)。而将一个节点移到双向链表的头部，可以分成「删除该节点」和「在双向链表的头部添加节点」两步操作，都可以在 O(1) 时间内完成。

把存入的元素按访问的先后顺序存入双向链表。每次访问一个元素，无论是 put 还是 get 操作，都把该元素移动到链表的尾部。这样就可以保证链表的头部就是最近最少使用的元素。在实现了最近最少使用的功能后，在加入哈希表就可以实现 get 和 put 操作时间复杂度为 O(1)。哈希表内存在 key → 对应链表节点的指针，得到对应的指针便可以操作节点内的 key 和 value 值。

在双向链表的实现中，使用一个伪头部（dummy head）和伪尾部（dummy tail）标记界限，这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。

class DLinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None
        
class LRUCache:
    def __init__(self, capacity: int):
        self.cache = dict()
        # 使用伪头部和伪尾部节点    
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.size = 0

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        # 如果 key 存在，先通过哈希表定位，再移到头部
        node = self.cache[key]
        self.moveToHead(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            # 如果 key 不存在，创建一个新的节点
            node = DLinkedNode(key, value)
            # 添加进哈希表
            self.cache[key] = node
            # 添加至双向链表的头部
            self.addToHead(node)
            self.size += 1
            if self.size > self.capacity:
                # 如果超出容量，删除双向链表的尾部节点
                removed = self.removeTail()
                # 删除哈希表中对应的项
                self.cache.pop(removed.key)
                self.size -= 1
        else:
            # 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node = self.cache[key]
            node.value = value
            self.moveToHead(node)
    
    def addToHead(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    
    def removeNode(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def moveToHead(self, node):
        self.removeNode(node)
        self.addToHead(node)

    def removeTail(self):
        node = self.tail.prev
        self.removeNode(node)
        return node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

python OrderedDict

python 官方文档， python 3.6 及之后 Dict 就有序了，但与 OrderedDict 还是区别的，Dict 没有 move_to_end() 方法，popitem() 不接受可选参数。

1、定义

python 中字典 Dict 是利用 hash 存储，因为各元素之间没有顺序。OrderedDict 是按照插入顺序存储 的有序字典。 除此之外还可根据 key， val 进行排序。

2、初始化

2.1 先初始化定义一个 OrderedDict，然后按照键值对插入，此时 dict 可以记录插入字典的顺序

import collections
d = collections.OrderedDict()
d["name"] = "muya"
d["age"] = 25
d["money"] = "Zero"
 
for key, value in d.items():
    print(key, value)
 
# 输出：
# name muya
# age 25
# money Zero
1
2
3
4
5
6
7
8
9
10
11
12
13

2.2 在定义时初始化好键值对，但这些初始化的内容无法实现有序。不过之后再对该字典进行插入的键值仍然是有序的。

import collections
 
d = collections.OrderedDict(name="muya", age=25, money="Zero")
d["dream"] = "have money"
d["other dream"] = "have gf"
 
for key, value in d.items():
    print(key, value)
 
# 输出：
# money Zero
# age 25
# name muya
# dream have money
# other dream have gf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3、排序

OrderedDict 可根据 key 或者 val 进行排序。

dd = {'banana': 3, 'apple':4, 'pear': 1, 'orange': 2}
# 按 key 排序
kd = collections.OrderedDict(sorted(dd.items(), key=lambda t: t[0]))
print(kd)
# 按照 value 排序
vd = collections.OrderedDict(sorted(dd.items(),key=lambda t:t[1]))
print(vd)
# 输出
# OrderedDict([('apple', 4), ('banana', 3), ('orange', 2), ('pear', 1)])
# OrderedDict([('pear', 1), ('orange', 2), ('banana', 3), ('apple', 4)])
1
2
3
4
5
6
7
8
9
10

4、常用函数

import collections 
dic = collections.OrderedDict()
dic.clear()  # clear(清空有序字典)
new_dic = dic.copy() # copy(拷贝)
 
# fromkeys(指定一个列表，把列表中的值作为字典的 key,生成一个字典)
name = ['tom','lucy','sam']
dic.fromkeys(name)
dic.fromkeys(name, 20)
dic.items() # items(返回由“键值对组成元素“的列表)
dic.keys() # keys(获取字典所有的key)
dic.value() # values(获取字典所有的value，返回一个列表)
 
# move_to_end(指定一个 key，把对应的 key-value 移到最后)
dic["name"] = "muya"
dic["age"] = 25
dic["money"] = "Zero"
dic.move_to_end("name")    # 将 name 移到最后
dic.move_to_end("money", last=False)   # 设置 last 为 False, 将 money 移到最前面
 
# pop(获取指定 key 的 value，并在字典中删除)
dic.pop("name")           # 删除 name, 注意必须指定关键字 key 
# popitem(按照后进先出原则，删除最后加入的元素，返回 key-value)
dic.popitem()            # 删除最后加入的
dic.popitem(last=False)  # 删除第一个加入的 
# setdefault(获取指定 key 的 value，如果 key 不存在，则创建)
val = dic.setdefault('k5')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

5、与 Dict 区别

常规的 Dict 被设计为非常擅长映射操作。 跟踪插入顺序是次要的
OrderedDict 旨在擅长重新排序操作。 空间效率、迭代速度和更新操作的性能是次要的
OrderedDict 在频繁的重排任务中还是比 Dict 更好，这使他更适用于实现各种 LRU 缓存
OrderedDict 类的 popitem() 方法有不同的签名。它接受一个可选参数来指定弹出哪个元素
弹出最后面元素：常规的 Dict 使用 d.popitem() ，OrderedDict 类使用 od.popitem()
弹出第一个元素：常规的 Dict 使用 (k := next(iter(d)), d.pop(k)) ，OrderedDict 类使用 od.popitem(last=False)
类有一个 move_to_end() 方法，可以有效地将元素移动到任一端
将 K，V 对移到最后面：常规的 Dict 使用 d[k] = d.pop(k) ，OrderedDict 类使用 od.move_to_end(k, last=True)
将K，V 对移到最前面：常规的 Dict 没有对应功能，OrderedDict 类使用 od.move_to_end(k, last=False)

OrderedDict 对象

有序词典就像常规词典一样，但有一些与排序操作相关的额外功能。由于内置的 dict 类获得了记住插入顺序的能力（在 Python 3.7 中保证了这种新行为），它们变得不那么重要了。

一些与 dict 的不同仍然存在：

常规的 dict 被设计为非常擅长映射操作。 跟踪插入顺序是次要的。
OrderedDict 旨在擅长重新排序操作。 空间效率、迭代速度和更新操作的性能是次要的。
The OrderedDict algorithm can handle frequent reordering operations better than dict. As shown in the recipes below, this makes it suitable for implementing various kinds of LRU caches.

对于 OrderedDict ，相等操作检查匹配顺序。
A regular dict can emulate the order sensitive equality test with p == q and all(k1 == k2 for k1, k2 in zip(p, q)).

OrderedDict 类的 popitem() 方法有不同的签名。它接受一个可选参数来指定弹出哪个元素。

A regular dict can emulate OrderedDict’s od.popitem(last=True) with d.popitem() which is guaranteed to pop the rightmost (last) item.

A regular dict can emulate OrderedDict’s od.popitem(last=False) with (k := next(iter(d)), d.pop(k)) which will return and remove the leftmost (first) item if it exists.

OrderedDict 类有一个 move_to_end() 方法，可以有效地将元素移动到任一端。

A regular dict can emulate OrderedDict’s od.move_to_end(k, last=True) with d[k] = d.pop(k) which will move the key and its associated value to the rightmost (last) position.

A regular dict does not have an efficient equivalent for OrderedDict’s od.move_to_end(k, last=False) which moves the key and its associated value to the leftmost (first) position.

Python 3.8之前， dict 缺少 reversed() 方法。

class collections.OrderedDict([items])
返回一个 dict 子类的实例，它具有专门用于重新排列字典顺序的方法。

3.1 新版功能.

popitem(last=True)
有序字典的 popitem() 方法移除并返回一个 (key, value) 键值对。 如果 last 值为真，则按 LIFO 后进先出的顺序返回键值对，否则就按 FIFO 先进先出的顺序返回键值对。

move_to_end(key, last=True)
Move an existing key to either end of an ordered dictionary. The item is moved to the right end if last is true (the default) or to the beginning if last is false. Raises KeyError if the key does not exist:

d = OrderedDict.fromkeys(‘abcde’)
d.move_to_end(‘b’)
‘’.join(d)
‘acdeb’
d.move_to_end(‘b’, last=False)
‘’.join(d)
‘bacde’

3.2 新版功能.

相对于通常的映射方法，有序字典还另外提供了逆序迭代的支持，通过 reversed() 。

OrderedDict 之间的相等测试是顺序敏感的，实现为 list(od1.items())==list(od2.items()) 。 OrderedDict 对象和其他的 Mapping 的相等测试，是顺序敏感的字典测试。这允许 OrderedDict 替换为任何字典可以使用的场所。

在 3.5 版更改: OrderedDict 的项(item)，键(key)和值(value) 视图 现在支持逆序迭代，通过 reversed() 。

在 3.6 版更改: PEP 468 赞成将关键词参数的顺序保留， 通过传递给 OrderedDict 构造器和它的 update() 方法。

在 3.9 版更改: 增加了合并 (|) 与更新 (|=) 运算符，相关说明见 PEP 584。

OrderedDict 例子和用法

创建记住键值 最后 插入顺序的有序字典变体很简单。 如果新条目覆盖现有条目，则原始插入位置将更改并移至末尾:

class LastUpdatedOrderedDict(OrderedDict):
    'Store items in the order the keys were last added'

    def __setitem__(self, key, value):
        super().__setitem__(key, value)
        self.move_to_end(key)
一个 OrderedDict 对于实现 functools.lru_cache() 的变体也很有用:

from time import time

class TimeBoundedLRU:
    "LRU Cache that invalidates and refreshes old entries."

    def __init__(self, func, maxsize=128, maxage=30):
        self.cache = OrderedDict()      # { args : (timestamp, result)}
        self.func = func
        self.maxsize = maxsize
        self.maxage = maxage

    def __call__(self, *args):
        if args in self.cache:
            self.cache.move_to_end(args)
            timestamp, result = self.cache[args]
            if time() - timestamp <= self.maxage:
                return result
        result = self.func(*args)
        self.cache[args] = time(), result
        if len(self.cache) > self.maxsize:
            self.cache.popitem(0)
        return result
class MultiHitLRUCache:
    """ LRU cache that defers caching a result until
        it has been requested multiple times.

        To avoid flushing the LRU cache with one-time requests,
        we don't cache until a request has been made more than once.

    """

    def __init__(self, func, maxsize=128, maxrequests=4096, cache_after=1):
        self.requests = OrderedDict()   # { uncached_key : request_count }
        self.cache = OrderedDict()      # { cached_key : function_result }
        self.func = func
        self.maxrequests = maxrequests  # max number of uncached requests
        self.maxsize = maxsize          # max number of stored return values
        self.cache_after = cache_after

    def __call__(self, *args):
        if args in self.cache:
            self.cache.move_to_end(args)
            return self.cache[args]
        result = self.func(*args)
        self.requests[args] = self.requests.get(args, 0) + 1
        if self.requests[args] <= self.cache_after:
            self.requests.move_to_end(args)
            if len(self.requests) > self.maxrequests:
                self.requests.popitem(0)
        else:
            self.requests.pop(args, None)
            self.cache[args] = result
            if len(self.cache) > self.maxsize:
                self.cache.popitem(0)
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63