ImmutableDictionary和ImmutableSortedDictionary哪个更好？

Question

我听说.NET的System.Collections.Immutable集合被实现为平衡二叉树，以满足其不可变性限制，即使像Dictionary这样传统模拟哈希表的集合，也是通过使用GetHashCode的整数值作为排序关键字来实现的。

如果我有一个类型可以很容易地生成哈希码，并且比较成本很低（例如string或int），并且我不关心我的集合是否已排序，那么选择ImmutableSortedDictionary是否有意义，因为底层数据结构已经是排序的？

- Billy ONeal

---

如果我有一种类型，生成哈希码很便宜，比较也很便宜（例如字符串或整数），并且我不关心集合的排序。我认为你已经回答了自己的问题。保持简单。从另一个程序员的角度来看，如果发现排序字典的排序无用，会让人感到困惑，让人想知道为什么首先要使用它。 - Yuval Itzchakov

@YuvalItzchakov: ImmutableDictionary和ImmutableSortedDictionary（它们都是AVL树） - Billy ONeal

那么这有什么关系呢？如果排序不是问题，为什么不使用ImmutableDictionary呢？ - Yuval Itzchakov

@Yuval：因为ImmutableDictionary已经被排序了。它是按照GetHashCode的数值大小进行排序，而不是按照键类型提供的内在排序进行排序。 - Billy ONeal

@Yuval：这不是实现细节，就像字典是哈希表一样，这也不是实现细节。价值在于按T排序的版本在典型用例中可能比按GetHashCode排序的版本更快，就像字典通常比SortedDictionary更快一样。 - Billy ONeal

Answer 1

答案是 是的，在某些情况下，例如使用 Int32 键时，优选使用 ImmutableSortedDictionary 可以更有意义。在我的情况下，使用 Int32 键时，我发现 ImmutableSortedDictionary 是更好的选择。我运行了一个小型基准测试，使用了100万个元素：

• 按键升序插入100万个元素
• 更新100万个随机元素
• 扫描100万个元素，即迭代集合中的每个元素一次
• 读取100万个随机元素
• 删除100万个随机元素

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稍微快一些。请注意，插入是按键的升序一个接一个地完成的（因为它恰好符合我特定的用例）。

然而，您还应该考虑使用带有一些锁定的可变集合。写入可变的Dictionary<int, object>要快一个数量级。

- ZunTzu

Answer 2

基于哈希的集合在.NET上应该会更快，因为：

1. 它可以使用更高效的搜索树，专门针对int键，例如哈希trie或Patricia树。

2. 其内部循环几乎完全执行int比较，而不是通用比较。

然而，如果您需要更好的性能，通常最好切换到可变集合，如HashSet。

- J D

Answer 3

这并不是很重要。这篇博客文章中的时间复杂度表明，虽然使用Dictionary.Add比SortedDictionary.Add获得更好的性能（O(1) vs O(log n)），但ImmutableDictionary和ImmutableSortedDictionary的时间复杂度均为O(log n)

- Scott Chamberlain

---

1. 嗯，我对实际行为更感兴趣；例如，ImmutableArray在迭代时比ImmutableList快得多，但复杂度相同。
2. 当GetHashCode的值相同时，当然ImmutableDictionary会退回到线性行为...

- Billy ONeal

@BillyONeal 这篇文章没有明确说明ImmuteableSortedDictionary的最坏情况，我不确定它是O(n log n)还是O(n)。 - Scott Chamberlain