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

Question

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

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

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

这在大型 key 集上变得非常昂贵(如此处所述:Iterating through a LinkedHashMap in reverse order)。

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

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

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

Answer 1

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

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

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

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