【数据结构】LRU Cache

在这里插入图片描述

文章目录

• LRUCache

LRUCache

1. LRUCache是一种缓存的替换技术，在CPU和main memory之间根据计算机的局部性原理，往往会采用SRAM技术来构建CPU和主存之间的高速缓存，DRAM(dynamic random access memory)用于构建主存，LRUCache这种缓存替换技术常被应用于高速缓存中缓存行的替换，我们接下来就要模拟实现LRUCache这种数据结构。

LRU 缓存

2. LRUCache主要实现两个接口，一个是get，一个是put，实现get和put有人可能会想到用一个哈希表，因为哈希表查找和插入数据的时间复杂度刚好是O(1)，这当然没问题，但是你如何实现LRU呢？ 我们如何每次在数据满了之后，删除的数据是最近没有访问的数据呢？这该怎么保证？实际上要保证LRU方式数据的删除和更新，使用一个链表是最合适不过的了，如果我们访问了某一个数据，那就把这个数据从链表中的某一位置移动到链表头去，这样的话，每次最近访问的数据都会在链表的头部，而长时间不访问的数据就会在链表尾部放着，那么当数据结构中数据满了的时候，我们只要将链表尾部的数据删除即可，然后将新到来的数据重新插入到数据结构中，这样就可以实现LRU了。 但是现在还有一个问题，我们是将数据存储到链表当中了，但是当涉及到更新操作时，如何快速找到特定的pair结点，将他的value值更改呢？如果遍历链表来更新的话，那么这个操作就不是O(1)了而是O(N)，所以如何找到特定结点成为了破局的关键！我们让哈希表存储的pair对中的value值为链表的迭代器，这样一来就完美设计出一个高效的LRUCache结构了。 在查找某一结点时，我们直接用哈希表就可以实现O(1)的快速查找，只要能够查找到结点，那么get操作，put时可能的更新操作，这些就都是O(1)时间复杂度了。 在实现代码时，如果我们访问了某个结点，那么就要把这个结点转移到链表头部，转移的操作可以使用erase+push_front，但这样会涉及到迭代器失效的问题，因为哈希表中存储的迭代器指向原来的结点，结点被你erase了，那么迭代器就会失效，我们还需要自己重新更改哈希表中存储的迭代器，这样有点麻烦，同时删除结点其实会遍历链表，这样的操作也不是很高效，那么这时候STL还给我们提供了一个接口splice，意为拼接，可以将某一位置的迭代器指向的结点，拼接到链表中的任意位置，拼接的原理其实就是通过更改指针的指向来完成结点的转移，这样就可以不用释放结点和重新申请结点的操作了，效率就会高一些。

3. 某些面试官为了测试我们的能力，并不想让我们使用STL自带的list，而是想要让我们手搓一个链表来完成这题，则我们可以自己实现一个双向循环链表，为了使得头插尾删操作的便捷性，与传统的带头双向循环链表不同的是，我们可以伪造两个哨兵卫结点，一前一后，分别是dummyHead和dummyTail，这样在实现尾删接口时，我们不用再去找尾，同时在头插时也不用考虑结点作头的情况，直接在dummyHead后面插入即可，所以说，两个哨兵卫结点是真的香啊！