是否有HybridDictionary的通用版本？

Question

System.Collection.Specialized.HybridDictionary的描述如下:

在集合较小时使用System.Collections.Specialized.ListDictionary实现IDictionary,然后在集合变大时切换到System.Collections.Hashtable.

是否有等效的通用实现？

Answer 1

从来没听说过。然而，是否有经过证实的需求呢？哈希表没有很大的开销，即使对于非常小的N，使用普通哈希表应该比线性搜索更快。

编辑我没有基准来证明这一点，但仅通过比较算法，我得出结论，平均而言，只要N > 6（对于字符串键或类似的非平凡哈希），哈希表就应该比线性搜索更快，所以实际上没有混合实施的原因。

论证如下。在线性搜索中，平均有一半的元素必须与输入进行比较，即N  / 2。在哈希表中，我们知道，无论输入大小如何，预期的比较次数都是 2（对于具有负载系数小于 0.1，这实际上接近 1)。此外，还必须计算哈希值。这会导致您的输入需要进行 3 次操作，再加上非常小的可以忽略不计的开销。因此，我们搜索哪个N满足 3 > N  / 2，即N  > 6。

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