LRU Cache简介

LRU是Least Recent Used的简写，翻译成中文就是 最近最少被使用。
无论是对某个key的get，还是set都算做是对该key的一次使用。当set一个不存在的key，并且LRU Cache中key的数量超过cache size的时候，需要将使用时间距离现在最长的那个key从LRU Cache中清除。

LRU Cache实现

在Java中，LRUCache是通过LinkedHashMap实现的。鄙人照猫画虎，实现一个Python版的LRU Cache（可能和其他大神的实现有所区别）。

首先，需要说明的是：

• LRU Cache对象内部会维护一个 双端循环链表 的 头节点
• LRU Cache对象内部会维护一个dict
• 内部dict的value都是Entry对象，每个Entry对象包含：
  • key的hash_code（hash_code = hash(key)，在本实现中，hash_code相同的不同key，会被当作一个key来处理。因此，对于自定义类，应该实现魔术方法：__hash__）
  • v - (key, value)对中的value
  • prev - 前一个对象
  • next - 后一个对象

具体实现是：

• 当从LRU Cache中get一个key的时候：
  • 计算该key的hash_code
  • 从内部dict中获取到entry
  • 将该entry移动到 双端循环链表 的 第一个位置
  • 返回entry.value
• 当向LRU Cache中set一个(key, value)对的时候：
  • 计算该key的hash_code，
  • 从LRU Cache的内部dict中，取出该hash_code对应的old_entry（可能不存在），然后根据(key, value)对生成一个new_entry，之后执行：
    • dict[hash_code] = new_entry
    • 将new_entry提到 双端循环链表 的第一个位置
    • 如果old_entry存在，则从链表中删除old_entry
    • 如果是新增了一个(key, value)对，并且cache中key的数量超过了cache size，那么将双端链表的最后一个元素删除（该元素就是那个最近最少被使用的元素），并且从内部dict中删除该元素

Python实现

class Entry:
    def __init__(self, hash_code, v, prev=None, next=None):
        self.hash_code = hash_code
        self.v = v
        self.prev = prev
        self.next = next

    def __str__(self):
        return "Entry{hash_code=%d, v=%s}" % (
            self.hash_code, self.v)
    __repr__ = __str__

class LRUCache:
    def __init__(self, max_size):
        self._max_size = max_size
        self._dict = dict()
        self._head = Entry(None, None)
        self._head.prev = self._head
        self._head.next = self._head

    def __setitem__(self, k, v):
        try:
            hash_code = hash(k)
        except TypeError:
            raise

        old_entry = self._dict.get(hash_code)
        new_entry = Entry(hash_code, v)
        self._dict[hash_code] = new_entry

        if old_entry:
            prev = old_entry.prev
            next = old_entry.next
            prev.next = next
            next.prev = prev

        head = self._head
        head_prev = self._head.prev
        head_next = self._head.next

        head.next = new_entry
        if head_prev is head:
            head.prev = new_entry
        head_next.prev = new_entry
        new_entry.prev = head
        new_entry.next = head_next

        if not old_entry and len(self._dict) > self._max_size:
            last_one = head.prev
            last_one.prev.next = head
            head.prev = last_one.prev
            self._dict.pop(last_one.hash_code)

    def __getitem__(self, k):
        entry = self._dict[hash(k)]
        head = self._head
        head_next = head.next
        prev = entry.prev
        next = entry.next

        if entry.prev is not head:
            if head.prev is entry:
                head.prev = prev
            head.next = entry

            head_next.prev = entry
            entry.prev = head
            entry.next = head_next

            prev.next = next
            next.prev = prev

        return entry.v

    def get_dict(self):
        return self._dict

if __name__ == "__main__":
    cache = LRUCache(2)
    inner_dict = cache.get_dict()

    cache[1] = 1
    assert inner_dict.keys() == [1], "test 1"
    cache[2] = 2
    assert sorted(inner_dict.keys()) == [1, 2], "test 2"
    cache[3] = 3
    assert sorted(inner_dict.keys()) == [2, 3], "test 3"
    cache[2]
    assert sorted(inner_dict.keys()) == [2, 3], "test 4"
    assert inner_dict[hash(2)].next.v == 3
    cache[4] = 4
    assert sorted(inner_dict.keys()) == [2, 4], "test 5"
    assert inner_dict[hash(4)].v == 4, "test 6"