在Scala中，如何對垃圾收集進行不可變和可變集合和地圖的比較？

Question

我正在編寫一些代碼，涉及到通過大型結構遞歸時使用「小」（例如，短字符串或簡單案例類）對象的集合和映射，在每個點添加一個小的（通常是1，有時是一些）對象到集合或地圖。看起來好像使用可變集合和映射可以顯着提高速度，但我在定量評估差異時遇到了麻煩。

當我使用不可變數據結構時，Scala的垃圾回收會導致顯着的減速是否有意義？將使用可變數據結構解決這個問題嗎？

Answer 1

斯卡拉不可變集合驚人地高效。主要是因爲當一個結構發生變化時，許多結構被重用。

但是，如果你做了很多改變，可變結構可能更適合。實際上，這是Scala Collection API在內部許多地方所做的：使用可變數據結構來構建新東西，並且僅作爲最後一步，創建一個不可變的並返回它。

Answer 2

Scala可變數據結構通過預先分配內存來提高不可變數據結構的效率。它們更適合於許多插入（因此爲什麼它們是可變的）。看看該功能的實現+ =默認可變集合，一個HashMap，其中地圖擴展：

https://github.com/scala/scala/blob/v2.9.2/src/library/scala/collection/mutable/HashMap.scala#L84

def += (kv: (A, B)): this.type = { 
    val e = findEntry(kv._1) 
    if (e == null) addEntry(new Entry(kv._1, kv._2)) 
    else e.value = kv._2 
    this 
} 

HashMap中使用的HashTable實現一個可變的地圖，它定義的addEntry

https://github.com/scala/scala/blob/v2.9.2/src/library/scala/collection/mutable/HashTable.scala#L117

protected def addEntry(e: Entry) { 
    val h = index(elemHashCode(e.key)) 
    e.next = table(h).asInstanceOf[Entry] 
    table(h) = e 
    tableSize = tableSize + 1 
    nnSizeMapAdd(h) 
    if (tableSize > threshold) 
    resize(2 * table.length) 
} 

集合的大小加倍每次達到閾值時間。所以，如果你反覆添加一個條目到一個空的可變數據結構，你只需要調整log（n）次。我沒有深入研究過不變的數據結構實現，但我假設你將不得不調整每個插入。因此你的表現差距。