结构 k => v
(k
和 v
是 >=0
整数)其中所有 k
是唯一的,而 v
可能相等(k1 => v
和 k2 => v
)应该排序v
值的升序,例如:
让我们有 [35 => 1, 23 => 4, 9 => 9, 2 => 14]
并想插入一对新的 20 => 5
,那么结果将是 [35 => 1, 23 => 4, 20 => 5, 9 => 9, 2 => 14]
。
为了根据一些输入数据创建它并从左侧以“一个接一个”的方式进一步迭代它,我可以使用 Java 中最快的结构是什么。 SortedHashMap
?
最佳答案
前段时间遇到过类似的情况;我同时使用了几个 map :
A
HashMap<K, P>
M,其中 P 是对类型,以便能够通过它们的键找到对。A
TreeMap<P, P>
S,带有一个先按值再按键排序的比较器,以始终提供正确的排序顺序。
通过并行维护两个结构,可以始终对您的对进行排序,而不必使用键作为排序值。
添加一对:
M.put(key, pair);
S.put(pair, pair);
通过 key 获取一对:
M.get(key);
删除一对:
P pair = M.get(key);
M.remove(key);
S.remove(pair);
要获得对的排序列表:
S.keySet();
核心操作的平均复杂度是:
- 地址:
O(logn)
(TreeMap
) - 获取:
O(1)
(HashMap
) - 删除:
O(logn)
(TreeMap
)
关于具有唯一键的排序对列表的 Java 结构建议,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11967172/