import java.util.concurrent.ConcurrentHashMap
class LRUCache constructor(private val capacity: Int) {
class DLinkedNode {
var key: String? = null
var value: Int = 0
var pre: DLinkedNode? = null
var post: DLinkedNode? = null
}
private val head = DLinkedNode()
private val tail = DLinkedNode()
private val map = ConcurrentHashMap<String, DLinkedNode>()
private var count = 0
init {
head.pre = null
head.post = tail
tail.pre = head
tail.post = null
}
fun get(key: String): Int {
val node = map[key] ?: return -1
moveToHead(node)
return node.value
}
fun put(key: String, value: Int) {
val node = map[key]
if(node != null){
node.value = value
moveToHead(node)
return
}
val newNode = DLinkedNode()
newNode.key = key
newNode.value = value
addNode(newNode)
if(++count > capacity){
map.remove(tail.pre!!.key)
removeNode(tail.pre!!)
count--
}
}
private fun moveToHead(node: DLinkedNode) {
removeNode(node)
addNode(node)
}
private fun addNode(node: DLinkedNode) {
head.post!!.pre = node
node.post = head.post
head.post = node
node.pre = head
}
private fun removeNode(node: DLinkedNode) {
val pre = node.pre
val post = node.post
pre!!.post = post
post!!.pre = pre
}
}
參考：LRU原理和Redis實(shí)現(xiàn)——一個(gè)今日頭條的面試題 - 知乎 (zhihu.com)
