最近在刷力扣的时候碰到的题，要求用O(1)的时间复杂度实现一个LRU算法，过程记录如下。

LinkedHashMap

　HashMap和双向链表合二为一即是LinkedHashMap。所谓LinkedHashMap，其落脚点在HashMap，因此更准确地说，它是一个将所有Entry节点链入一个双向链表的HashMap。由于LinkedHashMap是HashMap的子类，所以LinkedHashMap自然会拥有HashMap的所有特性。比如，LinkedHashMap的元素存取过程基本与HashMap基本类似，只是在细节实现上稍有不同。当然，这是由LinkedHashMap本身的特性所决定的，因为它额外维护了一个双向链表用于保持迭代顺序。

LRU算法

Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法。选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。比如LRU共有两个空位，可以记录两个页面。当输入为2，3，1，4时，页面首先记录2，3，然后按照时间顺序，淘汰掉最久未使用的2，再输入1，依此类推。

题解

题解如下：
`
class LRUCache {
private int cap;
private Map<Integer, Integer> map = new LinkedHashMap<>();
public LRUCache(int capacity) {
this.cap = capacity;
}

public int get(int key) {
	if (map.keySet().contains(key)) {
		int value = map.get(key);
		map.remove(key);
                   // 保证每次查询后，都在末尾
		map.put(key, value);
		return value;
	}
	return -1;
}

public void put(int key, int value) {
	if (map.keySet().contains(key)) {
		map.remove(key);
	} else if (map.size() == cap) {
		Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
		iterator.next();
		iterator.remove();

		// int firstKey = map.entrySet().iterator().next().getValue();
		// map.remove(firstKey);
	}
	map.put(key, value);
}

}
`
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
每次get完以后，都要put进去，保持get完的关键字在链表的起始位置，即最近使用的。
put函数有两个功能：

1. 添加未使用过的记录
2. 更新已保存，但最近使用过的记录
   首先判断是否已经使用过，即哈希表里是否存在记录，没有就写入记录，如果有就删除记录，这个过程中先判断哈希表是否已经满了，满了就先删除最远的记录，再进行写入。