c#:字典按键排序,使用~O(1)查找
本文关键字:查找 使用 字典 排序 | 更新日期: 2023-09-27 17:49:41
没有找到答案。
我喜欢KeyedCollection,因为它保持插入顺序,并且有~O(1)键查找时间。
现在我正在寻找一个类似的类型,将排序键而不是插入顺序。
SortedDictionary确实做到了这一点,但是实现与我想要的完全相反。插入是O(1),查找是O(log n).然而,我希望查找~O(1)(例如哈希表),插入可以是O(log n)(二叉树?)。
这个存在吗?不应该是硬实现明智的…
谢谢
. net BCL中没有提供您所寻找的数据结构。也许有第三方的解决方案。
在大多数情况下,O(log n)就足够了。如果你尝试实现你自己的数据结构,你可能是在进行微优化。
然而,最快的方法可能是简单地声明一个新类,它将Dictionary和SortedDictionary作为私有成员。对于所有read方法,您都应该选择更有效的字典来返回值。对于所有write方法,您都要处理两个内部字典,并注意它们保持同步。但是,这可能不是最有效地利用内存的方法。但如果你想在这里优化,你必须重新实现哈希表的大部分功能。
我认为OrderedBag可能是你想要的:
频繁插入已排序集合