什么是TrieMap,与HashMap相比有哪些优缺点？

Question

Scala有一个TrieMap集合.

什么是TrieMap,与HashMap相比有哪些优缺点？

Answer 1

Scala TrieMap是基于特里结构的并发可伸缩地图实现.与普通的trie映射不同,Scala TrieMap具有高效,无阻塞,O(1)时间snapshot操作(以及稍微优化readOnlySnapshot)的操作.

a的绝对性能TrieMap略低于JDK8 ConcurrentHashMap,但其优点是它提供了一致的迭代器,这是并发数据结构通常所不具备的.这意味着您可以在一个时间点捕获特里结构中的所有元素(此处的性能数字和分析).您应该使用TrieMapif,如果您需要一次捕获所有元素(例如,在UI中列出其所有元素,或者一致地分析它们).

Answer 2

TrieMaps是使用trie数据结构的地图,其基本上是浅树.例如,如果您有32位哈希,则将其分解为多个部分,例如4次8,并在树的每个级别分支到最多256个子树.显然,由于哈希的固定大小(假设碰撞很少),这给出了O(1)性能.

可以有效地使trie结构不可变,重新使用trie的结构来创建具有添加或移除元素的新trie.GC对时间/内存影响的相对性能在很大程度上取决于实现和负载,而不是尝试一个通用的答案,我会说运行一个基准.虽然对于没有不变性要求的单个线程,经典的hashmap通常会产生更好的平均性能和更差的最坏情况性能.

作为旁注我会提到,因为trieMap也使用哈希它也是一个哈希映射,因此我建议将其称为trie支持的哈希映射与阵列支持的哈希映射.