一种O1性能的LRU算法

winston

LRU是一种淘汰算法，淘汰那些最久没被访问过的节点，以提高cache命中率。网游后台cache server经常会用到。这里说一种O1算法。

先明确两个操作相关的对象
1. DataKey: cache数据的key
2. IndexNode: 链表节点，内部有数据的index

list(单向链表)
      保存DataKeys。
hashtable(表)
      以DataKey作为key, IndexNode做为值，从DataKey可以定位到IndexNode。

访问一个数据对象
      先用DataKey查hash，如果找到，将IndexNode从list原来的位置拿掉，然后插到尾部。
      如果没找到，说明数据第一次被访问，有可能要淘汰旧点的数据。
      1. 查看hashtable size是否已达到最大值，未达到，将新的IndexNode插到list尾部；并且将DataKey和新的IndexNode保存到hashtable中。
      2. size已经是最大值，要淘汰一个旧节点来给新节点挪位置。从list头部取个节点，这个节点从list头部拿掉，然后通过DataKey把hash表对应的节点删除。

Dragon006

哪儿有具体实现代码啊