今天简单记录一下，利用Scala解答的一道LRU题目，原题为LeetCode的第146题，是一道设计LRU的题目。
题目详情
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
解答思路
这道题里，可以立即想到的是借助HashMap以及双向链表构建，更具体的分析可看LeetCode官方分析，在此不做赘述。
我的代码
对于Scala，由于其可以交叉使用Java的数据结构，因此在HashMap的构建部分，我也尝试了分别利用Scala自带的mutable.HashMap，以及Java当中的HashMap进行了比较，具体代码如下：
Scala的mutable.HashMap
import scala.collection.mutable.HashMap
class Node(var _key: Int, var _value: Int) {
var key = _key
var value = _value
var prev: Node = _
var next: Node = _
}
class DoubleLinked() {
var head: Node = new Node(-1, -1)
var tail: Node = new Node(-1, -1)
head.next = tail
tail.prev = head
def addNode(node: Node): Unit = {
head.next.prev = node
node.next = head.next
head.next = node
node.prev = head
}
def updateTail(node: Node): Unit = {
tail.prev = node
node.next = tail
}
}
class LRUCache(_capacity: Int) {
var cache: HashMap[Int, Node] = new HashMap[Int, Node]()
var dLinked = new DoubleLinked()
val capacity: Int = _capacity
def get(key: Int): Int = {
if (!cache.contains(key)) {
return -1
}
updateSurroundings(cache(key))
dLinked.addNode(cache(key))
cache(key).value
}
def put(key: Int, value: Int) {
if (cache.contains(key)) {
val node = cache(key)
node.value = value
updateSurroundings(node)
dLinked.addNode(node)
}
else {
val node = new Node(key, value)
dLinked.addNode(node)
if (dLinked.tail.prev == dLinked.head) {
dLinked.tail.prev=node
node.next=dLinked.tail
}
cache.put(key,node)
if(cache.size>capacity){
cache.remove(dLinked.tail.prev.key)
dLinked.updateTail(dLinked.tail.prev.prev)
dLinked.tail
}
}
}
def updateSurroundings(node: Node): Unit = {
if (node.next == dLinked.tail) {
dLinked.tail.prev = node.prev
}
node.prev.next = node.next
node.next.prev = node.prev
}
}
经提交测试，在LeetCode提交测试结果中，执行用时1628ms，占用内存82.9M
Java的HashMap
import java.util.HashMap
class Node(var _key: Int, var _value: Int) {
var key = _key
var value = _value
var prev: Node = _
var next: Node = _
}
class DoubleLinked() {
var head: Node = new Node(-1, -1)
var tail: Node = new Node(-1, -1)
head.next = tail
tail.prev = head
def addNode(node: Node): Unit = {
head.next.prev = node
node.next = head.next
head.next = node
node.prev = head
}
def updateTail(node: Node): Unit = {
tail.prev = node
node.next = tail
}
}
class LRUCache(_capacity: Int) {
var cache: HashMap[Int, Node] = new HashMap[Int, Node]()
var dLinked = new DoubleLinked()
val capacity: Int = _capacity
def get(key: Int): Int = {
var node:Node = cache.get(key)
if (node == null) {
return -1
}
updateSurroundings(node)
dLinked.addNode(node)
node.value
}
def put(key: Int, value: Int) {
if (cache.get(key)!=null) {
val node = cache.get(key)
node.value = value
updateSurroundings(node)
dLinked.addNode(node)
}
else {
val node = new Node(key, value)
dLinked.addNode(node)
if (dLinked.tail.prev == dLinked.head) {
dLinked.tail.prev=node
node.next=dLinked.tail
}
cache.put(key,node)
if(cache.size>capacity){
cache.remove(dLinked.tail.prev.key)
dLinked.updateTail(dLinked.tail.prev.prev)
dLinked.tail
}
}
}
def updateSurroundings(node: Node): Unit = {
if (node.next == dLinked.tail) {
dLinked.tail.prev = node.prev
}
node.prev.next = node.next
node.next.prev = node.prev
}
}
经提交测试，在LeetCode提交测试结果中，执行用时1456ms，占用内存83.9M
从上述的数据来看，两者运行时的占用内存相近，但是在速度上，使用Java的HashMap版本的代码，运行相对更快，所以有个猜想：如果在Scala代码中，直接使用Java原有的数据结构，是不是也同样会提高Scala代码的运行速度？
希望Scala方面的专家可以解答一下。