LRUcache

1.LinkedHashMap 是 HashMap 的一个子类，它保留插入的顺序，如果需要输出的顺序和输入时的相同，那么就选用 LinkedHashMap。

它通过维护一个链表来保证对哈希表迭代时的有序性。

在双向链表( std::list )中存放实际的KV对；
在哈希表( std::unordered_map )中存放Key到双向链表中的相应位置迭代器的映射。
这么设计的目的是，在插入和遍历时，可以利用利用双向链表的灵活性，进行随机地插入元素，同时因其迭代器永不失效，所以可以作为哈希表中的value；查找时可以利用哈希表的特性，基于关键字key做平均常数时间复杂度的快速查找。

put元素时：移除尾部节点，并将新节点插入到链表头部，hashmap正常插入

get元素时：获取这个节点将其移动到链表头部。

2. LruCache（Least Recently Used）算法的核心思想就是最近最少使用算法。

 LruCache中维护了一个集合LinkedHashMap，该LinkedHashMap是以访问顺序排序的。

当调用put()方法时，就会在结合中添加元素，并调用trimToSize()判断缓存是否已满，如果满了就用LinkedHashMap的迭代器删除队尾元素，即最近最少访问的元素。

当调用get()方法访问缓存对象时，就会调用LinkedHashMap的get()方法获得对应集合元素，同时会更新该元素到队头。

3.

LRUcache

原文：https://www.cnblogs.com/liuweiweitju/p/14719376.html