C#:字典按键排序~~(1)查找

Question

没有找到答案.

我喜欢KeyedCollection,因为它保持了插入顺序并且具有~O(1)个键查找时间.

现在我正在寻找一个类似的类型,它将对键而不是插入顺序进行排序.

SortedDictionary就是这样做的,但是实现与我想要的完全相反.插入是O(1),查找O(log n).但是,我想查找~O(1)(例如哈希表),插入可以是O(log n)(二叉树？).

这存在吗？不应该是明智的实施......

谢谢

Answer 1

.NET BCL中没有提供您正在寻找的内容的数据结构.也许有第三方解决方案.

在大多数情况下,O(log n)就足够了.如果您尝试实现自己的数据结构,则可能会进行微优化.

但是,最快捷的方法可能是简单地声明一个同时具有Dictionary和SortedDictionary作为私有成员的新类.对于所有读取方法,您可以选择更有效的字典来返回值.对于所有写入方法,您将处理两个内部字典,并注意它们保持同步.但这可能不是最节省内存的方法.但是如果你想在这里优化,你必须重新实现散列表的大部分功能.