README
LRU
Least Recently Used,最近最久未使用法(我更喜欢理解为：最近最少使用) 它是按照一个非常著名的计算机操作系统基础理论得来的：最近使用的页面数据会在未来一段时期内仍然被使用,已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。
LRU 的策略是最早操作过的数据放最后，最晚操作过的放开始，按操作时间逆序，如果达到上限，则淘汰末尾的项。主要用于对数据的缓存，比如在操作数据库的时候，加一层缓存能够大大提高数据库的性能。
LRU 算法实现思路
写入和获取缓存-复杂度要求在O(1)
如需要在 O(1) 的时间复杂度中完成写入和获取操作，那哈希表是一个很好的选择。 在JS里有两种结构底层都是哈希表：
- 一个是ES5对象的键值存储{}
- 一个是ES6帮我们封装的Map
淘汰-复杂度要求在O(1)
它发生在写入新数据之时，一旦需要淘汰数据，则需要遍历整个哈希表以获取最早操作的那一项。获取操作不再是 O(1) 时间复杂度。淘汰数据的时间复杂度必须是 O(1)，因而需要额外的数据结构； 我们知道链表在插入的时候是不会像数组那样，移动其他的元素的，我们只需更改指针。所以链表的插入和删除都是O(1)的复杂度。 还有一个问题就是如何找到我们要删除的节点，即使是链表找到插入点复杂度也在O(n)。 这里有一个比较巧妙的地方就是，结合了上面的哈希表就可以了，哈希表找元素在O(1) 只要修改哈希表，将存储的值设为链表节点即可。
ES5：hash表+链表
简单理解为链表的每个节点被pre和next指向，而且每个节点还被hash表的不同地址唯一指向，这样找链表中的节点就可以直接找到了。
ES6：采用Map的特性
ES6 Map中keys是有序性的，意思就是Map内部帮我们维护了插入哈希表的先后顺序，而这个先后顺序就是我们需要的以时间来排序，所以Map不用结合双向循环链表来实现(我怀疑Map底层的keys就是基于链表做的)
get操作
- 如果元素存在，先delete再set, 元素便会置为最新使用；如果不存在，返回-1
put操作
- 如果元素存在，先delete再set, 元素便会置为最新使用；
- 如果容器超限，进行删除末尾元素操作，使用 Map{}.keys().next()得到迭代器的第一个元素，为使用时间最远的元素，进行删除
一些其他的算法
- LRU 最近最久未使用
- FIFO 先进先出置换算法 类似队列
- OPT 最佳置换算法 （理想中存在的）
- NRU Clock置换算法
- LFU 最少使用置换算法
- PBA 页面缓冲算法