1

我有一个 LinkedHashMap，我一直在以一种典型的方式使用它：在末尾添加新的键值对，并按插入顺序访问它们。但是，现在我有一个特殊情况，我需要将对添加到地图的“头部”。我认为 LinkedHashMap 源中有一些功能可以做到这一点，但它具有私有可访问性。

我有一个解决方案，我创建一个新映射，添加对，然后添加所有旧映射。在 Java 语法中：

newMap.put(newKey, newValue) 
newMap.putAll(this.map)
this.map = newMap

有用。但这里的问题是我需要将我的主要数据结构（this.map）设为 var 而不是 val。

谁能想到更好的解决方案？请注意，我绝对需要 Map 集合提供的快速查找功能。前置的性能并不是什么大问题。

更一般地说，作为一名 Scala 开发人员，在这种情况下，假设没有可预见的并发需求，您将如何努力避免使用 var？您会创建自己的 LinkedHashMap 版本吗？坦率地说，看起来很麻烦。

4

2 回答 2

1

你看过LinkedHashMap的代码吗？该类有一个 field firstEntry，只需快速浏览一下，创建一个仅添加新方法并导致您需要的行为updateLinkedEntries的子类应该相对容易，例如（未测试）：LinkedHashMapprependupdateLinkedEntriesPrepend

private def updateLinkedEntriesPrepend(e: Entry) {
    if (firstEntry == null) { firstEntry = e; lastEntry = e }
    else {
        val oldFirstEntry = firstEntry
        firstEntry = e
        firstEntry.later = oldFirstEntry
        oldFirstEntry.earlier = e
    }
}

这是我快速拼凑的示例实现（也就是说，没有经过彻底测试！）：

class MyLinkedHashMap[A, B] extends LinkedHashMap[A,B] {

  def prepend(key: A, value: B): Option[B] = {
    val e = findEntry(key)
    if (e == null) {
      val e = new Entry(key, value)
      addEntry(e)
      updateLinkedEntriesPrepend(e)
      None
    } else {
      // The key already exists, so we might as well call LinkedHashMap#put
      put(key, value)
    }
  }

  private def updateLinkedEntriesPrepend(e: Entry) {
    if (firstEntry == null) { firstEntry = e; lastEntry = e }
    else {
      val oldFirstEntry = firstEntry
      firstEntry = e

      firstEntry.later = oldFirstEntry
      oldFirstEntry.earlier = firstEntry
    }
  }

}

像这样测试：

object Main {

 def main(args:Array[String]) {
    val x = new MyLinkedHashMap[String, Int]();

    x.prepend("foo", 5)
    x.prepend("bar", 6)
    x.prepend("olol", 12)

    x.foreach(x => println("x:" + x._1 + " y: " + x._2  ));
  }

}

其中，在 Scala 2.9.0 上（是的，需要更新）导致

x:olol y: 12
x:bar y: 6
x:foo y: 5

一个快速的基准测试显示了扩展的内置类和“映射重写”方法之间的性能差异数量级（我使用了 Debilski 在“ExternalMethod”中的答案和我在“BuiltIn”中的答案）：

 benchmark length        us linear runtime
ExternalMethod     10   1218.44 =
ExternalMethod    100   1250.28 =
ExternalMethod   1000  19453.59 =
ExternalMethod  10000 349297.25 ==============================
       BuiltIn     10      3.10 =
       BuiltIn    100      2.48 =
       BuiltIn   1000      2.38 =
       BuiltIn  10000      3.28 =

基准代码：

  def timeExternalMethod(reps: Int) = {
    var r = reps
    while(r > 0) {
      for(i <- 1 to 100) prepend(map, (i, i))
      r -= 1
    }
  }

  def timeBuiltIn(reps: Int) = {
    var r = reps
    while(r > 0) {
      for(i <- 1 to 100) map.prepend(i, i)
      r -= 1
    }
  }

使用Scala 基准测试模板。

于 2012-07-08T20:10:39.910 回答
1

这会起作用，但也不是特别好：

import scala.collection.mutable.LinkedHashMap

def prepend[K,V](map: LinkedHashMap[K,V], kv: (K, V)) = {
  val copy = map.toMap
  map.clear
  map += kv
  map ++= copy
}

val map = LinkedHashMap('b -> 2)
prepend(map, 'a -> 1)
map == LinkedHashMap('a -> 1, 'b -> 2)
于 2012-07-08T20:12:20.807 回答