1

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

4

3 回答 3

1

我不认为有一个现有的结构。

SortedMap 不适合您，因为它使用键而不是值进行排序。

我将使用 HashMap 并在将 entrySet 复制到列表中的附加方法中实现排序。该列表将使用比较值的自定义比较器进行排序。

如果性能在这里很重要，那么您应该考虑实现自己的结构。有很多可能性可以做到这一点，但不能说什么是最快的。这取决于您想要执行的操作频率。

于 2012-08-15T10:00:44.993 回答
1

前段时间我也遇到过类似的情况；我并行使用了几张地图：

  • A HashMap<K, P>M，其中 P 是对类型，以便能够通过它们的键找到对。

  • A TreeMap<P, P>S，带有一个比较器，它首先按值排序，然后按键排序，以始终提供正确的排序顺序。

通过并行维护这两个结构，可以始终对您的对进行排序，而不必使用键作为排序值。

添加一对：

M.put(key, pair);
S.put(pair, pair);

要通过密钥获取一对：

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)
于 2012-08-15T10:09:53.420 回答
1

如果您不需要增量构建，我会这样做：

List<Pair> pairs = ...;
Collections.sort(pairs, new Comparator<Pair>() {
    @Override public int compare(Pair p1, Pair p2) {
        return p1.v - p2.v;
    }
}
LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
map.addAll(pairs); // retains insertion order
return map;
于 2012-08-15T10:10:36.783 回答