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

标签 java sorting hashmap sortedmap

结构 k => v(kv>=0 整数)其中所有 k 是唯一的,而 v 可能相等(k1 => vk2 => 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/

相关文章:

java - 无法将文件内容正确保存到 HashMap 中

java - 考虑到输入和输出,如何使用 python 执行 java 程序

java - 调试 "Comparison method violates its general contract!"

java - 如何从流计算 map ,然后检查 map 值的属性?

java - 打印存储在散列的散列中的元素

java - java中合并多个Map并用不同的key区分它们的值

java - JLine3 - 自动建议未按预期工作

java - 封装什么不变?

php - 使用匿名函数按两个对象属性对数组进行排序

sorting - block 排序算法