Scala - TrieMap vs Vector

Question

我讀到TrieMap在scala中是基於數組映射trie，比如說讀取位映射向量trie。

這兩個darastructures是否都支持同一個散列樹思想或者它們之間有區別？

Answer 1

有一些相似之處，但根本上它們是不同的數據結構：

矢量

沒有參與Vector散列。索引直接描述了樹中的路徑。當然，矢量的佔用索引是連續的。

不顧所有在生產實施scala.collection.immutable.Vector顯示指針的詭計，在除了在一個水平的最後一項的載體每一個分支節點具有相同數量的兒童（在階Vector的殼體32） 。這允許使用簡單的位操作進行索引。缺點是矢量中間的拼接元素很昂貴。

HashMap的

在HashTrieMap，哈希碼是路徑到樹。這意味着被佔領的指數是不是連續的，而是均勻分佈的。這需要樹分支節點的不同編碼。

在HashTrieMap，分支節點高達 32名兒童（但如果你有一個非常不好的哈希碼分佈是完全可能的，只有一個孩子的分支節點）。有一個Int位圖來編碼哪個孩子對應哪個位置，這意味着在HashTrieMap中查找值需要頻繁調用Integer.bitCount，幸運的是現代CPU上固有的CPU。

這是一個有趣的項目，讓你看看Scala的數據結構，如Vector和HashMap的內部：在使用本項目產生https://github.com/stanch/reftree

在這個答案中的圖像。