Collections中的哪种数据结构可以有效地存储键值Map，保持插入顺序并允许 * 有效 * 的反向遍历？数据结构必须来自原始的Java Collections，因此使用Apache Commons库是不可能的。
我目前使用的是LinkedHashMap，这是理想的，因为它保留了插入顺序，允许键值Map，并且具有在O（1）时间内操作的add（）和remove（）方法。然而，问题是，要反转LinkedHashMap，每次添加新键时，我都需要执行set-copy：
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，但我不确定这会有多有效。
在几千个键值Map中，哪种方法的性能最好？还有什么方法我没有列出，这将是一个更好的选择？
2条答案
按热度按时间7dl7o3gd1#
你必须只有一个变量吗？如果你想经常查询它们，通常的方法是在不同的结构中多次使用相同的数据。
添加/删除的成本更高，但选择可以少得多的成本。
在你的例子中，你可以有颠倒顺序的LinkedList（在零位置添加是O（1））和LinkedHashMap。
理想情况下，你应该用这两个变量和“add/remove等"方法创建自己的类，以确保它是一致的。
deyfvvtc2#
从Java 21开始，
LinkedHashMap满足了所有要求，因为它添加了一个reversed方法。字符串
Javadocs
public SequencedMap<K,V> reversed()个返回此Map的逆序视图。返回视图中Map的相遇顺序与此Map中Map的相遇顺序相反。[...]