我应该使用哪种数据结构来支持键值映射、反向迭代和插入顺序？

Question

集合中的哪种数据结构可以有效地存储键值映射、保留插入顺序并允许高效反向遍历？数据结构必须来自原始的Java Collections，因此使用Apache Commons库是不可能的。

我目前正在使用 LinkedHashMap，这是理想的选择，因为它保留插入顺序，允许键值映射，并且具有在 O(1) 时间内运行的 add() 和 remove() 方法。然而问题是，要反转 LinkedHashMap，我需要在每次添加新键时执行设置复制：

List<Integer> reverseKeys = new ArrayList<>(keys);
Collections.reverse(reverseKeys);

对于大型键集来说，这变得非常昂贵（正如这里提到的：以相反的顺序迭代LinkedHashMap）。

或者，我可以使用带有自定义比较器的 TreeMap 来保留插入顺序，但这似乎很浪费，因为 add() 和 remove() 将在 O(n) 时间内运行。这种方法的好处是 TreeMap 具有 DescendingKeySet() 方法，可以实现高效的反向遍历。

我唯一的另一个想法是使用 Entry 对象的 ArrayList，但是我不确定这有多高效。

在数千个键值映射中，哪种方法总体表现最佳？还有哪些我没有列出的方法是更好的选择？

Answer 1

你必须只有一个变量吗？如果您想经常查询它们，常见的方法是在不同的结构中多次使用相同的数据。

添加/删除成本更高，但选择成本要低得多。

在你的情况下，你可以以相反的顺序使用 LinkedList （在零位置添加是 O(1) ）和 LinkedHashMap 。

理想情况下，您应该使用这两个变量和方法（例如“添加/删除等”）创建自己的类，以确保其一致。

Answer 2

从 Java 21 开始，

LinkedHashMap

满足您的所有要求，因为添加了

reversed

方法。

SequencedMap<K, V> map = new LinkedHashMap<>();

// Add elements to the map here

SequencedMap<K, V> reversedMap = map.reversed();

Java文档

public SequencedMap<K,V> reversed()

返回此地图的逆序视图。返回视图中映射的遇到顺序与此映射中映射的遇到顺序相反。 […]