具有唯一键的排序对列表的 Java 结构建议

Question

结构 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?

Answer 1

前段时间遇到过类似的情况；我同时使用了几个 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 )