排序哈希表(map、dictionary)数据结构设计 [英] Sorted hash table (map, dictionary) data structure design
问题描述
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 hash map as dictionary and you get your datastructure.
In Java it is implemented as TreeMap as instance of SortedMap.
这篇关于排序哈希表(map、dictionary)数据结构设计的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!