排序哈希表（map，dictionary）数据结构设计

问题描述

这是数据结构的描述：

它的运行方式是一个常规的地图， get ， put 和删除方法，但是有一个 sort 被称为排序地图。然而，映射记住它的排序结构，所以随后的排序调用可以快得多（如果结构在调用 sort



例如：

• 我调用 put 方法1,000,000次。
  


• 我调用 sort 方法。 br />


• 我再次呼叫 put 方法100次。
  


• 我打电话给 sort 方法。
  

第二次我调用 sort 方法应该是一个更快的操作，因为地图的结构没有太大变化。请注意，地图不需要在调用 sort 之间维护排序顺序。

我知道它可能不可能，但我希望O（1）获得， put 和删除操作。像这样的东西提供了保证的O（log （n））这些操作的时间成本，但始终保持排序顺序（no sort 方法）。

那么这个数据结构的设计是什么？

编辑1 - 返回顶部的K条目

我很高兴听到上面的一般情况的答案，我的用例已经变得更具体了：我不需要整个事情排序;只是最高的K元素。

谢谢！

解决方案

为什么你需要一个sort（）函数？

你可能想要和需要的是红黑树。

这些树自动通过比较器对输入进行排序。它们是复杂的，但具有优异的O（n）特性。将您的树条目作为关键字，使用哈希
地图作为字典，并获得您的数据结构。

在Java中，它实现为TreeMap作为SortedMap的实例。 / p>

Here's a description of the data structure:

It operates like a regular map with get, put, and remove methods, but has a sort method that can be called to sorts the map. However, the map remembers its sorted structure, so subsequent calls to sort can be much quicker (if the structure doesn't change too much between calls to sort).

For example:

• I call the put method 1,000,000 times.
  
• I call the sort method.
  
• I call the put method 100 more times.
  
• I call the sort method.
  

The second time I call the sort method should be a much quicker operation, as the map's structure hasn't changed much. Note that the map doesn't have to maintain sorted order between calls to sort.

I understand that it might not be possible, but I'm hoping for O(1) get, put, and remove operations. Something like TreeMap provides guaranteed O(log(n)) time cost for these operations, but always maintains a sorted order (no sort method).

So what's the design of this data structure?

Edit 1 - returning the top-K entries

Alhough I'd enjoy hearing the answer to the general case above, my use case has gotten more specific: I don't need the whole thing sorted; just the top K elements.

Data structure for efficiently returning the top-K entries of a hash table (map, dictionary)

Thanks!

解决方案

Why exactly do you need a sort() function ?
What do you perhaps want and need is a Red-Black Tree.

http://en.wikipedia.org/wiki/Red-black_tree

These trees are automatically sorting your input by a comparator you give. They are complex, but have excellent O(n) characteristics. Couple your tree entries as key with a hashmap as dictionary and you get your datastructure.

In Java it is implemented as TreeMap as instance of SortedMap.

这篇关于排序哈希表（map，dictionary）数据结构设计的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！