LRU原理

HashMap+双向链表实现（hashmap用于查询，双向链表主要用于保证新旧顺序）

put O(1)

  1. 判断是否存在，如果存在，替换（这里存在替换是否算是被使用？如果是的话，需要把它提到链表头）
  2. 如果不存在，需要插入，此时需要判断是否达到容量限制，如果达到了，需要先将最少使用的元素删除掉（tail）然后再插入（head），否则直接插入（head）

get O(1)

  1. 在hashmap中判断是否存在，不存在返回-1
  2. 存在返回value值，并更新该节点位置（head）

LRU实现

https://www.nowcoder.com/profile/3579635/codeBookDetail?submissionId=67309100

  1. 双向链表头尾都添加一个哑节点，以方便对链表进行操作
  2. 不要忘记对HashMap进行操作，往往只记得了对双向链表更新；
  3. 记得size++

Redis的LRU实现

  1. Redis并没有采取双向链表来保存节点的新旧关系，而是为每个value添加一个时间戳，每次获取都会更新其时间戳
  2. 超过capacity进行删除操作时，最开始采用的是随机选取若干个，删除其中最小的那个值，后来对该算法进行了改进，每一次随机选取出来的value会被放入一个pool中（只有比pool中的元素旧，才放入），当pool满时，删除其中最新的值；每次删除操作时，都选择删除pool中最老的元素。