下面是数据结构的描述：
它的操作就像一张普通的地图get, put, and remove方法，但有一个sort可以调用对地图进行排序的方法。然而，地图记得它的排序结构，因此后续调用 sort 可以更快（如果结构在调用之间没有改变太多）sort).
例如：
- 我打电话给
put方法 1,000,000 次。
- 我打电话给
sort method.
- 我打电话给
put方法再重复100次。
- 我打电话给
sort method.
我第二次打电话给sort方法应该是一个更快的操作，因为地图的结构没有太大变化。请注意，映射不必在调用之间保持排序顺序sort.
我知道这可能不可能，但我希望 O(1)get, put, and remove运营。就像是TreeMap为这些操作提供保证的 O(log(n)) 时间成本，但始终保持排序顺序（无sort方法）。
那么这个数据结构的设计是怎样的呢？
编辑 1 - 返回前 K 个条目
尽管我很高兴听到上述一般情况的答案，但我的用例变得更加具体：我不需要对整个事情进行排序；只是前 K 个元素。
用于高效返回的数据结构top-K哈希表（映射、字典）的条目
Thanks!
对于“O(1) 获取、放置和删除操作”，您本质上需要 O(1) 查找，这意味着哈希函数（如您所知），但良好哈希函数的要求通常会打破轻松排序的要求。 （如果您有一个哈希表，其中相邻值映射到同一个存储桶，那么对于大量公共数据，它会退化为 O(N)，这是您通常希望哈希函数避免的更糟糕的情况。）
我能想到如何让你完成 90% 的任务。在已排序的并行索引旁边设置一个哈希表。索引有干净部分（有序）和脏部分（无序）。索引会将键映射到值（或对存储在哈希表中的值的引用 - 无论在性能或内存使用方面适合您）。当您添加到哈希表时，新条目将被推到脏列表的后面。当您从哈希表中删除时，该条目将从索引的干净部分和脏部分中清空/删除。您可以对索引进行排序，它仅对脏条目进行排序，然后将它们合并到索引中已排序的“干净”部分。显然你可以迭代索引。
据我所知，除了删除操作之外，这在任何地方都为您提供了 O(1)，并且使用标准容器（至少 C++、Java 或 Python 提供的）实现起来仍然相当简单。它还为您提供了“第二种排序更便宜”的条件，只需对脏索引条目进行排序，然后让您进行 O(N) 合并。所有这一切的代价显然是索引的额外内存和使用索引时的额外间接性。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
