起因：我的同事需要一个固定大小的cache，如果记录在cache中，直接从cache中读取，否则从数据库中读取。python的dict 是一个非常简单的cache,但是由于数据量很大，内存很可能增长的过大，因此需要限定记录数，并用LRU算法丢弃旧记录。key 是整型，value是10KB左右的python对象

分析：

1）可以想到，在对于cache，我们需要维护 key -> value 的关系

2）而为了实现LRU，我们又需要一个基于时间的优先级队列，来维护 timestamp -> (key, value) 的关系

3）当cache 中的记录数达到一个上界maxsize时，需要将timestamp 最小的(key,value) 出队列

4. 当一个（key, value) 被命中时，实际上我们需要将它从队列中，移除并插入到队列的尾部。

从分析可以看出我们的cache 要达到性能最优需要满足上面的四项功能，对于队表的快速移除和插入，链表显然是最优的选择，为了快速移除，最好使用双向链表，为了插入尾部，需要有指向尾部的指针。

下面用python 来实现：

复制代码 代码如下:

encoding=utf-8

class LRUCache(object):
def init(self, maxsize):

cache 的最大记录数

    self.maxsize = maxsize  
    # 用于真实的存储数据  
    self.inner_dd = {}  
    # 链表-头指针  
    self.head = None  
    # 链表-尾指针   
    self.tail = None

def set(self, key, value):  
    # 达到指定大小        
    if len(self.inner_dd) >= self.maxsize:  
        self.remove_head_node()

    node = Node()  
    node.data = (key, value)  
    self.insert_to_tail(node)  
    self.inner_dd[key] = node

def insert_to_tail(self, node):  
    if self.tail is None:  
        self.tail = node  
        self.head = node  
    else:  
        self.tail.next = node  
        node.pre = self.tail  
        self.tail = node

def remove_head_node(self):  
    node = self.head  
    del self.inner_dd[node.data[0]]  
    node = None  
    self.head = self.head.next  
    self.head.pre = None  
def get(self, key):  
    if key in self.inner_dd:  
        # 如果命中, 需要将对应的节点移动到队列的尾部  
        node = self.inner_dd.get(key)  
        self.move_to_tail(node)  
        return node.data[1]  
    return None

def move_to_tail(self, node):  
    # 只需处理在队列头部和中间的情况  
    if not (node == self.tail):  
        if node == self.head:  
            self.head = node.next  
            self.head.pre = None  
            self.tail.next = node  
            node.pre = self.tail  
            node.next = None  
            self.tail = node  
        else:  
            pre_node = node.pre  
            next_node = node.next  
            pre_node.next = next_node  
            next_node.pre = pre_node

            self.tail.next = node  
            node.pre = self.tail  
            node.next = None  
            self.tail = node

class Node(object):
def init(self):
self.pre = None
self.next = None

(key, value)

    self.data = None

def __eq__(self, other):  
    if self.data[0] == other.data[0]:  
        return True  
    return False  
def __str__(self):  
   return str(self.data)

if name == 'main':
cache = LRUCache(10)
for i in xrange(1000):
cache.set(i, i+1)
cache.get(2)
for key in cache.inner_dd:
print key, cache.inner_dd[key]