应该更喜欢ImmutableDictionary还是ImmutableSortedDictionary？

Question

我听说.NET System.Collections.Immutable集合是作为平衡二叉树实现的,以便Dictionary通过使用整数值GetHashCode作为排序键来满足它们的不变性约束,甚至传统上模拟散列表的集合.

如果我有一个类型,它是便宜生成一个散列码,以及对于便宜的比较(如string或int),我不关心我收集整理的烦躁,这将是有意义的喜欢ImmutableSortedDictionary,因为底层数据结构是否仍然排序？

Answer 1

答案是肯定的,ImmutableSortedDictionary在某些条件下,例如使用Int32键,可能更有意义.

在我的情况下,通过Int32键我发现这ImmutableSortedDictionary是一个更好的选择.

我使用了100万件物品运行了一个小基准:

• 按键的升序插入1,000,000个项目
• 更新1,000,000个随机物品
• 扫描1,000,000个项目,即在集合中的每个项目上迭代一次
• 阅读1,000,000个随机项目
• 删除1,000,000个随机项

ImmutableDictionary <int,object>

Insert: 2499 ms
Update: 7275 ms
Scan:    385 ms
Read:    881 ms
Delete: 5037 ms

ImmutableSortedDictionary <int,object>

Insert: 1808 ms
Update: 4928 ms
Scan:    246 ms
Read:    732 ms
Delete: 3522 ms

ImmutableSortedDictionary比ImmutableDictionary所有操作都快一点.请注意,插入是按键的升序一次一个项目完成的(因为它恰好符合我的特定用例).

但是,您还应该考虑使用带有一些锁定的可变集合.写入mutable Dictionary<int, object>的速度要快一个数量级.

Answer 2

这应该不重要。这篇博文的时间复杂度表明，虽然您确实获得了Dictionary.Add比SortedDictionary.Add( O(1)vs O(log n))更好的性能ImmutableDictionary，并且ImmutableSortedDictionary时间复杂度为O(log n)