缓存

LRU是Least Recently Used的缩写，即最近最少使用算法。 插入时是最新的数据，如果缓存已满，要淘汰最旧的数据。 更新时把旧元素变为最新数据，无需淘汰。 读取时把元素变为最新数据，无需淘汰。 数组侧重读，链表侧重写。因为数组在删除插入非末尾元素的时候，需要调整余下元素的位置，所以链表会更合适。至于读，可以用哈希表提升性能。 链表和哈希表结合，这不就是java的LinkedHashMap么。LinkedHashMap会按put的顺序组织元素，链表头最旧，链表尾最新，LinkedHashMap有个accessOrder的属性，当为true时，访问元素的时候会把元素从原来的位置移除，放到链表尾，即最新的位置。因此如果要用LinkedHashMap实现一个LRU缓存，只需要给定一个容量，当元素超过这个容量的时候，把链表头（最旧）的元素移除就可以了。当然这只是一个idea，因为LinkedHashMap不是线程安全的，而缓存往往伴随多线程。 Guava的LRU 每个java程序员应该都用过Guava，guava的核心结构也是哈希表，为了线程安全，guava采用了segment分段的设计，而java8之前的ConcurrentHashMap也是采用分段来保证线程安全。 因此Guava的LRU是针对segment的，每个segment有自己的accessQueue,writeQueue,是两个双向链表，和哈希表本身结合，一个标准的LRU算法就呼之欲出了。 Redis的LRU redis作为一个内存数据库，内存弥足珍贵，我们可以在内存不足时设定几种淘汰策略，默认是不驱逐，而LRU是可选择之一。 redis维护的key数量之多，如果用双向链表和哈希来做LRU，占用额外的空间会比我们应用里实现一个LRU多的多。 因此redis采取的是不严格的LRU，LFU亦如是。 typedef struct redisObject { unsigned type:4; unsigned encoding:4; unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or * LFU data (least significant 8 bits frequency * and most significant 16 bits access time). */ int refcount; void *ptr; } robj; 在redis里，一个key对应一个redisObject，redisObject有个属性是lru，长度为LRU_BITS24位。 然后redis还自己维护了一个全局时钟。 struct redisServer { pid_t pid; char *configfile; // 全局时钟，他的取值是 mstime()/LRU_CLOCK_RESOLUTION) & LRU_CLOCK_MAX // LRU_CLOCK_RESOLUTION表示精度，默认是1s， // 所以这个取值每过 2^24 * 1s ≈ 194天 就会归零 unsigned lruclock:LRU_BITS; ....