scala 什么是 TrieMap，与 HashMap 相比，它的优点/缺点是什么？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/29499381/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What is a TrieMap and what is its advantages/disadvantages compared to a HashMap?
提问by Pinch
Scala has a TrieMap collection.
Scala 有一个 TrieMap 集合。
What is a TrieMap and what is its advantages/disadvantages compared to a HashMap?
什么是 TrieMap，与 HashMap 相比，它的优点/缺点是什么？
回答by axel22
A Scala TrieMapis a trie-based concurrentscalable map implementation. Unlike normal trie maps, a Scala TrieMaphas an efficient, non-blocking, O(1) time snapshotoperation (and a slightly optimized readOnlySnapshot) operation.
ScalaTrieMap是一种基于 trie 的并发可扩展映射实现。与普通的 trie 映射不同，ScalaTrieMap具有高效的、非阻塞的、O(1) 时间snapshot操作（和稍微优化的readOnlySnapshot）操作。
Absolute performance of a TrieMapis slightly below the JDK8 ConcurrentHashMap, but the advantage is that it provides consistent iterators, something that concurrent data structures typically do not have. This means that you can capture all the elements in the trie at one point in time (performance numbers and analysis here). You should use the TrieMapif you need to capture all the elements at once (e.g. to list all its elements in the UI, or to consistently analyze them).
a 的绝对性能TrieMap略低于 JDK8 ConcurrentHashMap，但优点是它提供了一致的迭代器，这是并发数据结构通常没有的。这意味着您可以在一个时间点捕获特里树中的所有元素（性能数据和分析在这里）。您应该使用TrieMap，如果你需要捕获所有的元素在一次（例如列出在用户界面中的所有元素，或将始终如一地对它们进行分析）。
回答by Meir Maor
TrieMaps are Maps using trie data structure which are essentially shallow trees. For example, If you have a 32 bit hash you break it up into sections for example 4 times 8 and at every level of the tree you branch to up to 256 sub trees. Obviously this gives O(1) performance due to the fixe size of hash(assuming few collisions).
TrieMaps 是使用 trie 数据结构的 Maps，本质上是浅树。例如，如果您有一个 32 位散列，则将其分成多个部分，例如 4 次 8 次，并且在树的每个级别上最多分支到 256 个子树。显然，由于哈希的固定大小（假设很少发生冲突），这提供了 O(1) 性能。
A trie structure can be made immutable efficently, reusing the structure of a trie to create a new trie with an added or removed element. The relative performance in time/memory affect on GC depend greatly on implementation and load so rather then attempt a generic answer I would say run a benchmark. Though for a single thread with no immutability requirement a classic hashmap will normally produce better average performance and inferior worst case performance.
可以有效地使特里结构不可变，重用特里的结构来创建具有添加或删除元素的新特里。对 GC 的时间/内存影响的相对性能在很大程度上取决于实现和负载，因此与其尝试通用答案，不如说运行基准测试。尽管对于没有不变性要求的单线程，经典的哈希图通常会产生更好的平均性能和较差的最坏情况性能。
As a side note I will mention since the trieMap also uses a hash it is also a hashmap so I would recommend calling it a trie backed hashmap vs array backed hashmap.
作为旁注，我会提到，因为 trieMap 也使用散列，它也是一个散列图，所以我建议将其称为 trie 支持的散列图与数组支持的散列图。
