.net - 是否有HybridDictionary的通用版本？

Question

System.Collection.Specialized.HybridDictionary的描述是这样的:

Implements IDictionary by using a System.Collections.Specialized.ListDictionary while the collection is small, and then switching to a System.Collections.Hashtable when the collection gets large.

是否有一个等效的泛型实现？

Answer 1

从来没听说过。但是，是否已证明需要？哈希表没有太大的开销，即使对于非常小的N，使用普通哈希表也要比线性搜索更快。

我没有基准来证明这一点，但是仅通过比较算法，我得出结论，只要平均N> 6(对于字符串键或类似的非平凡哈希)，哈希表应比线性搜索更快。确实没有理由采用混合实现。

参数如下。在线性搜索中，平均必须将一半的元素与您的输入进行比较，即N/2。在哈希表中，无论输入大小如何，预期的比较次数为2(对于具有小于0.1的负载系数实际上接近1)。另外，必须计算哈希值。这将导致对输入的3种操作，加上可以忽略的很小的开销。因此，我们搜索3> N/2(哪个是N> 6)的确是哪个N.

请注意，上述计算实际上是错误的，因为对于这么少的元素，.NET的Dictionary的负载系数将远远小于0.1。因此，临界点实际上甚至更低。