卖萌的弱渣

I am stupid, I am hungry.

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.

Solution

  • 双链表+hash表
  • tail: 指向新节点的位置
  • root: 指向要被删除的节点位置
  • entryFinder: 哈希表<key,node>，记录所有节点
(LRU-Cache.py) download
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

class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        # LRU 的大小
        self.capacity = capacity
        # LRU 当前的大小
        self.size = 0
        # root 指向下一个要被删除的node
        self.root = Node(-1,-1)
        # 记录一个被访问的node 顺序， tail指向上一次被访问的节点，新节点就插入在这里
        self.tail = self.root
        # hash<key, node> 记录所有node
        self.entryFinder = {}

    def get(self, key):
        """
        :rtype: int
        """
        entry = self.entryFinder.get(key)
        if entry == None:
            return -1
        else:
            self.renew(entry)
            return entry.val


    def set(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: nothing
        """
        entry = self.entryFinder.get(key)
        # 新node
        if entry == None:
            entry = Node(key,value)
            self.entryFinder[key] = entry
            # entry插入tail
            self.tail.next = entry
            entry.prev = self.tail
            self.tail = entry

            # Cache 没有满
            if self.size<self.capacity:
                self.size += 1
            else:
                # cache 已经慢 拿掉LRU
                head = self.root.next
                if head != None:
                    self.root.next = head.next
                    head.next.prev = self.root
                del self.entryFinder[head.key]
        else:
            # 更新val和
            entry.val = value
            self.renew(entry)

    def renew(self,entry):
        # 把entry 重新插入
        if self.tail != entry:
            # remove entry
            prevNode = entry.prev
            nextNode = entry.next
            prevNode.next = nextNode
            nextNode.prev = prevNode

            # 把entry插入到tail后面并更新tail
            entry.next = None
            self.tail.next = entry
            entry.prev = self.tail
            self.tail = entry