LRU Cache (146. LRU Cache)

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

Constraints:

  • 1 <= capacity <= 1000
  • 0 <= key <= 1000
  • 0 <= value <= 1000
  • At most 10000 calls will be made to get and put.

Approach:

We can solve this problem using a combination of a hash map and a doubly linked list. The hash map will store the keys and their corresponding nodes in the linked list, and the linked list will maintain the order of the nodes based on their recent usage.

Algorithm:

  • Create a hash map cache to store the keys and their corresponding nodes in the linked list.
  • Create a doubly linked list dll to store the nodes in the order of their recent usage.
  • Implement the get operation:
    • Check if the key exists in the cache. If it does, move the corresponding node to the front of the linked list and return the value.
    • If the key does not exist, return -1.
  • Implement the put operation:
    • If the key already exists in the cache, update the value and move the corresponding node to the front of the linked list.
    • If the key does not exist and the cache is full, remove the least recently used node (the node at the end of the linked list) and add the new node to the front of the linked list.
    • If the key does not exist and the cache is not full, add the new node to the front of the linked list.

代码实现：

 type LRUCache struct {
 	Cap   int
 	Keys  map[int]*list.Element // map 保存双向链表的结点
 	Lists *list.List
 }
 
  type kv struct {
  	K, V int
  }
  
func Constructor(capacity int) LRUCache {
  	return LRUCache{
  		Cap:   capacity,
  		Keys:  make(map[int]*list.Element),
  		Lists: &list.List{},
  	}
}
 
  // LRUCache 的 Get 操作很简单，在 map 中直接读取双向链表的结点。如果 map 中存在，将它移动到双向链表的表头，并返回它的 value 值，如果 map 中不存在，返回 -1。
func (this *LRUCache) Get(key int) int {
  	if element, ok := this.Keys[key]; ok {
  		this.Lists.MoveToFront(element)
  		return element.Value.(kv).V
  	}
  	return -1
}

  // 先查询 map 中是否存在 key，如果存在，更新它的 value，并且把该结点移到双向链表的表头。
  // 如果 map 中不存在，新建这个结点加入到双向链表和 map 中。
  // 最后别忘记还需要维护双向链表的 cap，如果超过 cap，需要淘汰最后一个结点，双向链表中删除这个结点，map 中删掉这个结点对应的 key。
func (this *LRUCache) Put(key int, value int) {
  	if el, ok := this.Keys[key]; ok {
  		el.Value = kv{
  			K: key,
  			V: value,
  		}
  		this.Lists.MoveToFront(el)
  	} else {
  		el := this.Lists.PushFront(kv{
  			K: key,
  			V: value,
  		})
  		this.Keys[key] = el
  	}
  	if this.Lists.Len() > this.Cap {
  		el := this.Lists.Back()
  		this.Lists.Remove(el)
  		delete(this.Keys, el.Value.(kv).K)
  	}
}