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

Question

一个结构k=

让我们有[35=

我可以使用Java中最快的结构是什么，以便根据一些输入数据创建它，并从左边以“一个接一个”的方式进一步迭代它。SortedHashMap？




Answer 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;

Answer 2

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

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

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

如果性能是一个大问题，那么您应该考虑实现自己的结构。有很多种可能性可以做到这一点，我们不能说什么是最快的。这取决于您希望执行的操作的频率。

Answer 3

不久前，我遇到了类似的情况；我并行使用了两张地图：

>

AHashMap

一个树形图

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

要添加一对：

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）