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

Question

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

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

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

这在大型密钥集上变得非常昂贵（如此处所述：Iterating through a LinkedHashMap in reverse order）。

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

我唯一的其他想法是使用 Entry 对象的 ArrayList，但是我不确定这会有多有效。

在几千个键值映射中，这些方法中的哪一个总体上表现最好？有没有我没有列出的更好的替代方法？

Answer 1

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

add/remove的成本更高，但选择成本会低很多。

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

理想情况下，您应该使用这两个变量和方法创建自己的 class，例如 "add/remove etc."，以确保它是一致的。

Which data structure should I use to support key-value mappings, reverse iteration and insertion ordering?