Rud*_*ger 7 hashtable sorted hashmap map data-structures
这是数据结构的描述:
它的操作类似于带有get,put和remove方法的常规地图,但有一个sort方法可以调用以对地图进行排序.但是,映射会记住它的排序结构,因此后续的sort调用可以更快(如果结构在调用之间没有太大的变化sort).
例如:
put方法为1,000,000次.sort方法.put方法称为100次.sort方法.我第二次调用该sort方法应该是一个更快的操作,因为地图的结构没有太大变化.请注意,映射不必维护调用之间的排序顺序sort.
我明白,这也许是不可能的,但我希望为O(1) get,put和remove操作.像TreeMap这样的东西为这些操作提供了保证的O(log(n))时间成本,但始终保持排序顺序(无sort方法).
那么这个数据结构的设计是什么？
编辑1 - 返回前K个条目
虽然我很高兴听到上面一般情况的答案,但我的用例更加具体:我不需要对整个事情进行排序; 只是顶部的K元素.
谢谢!
对于"O(1)获取,放置和删除操作",你基本上需要O(1)查找,这意味着一个哈希函数(如你所知),但是一个好的哈希函数的要求经常打破要求,以便轻松排序.(如果你有一个哈希表,其中相邻的值映射到同一个桶,它会在许多常见数据上退化为O(N),这是一个更糟糕的情况,你通常希望哈希函数避免.)
我可以想到如何让你90%的方式.在排序的并行索引旁边设置哈希表.索引有一个干净的部分(有序)和一个脏部分(无序).索引会将键映射到值(或对哈希表中存储的值的引用 - 在性能或内存使用方面适合您).添加到哈希表时,新条目将被推送到脏列表的后面.从哈希表中删除时,该条目将从索引的干净和脏的部分中删除/删除.您可以对索引进行排序,该索引仅对脏条目进行排序,然后将它们合并到索引的已排序的"干净"部分中.显然你可以迭代索引.
据我所知,除了remove操作之外,这给你O(1),并且使用标准容器(至少由C++,Java或Python提供)仍然相当简单.它还为您提供了"第二种更便宜"的条件,只需要对脏索引条目进行排序,然后让您进行O(N)合并.所有这些的成本显然是索引的额外内存和使用它时的额外间接.
为什么需要 sort() 函数？
您可能想要和需要的是一棵红黑树。
http://en.wikipedia.org/wiki/Red-black_tree
这些树会根据您提供的比较器自动对您的输入进行排序。它们很复杂，但具有出色的 O(n) 特性。将树条目作为键与哈希图作为字典结合起来，就得到了数据结构。
在 Java 中，它被实现为 TreeMap 作为 SortedMap 的实例。