解決方案預先添加到Scala中的LinkedHashMap？

Question

我有一個LinkedHashMap，我一直在以一種典型的方式使用：在結尾添加新的鍵值 對，並按插入順序訪問它們。不過，現在我有一個特殊情況，我需要在地圖的「頭部」添加對。我認爲LinkedHashMap源代碼中有一些功能 用於執行此操作，但它具有私有的 可訪問性。

我有一個解決方案，我創建一個新的地圖，添加一對，然後添加所有舊的映射。 在Java語法中：

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

它的工作原理。但這裏的問題是，我需要使我的主要數據結構 （this.map）var而不是val。

任何人都可以想出更好的解決方案嗎？請注意，我絕對需要由Map集合提供的快速查找功能 。預計的表現不是 這麼重要。

更一般地說，作爲一個Scala開發人員，在這種情況下，如果沒有可預見的併發需求，你會如何努力避免變種 ？ 你會創建你自己的LinkedHashMap版本嗎？坦率地說，這看起來很麻煩。

Answer 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) 

Answer 2

你看了一下LinkedHashMap的代碼嗎？該班有一個firstEntry字段，只需快速瀏覽updateLinkedEntries，創建LinkedHashMap的子類應該相對容易，該子類只會添加新方法prepend和updateLinkedEntriesPrepend，從而導致您需要的行爲，例如， （未測試）：

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 )); 
    } 

} 

其中，在斯卡拉2.9.0（是的，需要更新）結果

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

---

快速基準顯示之間的性能差異量級擴展內置類和「地圖重寫」的做法（我使用Debilski在「ExternalMethod」答案的代碼和我在「內建」 ）：

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 benchmarking template。