-
Difficulty: Medium
-
Related Topics: Design
Description
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
设计一个数据结构，使其满足 LRU 缓存的限制。
Implement the LRUCache class:
实现 LRUCache 类：
LRUCache(int capacity)Initialize the LRU cache with positive sizecapacity.
LRUCache(int capacity)用大于 0 的整数capacity初始化 LRU 缓存。int get(int key)Return the value of thekeyif the key exists, otherwise return-1.
int get(int key)如果key存在，返回key对应的value，否则返回-1。void put(int key, int value)Update the value of thekeyif thekeyexists. Otherwise, add thekey-valuepair to the cache. If the number of keys exceeds thecapacityfrom this operation, evict the least recently used key.
void put(int key, int value)若key存在，更新key对应的value，否则，将该key-value对加入缓存。如果key的数量超过了capacity的限制，则将最近最少使用的key清出缓存。
Follow up
Could you do get and put in O(1) time capacity?
get 和 put 操作，你能使用 O(1) 时间完成吗？
Example
Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1); // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2); // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1); // return -1 (not found)
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4
Constraints
1 <= capacity <= 30000 <= key <= 30000 <= value <= 104- At most
3 * 104calls will be made togetandput.
Solution
先介绍一个“作弊”的方法，在 Java/Kotlin (JVM) 的类库里有这样一个类：java.util.LinkedHashMap/kotlin.collections.LinkedHashMap（在 Kotlin (JVM) 里其实就是前者的 alias），其实现是可以做到符合 LRU 的要求的，也被不少第三方库用作 LRUCache 的实现，我们需要做的，就是继承它，然后覆写其中的部分方法，代码如下：
class LRUCache(val capacity: Int) : LinkedHashMap<Int, Int>(capacity, 0.75f, true) {
override fun get(key: Int): Int {
return super.get(key)?:-1
}
override fun removeEldestEntry(eldest: MutableMap.MutableEntry<Int, Int>?): Boolean {
return size > capacity
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* var obj = LRUCache(capacity)
* var param_1 = obj.get(key)
* obj.put(key,value)
*/
其中 LinkedHashMap 的构造方法里有一个参数 accessOrder，将其设置为 true，将其设置为按访问顺序排列，然后重写其中的 removeEldestEntry 方法（当这个方法返回 true 时，执行 put 和 putAll 操作会清除最近最少访问的 entry，父类里此方法固定返回 false）。即可将 LinkedHashMap 作为一个 LRU Cache 来使用。至于 LinkedHashMap 的实现原理，读者可自行阅读源码，或者在网络上搜索解析。
当然，也有不那么作弊的方法，就是把 LinkedHashMap 手动展开来。相当于同时维护一个 map 和一个节点的双向链表，get 时，把 get 的节点移动到头部；remove 时，从 map 和链表中同时移除该节点；put 时，当容量超出时，把双链表尾部元素清除。代码如下：
class LRUCache(private val capacity: Int) {
private val cache = hashMapOf<Int, Node>()
private var count = 0
private var head = Node()
private var tail = Node()
init {
head.prev = null
tail.next = null
head.next = tail
tail.prev = head
}
fun get(key: Int): Int {
val node = cache[key] ?: return -1
this.moveToHead(node)
return node.value
}
fun put(key: Int, value: Int) {
val node = cache[key]
if (node == null) {
val newNode = Node(key, value)
this.cache[key] = newNode
this.addNode(newNode)
this.count++
if (this.count > this.capacity) {
val tail = this.popTail()
tail?.let { this.cache.remove(it.key) }
this.count--
}
} else {
node.value = value
this.moveToHead(node)
}
}
/**
* 双向链表节点结构
*/
private data class Node(val key: Int = 0, var value: Int = 0) {
var prev: Node? = null
var next: Node? = null
}
private fun addNode(node: Node) {
node.prev = head
node.next = head.next
head.next?.prev = node
head.next = node
}
private fun removeNode(node: Node) {
val prev = node.prev
val next = node.next
prev?.next = next
next?.prev = prev
}
private fun moveToHead(node: Node) {
this.removeNode(node)
this.addNode(node)
}
private fun popTail(): Node? {
val result = tail.prev
result?.let { removeNode(it) }
return result
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* var obj = LRUCache(capacity)
* var param_1 = obj.get(key)
* obj.put(key,value)
*/