本文主要介绍一下LRU算法，least recently used,
翻译中文就是，最常使用的放在最优先级的位置，也就是按照使用的次序从近到远排序；
下面举例来说；
有 1,2,3,4,5个对象；我先使用了2，再使用了1，最后使用了3；
则顺序为: 3,1,2,4,5
这是因为最近使用的是3，其次是1，其次是2；
然后可以新加入对象，比如加入6（加入也视为一次使用），则顺序变为:
6,3,1,2,4,5
还有个需求，就是可保留的对象个数有限，比如最多就6个；
当再加入新对象时，要把最不常使用的删除；
比如加入7，则5是最不常使用的；删除，变为:
7,6,3,1,2,4
LRU是一个数据结构，主要支持两个函数
get(key), put(key,value)
含义很明显，一个是根据key,访问 值；还有一个是，把key设为对应值，要求是这两个函数都在O(1)时间完成；
类似一个map的功能，不过它有个额外能力，就是容量受限，可以把最不常用的自动删除；（或者按照从最近使用到最久使用的顺序把数据列出来）
下面我们看如何实现该结构；
从上面可以猜测用链表实现，不过链表无法实现O(1)访问，
LRU实际就是一个 hashMap + 双向List;
List中的节点是
{
key
value
}
hashMap中的值是:
{
key
ListNode*
}
也就是hashMap维护着key到链表节点的映射；
当需要访问的时候，直接通过hashMap的key O(1)索引到链表指针，进而取到value;
同时把访问的节点移动到链表首部是容易的；
下面画个图来说明:
还是用上面的例子来讲解,这里为简化假设链表中的key,value都相等，链表中就只写key了
初始:
list : n1{1} <->n2(2) <->n3{3}<->n4{4}<-> n5{5}
hash_map: (1,n1) (2,n2) (3,n3) (4,n4) (5,n5)
先使用了2:
则通过hash_map获取到 n2节点,O(1)；
再通过n2得到value 2 O(1);
再把n2移动到链表首部,O(1),(因为是双向链表，很容易把该节点O(1)时间移动到首部)
整体时间为O(1)，
变为：
list : n2{2} <->n1(1) <->n3{3}<->n4{4}<-> n5{5}
hash_map: (1,n1) (2,n2) (3,n3) (4,n4) (5,n5)
类似的使用了1，之后:
list : n1{1} <->n2(2) <->n3{3}<->n4{4}<-> n5{5}
hash_map: (1,n1) (2,n2) (3,n3) (4,n4) (5,n5)
使用了3之后:
list : n3{3} <->n1(1) <->n2{2}<->n4{4}<-> n5{5}
hash_map: (1,n1) (2,n2) (3,n3) (4,n4) (5,n5)
可见使用元素不改变hashMap,只改变链表；
之后加入key=6：
相当于在hashMap里插入一个元素，时间O(1)，同时在链表首部插入元素也是O(1),变为，
list : n6{6}<->n3{3} <->n1(1) <->n2{2}<->n4{4}<-> n5{5}
hash_map: (1,n1) (2,n2) (3,n3) (4,n4) (5,n5) (6,n6)
之后加入key=7:
此时可以把链表尾部元素删除；同时更新map，变为:
list : n7{7}<->n6{6}<->n3{3} <->n1(1) <->n2{2}<->n4{4}
hash_map: (1,n1) (2,n2) (3,n3) (4,n4) (6,n6)(7,n7)
此时链表尾部访问速度为O(1)，删除速度是O(1)，hash_map删除也是O(1);
综上，就实现了LRU数据结构算法，
可见，总结一下，
LRU其实就是用hashMap的O(1)访问能力弥补了链表的访问不足；
又利用了链表的可以很方便的把某个节点移动到首部，以及有序性的特性 弥补了hashMap的顺序性缺失，
从而者结合达到预定效果；
至此LRU算法原理就以一种非常浅显易懂的方式介绍玩了，，如果觉着好，可以点个赞，加个糖果，你的支持是我继续创作的动力
