146.LRU缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。

1. 难点在于用什么样的数据结构来记录Cache缓存中每个结点的访问状态。一开始用的ArrayList来保存每个key，容器中重载了两种remove()方法，分别对应着两种场景： -①缓存满时需要逐出最久未使用的结点时，可以直接通过索引下标删除cache.remove(0) -②访问一个已有结点需要更新该节点的使用状态时，可以先移除该key，再add()加入到缓存数组的尾部，这样便实现了最近使用状态的更新。此时移除是通过key值删除cache.remove(Integer.valueOf(key)) 最后还需要考虑的是当新加入的结点仅仅需要更新value值情况，这时候对应cache对这个key值使用状态更新所采取的操作会有不同。

2. 另一种是用双向链表来记录使用状态。比较难想到的点是hashmap里面value存放的不是结点值，而是这个key存放在双向链表的结点（位置），这样每次需要根据key来找到存放该结点状态的位置进行更新时，就不要遍历整个双向链表才找得到，否则单单是使用双向链表的话查询复杂度就为O(n)不满足O(1)。同时双向链表的属性除了要有value，还需要有对应的key，只有这样当缓存溢出时，才能通过head.key删去哈希表中的key结点。