前言缓存是一种提高数据读取性能的技术。计算机中CPU和主存读取数据是有区别的。在CPU和主存之间有一个CPU缓存，而在内存和硬盘中有一个内存缓存。当主存容量远大于CPU缓存，或者磁盘容量远大于主存时，哪些数据应该清除，哪些数据应该保留，需要缓存淘汰策略来决定。常见的策略有三种：先进先出策略FIFO（FirstInFirstOut），最少使用策略LFU（LeastFrequentlyUsed），最近最少使用策略LRU（LeastRecentlyUsed）。LRU描述了LRU（最近最少使用）缓存机制的设计和实现。实现LRUCache类：LRUCache(intcapacity)使用正整数作为容量初始化LRU缓存intget(intkey)如果缓存中存在key，则返回key的值，否则返回-1。voidput(intkey,intvalue)如果关键字已经存在，改变它的数据值；如果关键字不存在，则插入“keyword-value”的集合。当缓存容量达到上限时，它应该在写入新数据之前删除最旧的未使用数据值，从而为新数据值腾出空间。解题思路哈希表+双向链表针对LRU的特点，选择使用双向链表来实现。使用gut方法获取数据，如果有数据则返回数据，并将数据放在链表的头部。使用put方法存储数据。如果数据存在，直接覆盖新值；如果数据不存在，则添加一个新值。新值放在链表的头部。此外，还需要判断缓存是否已经超过capacity容量，如果超过则删除链表的尾节点。因为是单链表，每次获取数据或者删除数据，都需要遍历链表。时间复杂度为O(n)。这里使用hash来记录每条数据的位置，降低数据访问的时间复杂度为O。(1)。classLRUCache{classDLinkedNode{intkey;整数值；DLinkedNode上一个；接下来是DLinkedNode；publicDLinkedNode(){}publicDLinkedNode(intkey,intvalue){this.key=key;this.value=值；}}私有整数大小；私有int容量；私有DLinkedNode头；私有DLinkedNode尾部；privateMapcache=newHashMap<>();publicLRUCache(intcapacity){this.size=0;this.capacity=容量；head=newDLinkedNode();tail=newDLinkedNode();head.next=尾巴；tail.prev=head;}publicintget(intkey){DLinkedNodenode=cache.get(key);如果（节点==null）{返回-1；}//找到并移动到首位moveToHead(node);返回节点值；}publicvoidput(intkey,intvalue){DLinkedNodenode=cache.get(key);if(node==null){//如果不存在则创建一个新的节点DLinkedNodenewNode=newDLinkedNode(key,value);cache.put(key,newNode);添加到头（新节点）；尺码++；if(size>capacity){//超出容量，移除最后一个节点DLinkedNodetail=removeTail();缓存.remove(tail.key);尺寸-;}}else{//key存在，覆盖value，移至headif(node.value!=value){node.value=value;}moveToHead（节点）；}}privateDLinkedNoderemoveTail(){DLinkedNodenode=tail.prev;移除节点（节点）；返回节点；}privateDLinkedNoderemoveNode(DLinkedNodenode){node.next.prev=node.prev;node.prev.next=node.next;返回节点；}privatevoidmoveToHead(DLinkedNodenode){removeNode(node);添加到头（节点）；}私有无效addToHead广告（DLinkedNode节点）{node.prev=head;node.next=head.next;head.next.prev=节点；head.next=节点；}}参考[LRU维基百科]()极客时间-王征-LRU缓存淘汰算法如何实现？
