地圖成員的排序是否似乎是可靠的？

Question

當我創建一個不可變的地圖時，通過對Map()的標準調用或通過連接現有地圖創建這種方式，在所有我的測試中，我得到遍歷它的成員按添加的順序提供它們。這正是我需要對它們進行排序的方式，但文檔中沒有關於地圖成員排序可靠性的文字。

所以我想知道是否可以安全地期望標準Map按照添加的順序返回它的項目，或者我應該尋找其他的實現以及在這種情況下的哪些實現。

Answer 1

我不認爲它是安全的，不保留的順序從5個元素（斯卡拉2.9.1）開始：

scala> Map(1 -> 1, 2 -> 2, 3 -> 3, 4 -> 4, 5 -> 5) 
res9: scala.collection.immutable.Map[Int,Int] = 
    Map(5 -> 5, 1 -> 1, 2 -> 2, 3 -> 3, 4 -> 4) 

有了更大的映射的順序是完全「隨機」，嘗試Map((1 to 100) zip (1 to 100): _*)。

嘗試LinkedHashMap訂購條目和TreeMap以實現排序條目。

Answer 2

對於Map的訂單沒有承諾。在scalas收集包中有一個OrderedMap。該包中的值由隱含的Ordering排序。作爲quickfix，我建議你使用一個鍵列表來排列你的Map。

var keyOrdering = List[Int]() 
var unorderedMap = Map[Int, String]() 

unorderedMap += (1 -> "one") 
keyOrdering :+= 1 

編輯

你可以實現自己的Ordering，並把它傳遞給一個SortedMap爲好。

編輯＃2

一個簡單的例子是下面的：

scala> import scala.collection.SortedMap 
import scala.collection.SortedMap 

scala> implicit object IntOrdering extends Ordering[Int] 
    | def compare(a: Int, b: Int) = b - a 
    | } 
defined module IntOrdering 

scala> var sm = SortedMap[Int, String]() 
sm: scala.collection.SortedMap[Int,String] = Map() 

scala> sm += (1 -> "one") 

scala> sm += (2 -> "two") 

scala> println(sm) 
Map(2 -> two, 1 -> one) 

隱式排序被應用到密鑰，所以IntOrdering可能被施加到SortedMap[Int, Any]。

編輯＃3

自訂貨數據類型一樣在我的評論看起來是這樣的：

case class DataType[T](t: T, index: Int) 
object DataType{ 
    private var index = -1 
    def apply[T](t: T) = { index += 1 ; new DataType[T](t, index) 
} 

現在，我們需要改變排序：

implicit object DataTypeOrdering extends Ordering[DataType[_]] { 
    def compare(a: DataType[_], b: DataType[_]) = a.index - b.index 
} 

希望這是你期待我的答案的方式。

Answer 3

挖掘之後，我發現存在一個不可變的ListMap，其行爲與我想要的完全一樣，但根據this table，其性能只是很差。所以我寫了一個自定義的不可變實現，它應該對除了刪除之外的所有操作都有效地執行，並在其中線性執行。它確實需要更多的內存，因爲它有一個標準的Map和Queue作爲後盾，後者本身使用了List兩次，但在當前時代這不是問題，對。

import collection.immutable.Queue 

object OrderedMap { 
    def apply[A, B](elems: (A, B)*) = 
    new OrderedMap(Map(elems: _*), Queue(elems: _*)) 
} 
class OrderedMap[A, B](
    map: Map[A, B] = Map[A, B](), 
    protected val queue: Queue[(A, B)] = Queue() 
) extends Map[A, B] { 
    def get(key: A) = 
    map.get(key) 
    def iterator = 
    queue.iterator 
    def +[B1 >: B](kv: (A, B1)) = 
    new OrderedMap(
     map + kv, 
     queue enqueue kv 
    ) 
    def -(key: A) = 
    new OrderedMap(
     map - key, 
     queue filter (_._1 != key) 
    ) 
    override def hashCode() = 
    queue.hashCode 
    override def equals(that: Any) = 
    that match { 
     case that: OrderedMap[A, B] => 
     queue.equals(that.queue) 
     case _ => 
     super.equals(that) 
    } 
}