##1. Cache的简介

缓存，顾名思义，也就是方便用户快速的获取值的一种储存方式。小到与CPU同频的昂贵的缓存颗粒，内存，硬盘，网络，CDN反代缓存，DNS递归查询，OS页面置换，Redis数据库，都可以看作缓存。它有如下的特点：

1. 缓存载体与持久载体总是相对的，容量远远小于持久容量，成本高于持久容量，速度高于持久容量。比如硬盘与网络，目前主流的SSD硬盘可以达到1000MB/S，而很多地区网速却只有4M，将网络中的文件存到硬盘中，硬盘就相当于缓存；再比如内存与硬盘，主流的DDR3内存的速度可以达到10GB/S，而硬盘相对的慢了很多数量级别，将硬盘的游戏加载到内存，内存就相对于硬盘是一种缓存。
2. 需要实现排序依据，在java中，可以使用Comparable<T>作为排序的的接口
3. 需要一种页面置换算法(page replacement algorithm)将旧页面去掉换成新的页面，如最久未使用算法（LFU）、先进先出算法（FIFO）、最近最少使用算法（LFU）、非最近使用算法（NMRU）等
4. 如果没有命中缓存，就需要从原始地址获取，这个步骤叫做“回源”，CDN厂商会标注“回源率”作为卖点

1. Comparable<T>是java用来排序的接口，推荐参考阅读《Java Software Structures Designing and Using Data Structures》
2. 页面置换算法可以参考阅读《现代操作系统》的中译本

##2. LinkedHashMap原理

###2.1. 源码概述分析

在HashMap中，维护了一个Node<K,V>[] table，当put操作时，将元素按照计算出的Hash填到数组相应位置table[Hash]中，最后迭代时，从table[0]开始向后迭代，具体的顺序取决于元素的HashCode，所以我们常说HashMap的元素迭代是不可预测的。

而在LinkedHashMap中，除了Node<K,V>[] table，还维护着2个Entry<K,V> head,tail，并组成了链表。当put元素后，调用下列回调函数对链表将元素移动到链尾以及清理旧的元素

// move node to last
void afterNodeAccess(Node<K,V> e)
// possibly remove eldest
void afterNodeInsertion(boolean evict)

在get元素时，如果设置accessOrder为true时，通过调用如下回调移动元素到链尾，这里特别强调移动，如果这个元素本身已经在链表中，那它将只会移动，而不是新建

// move node to last
void afterNodeAccess(Node<K,V> e)

综上，当你反复对元素进行get/put操作时，经常使用的元素会被移动到tail中，而长期不用的元素会被移动到head

最后迭代(Iterator)时，迭代是从旧元素迭代到新元素，这就是LRU的实现

head <--> .... <--> tail

旧元素 <-----------> 反复使用的新元素

对LinkedHashMap进行了封装实现LRU的框架，基本上是按照下图的方法进行初始化

//按照访问顺序排序的Map，设置accessOrder为true
map = new LinkedHashMap<>(0, 0.75f, true);

###2.2. HashMap的对比

以下是常见的3种map的区别，以下均不计算扩容时的时间复杂度

上述具体代码没有源码分析哦

2. 本部分基于JDK1.8.0_05，可能部分函数与网上文章相冲突
3. 在golang中，使用ring与map实现了Lru，可以看这里