|
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
分析
一道经典的算法题，可以背下来，但是最好整理一下思路：
1，缓存有容量限制，为了避免超出容量限制，一般会用一个属性size记录缓存内数据的数目。
2，需要以O(1)的时间复杂度查找一个数据，一般是用哈希表实现的，其他数据结构没有那么快。也就是说，我们需要把所有数据存入一个哈希表中，对于每个要查找的数据，能快速从表中取出这个数据。
3，关键字存在则变更数据，不存在则插入数据，超出容量则逐出一个数据，直到这里的要求，哈希表都是可以满足的，但是该题还要求逐出最久未使用的关键字，哈希表无法快捷有效地做到查找到最久未使用的关键字，因为哈希表逻辑上是没有顺序的，所以为了使数据具有顺序性，需要一个线性的数据结构，而且这个数据需要能便捷地在任意位置进行插入删除操作，这样才能做到当访问过已有的某个数据时，把它的位置调整到数据开头，这种数据结构显然就是双向链表。但是双向链表无法进行随机访问，不过这个问题反过来又被哈希表解决，两个数据结构的组合可以完美地实现LRU功能。
总结
1，哈希表的作用是对于给定的关键字，定位到这个数据，实现O（1）的查找时间复杂度。
2，链表的作用是使得数据具有前后顺序性，即记录数据访问的时间顺序，把访问过的数据放到链表的开头就可以表示该数据最近访问过，如果要删除数据需要最后删除。
3，总的来说，总的数据结构就是快速随机查找，有顺序，可以快速随机删除插入。其中哈希表用来实现第一点，链表用来实现第二，三点。
4，可以把数据结构看成核心是一个双向链表，而哈希表的作用是实现随机查找。
细节
1,数据用内部类DLinkedNode表示，每个Node有关键字key和数据值val，一个key对应一个Node。
Node中为什么一定要存key？
Node中key的必要性在于，当从链表中删除一个Node时，需要取出对应的key，这样才能从哈希表中删除掉这个Node，因为哈希表是通过key查找Node的。
那为什么哈希表不能直接存Node?
因为题目要求就是通过key查找数据。
因为需要通过Key查找Node，所以哈希表是<key,Node>形式。因为删除数据时需要知道数据对应的key，所以Node中要有key。因为链表中的数据存的是Node，所以要通过Node才能得到key。因为删除数据是找到最近最久未使用的数据，所以只能从链表中找到删除的数据Node。
即：
找到链表中待删除的Node，删除这个Node,从Node中取出key，通过Key删除哈希表中的数据。
|