Java 有序映射

Java Ordered Map

提问by Whatsit

In Java, Is there an object that acts like a Map for storing and accessing key/value pairs, but can return an ordered list of keys and an ordered list of values, such that the key and value lists are in the same order?

在 Java 中，是否有一个对象像 Map 一样用于存储和访问键/值对，但可以返回一个有序的键列表和一个有序的值列表，这样键和值列表的顺序相同？

So as explanation-by-code, I'm looking for something that behaves like my fictitious OrderedMap:

因此，作为代码解释，我正在寻找行为类似于我虚构的 OrderedMap 的东西：

OrderedMap<Integer, String> om = new OrderedMap<>();
om.put(0, "Zero");
om.put(7, "Seven");

String o = om.get(7); // o is "Seven"
List<Integer> keys = om.getKeys();
List<String> values = om.getValues();

for(int i = 0; i < keys.size(); i++)
{
    Integer key = keys.get(i);
    String value = values.get(i);
    Assert(om.get(key) == value);
}

采纳答案by dmeister

The SortedMapinterface (with the implementation TreeMap) should be your friend.

该SortedMap的接口（与实施TreeMap的）应该是你的朋友。

The interface has the methods:

该接口具有以下方法：

• keySet()which returns a set of the keys in ascending order
• values()which returns a collection of all values in the ascending order of the corresponding keys

• keySet()它按升序返回一组键
• values()它以相应键的升序返回所有值的集合

So this interface fulfills exactly your requirements. However, the keys must have a meaningful order. Otherwise you can used the LinkedHashMapwhere the order is determined by the insertion order.

所以这个接口完全满足你的要求。但是，键必须具有有意义的顺序。否则，您可以使用LinkedHashMap，其中的顺序由插入顺序决定。

回答by John Feminella

Is there an object that acts like a Map for storing and accessing key/value pairs, but can return an ordered list of keys and an ordered list of values, such that the key and value lists are in the same order?

是否有一个对象像 Map 一样用于存储和访问键/值对，但可以返回一个有序的键列表和一个有序的值列表，这样键和值列表的顺序相同？

You're looking for java.util.LinkedHashMap. You'll get a list of Map.Entry<K,V>pairs, which always get iterated in the same order. That order is the same as the order by which you put the items in. Alternatively, use the java.util.SortedMap, where the keys must either have a natural orderingor have it specified by a Comparator.

您正在寻找java.util.LinkedHashMap。你会得到一个Map.Entry<K,V>对的列表，它们总是以相同的顺序迭代。该顺序与您放置项目的顺序相同。或者，使用java.util.SortedMap，其中键必须具有自然顺序或由 指定Comparator。

回答by bruno conde

I think the closest collection you'll get from the framework is the SortedMap

我认为您将从框架中获得的最接近的集合是SortedMap

回答by CJ F

I think the SortedMap interface enforces what you ask for and TreeMap implements that.

我认为 SortedMap 接口强制执行您的要求，而 TreeMap 实现了它。

http://java.sun.com/j2se/1.5.0/docs/api/java/util/SortedMap.htmlhttp://java.sun.com/j2se/1.5.0/docs/api/java/util/TreeMap.html

http://java.sun.com/j2se/1.5.0/docs/api/java/util/SortedMap.html http://java.sun.com/j2se/1.5.0/docs/api/java/util /TreeMap.html

回答by Vadzim

Since Java 6 there is also non-blocking thread-safe alternative to TreeMap. See ConcurrentSkipListMap.

从 Java 6 开始，还有TreeMap的非阻塞线程安全替代方案。请参阅ConcurrentSkipListMap。

回答by Vitalii Fedorenko

You can leverage NavigableMapinterface that may be accessed and traversed in either ascending or descending key order. This interface is intended to supersedethe SortedMap interface. The Navigable map is usually sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time.

您可以利用可按升序或降序键顺序访问和遍历的NavigableMap接口。此接口旨在取代SortedMap 接口。Navigable 映射通常根据其键的自然顺序进行排序，或者通过映射创建时提供的 Comparator 进行排序。

There are three most useful implementations of it: TreeMap, ImmutableSortedMap, and ConcurrentSkipListMap.

它有三个最有用的实现：TreeMap、ImmutableSortedMap和ConcurrentSkipListMap。

TreeMap example:

树图示例：

TreeMap<String, Integer> users = new TreeMap<String, Integer>();
users.put("Bob", 1);
users.put("Alice", 2);
users.put("John", 3);

for (String key: users.keySet()) {
  System.out.println(key + " (ID = "+ users.get(key) + ")");
}

Output:

输出：

Alice (ID = 2)
Bob (ID = 1)
John (ID = 3)

回答by VoNWooDSoN

LinkedHashMap maintains the order of the keys.

LinkedHashMap 维护键的顺序。

java.util.LinkedHashMap appears to work just like a normal HashMap otherwise.

否则，java.util.LinkedHashMap 似乎像普通的 HashMap 一样工作。

回答by Steffi Keran Rani J

I have used Simple Hash map, linked list and Collectionsto sort a Map by values.

我使用简单哈希映射、链表和集合按值对映射进行排序。

import java.util.*;
import java.util.Map.*;
public class Solution {

    public static void main(String[] args) {
        // create a simple hash map and insert some key-value pairs into it
        Map<String, Integer> map = new HashMap<String, Integer>();
        map.put("Python", 3);
        map.put("C", 0);
        map.put("JavaScript", 4);
        map.put("C++", 1);
        map.put("Golang", 5);
        map.put("Java", 2);
        // Create a linked list from the above map entries
        List<Entry<String, Integer>> list = new LinkedList<Entry<String, Integer>>(map.entrySet());
        // sort the linked list using Collections.sort()
        Collections.sort(list, new Comparator<Entry<String, Integer>>(){
        @Override
         public int compare(Entry<String, Integer> m1, Entry<String, Integer> m2) {
        return m1.getValue().compareTo(m2.getValue());
        }
      });
      for(Entry<String, Integer> value: list) {
         System.out.println(value);
     }
   }
}

The output is:

输出是：

C=0
C++=1
Java=2
Python=3
JavaScript=4
Golang=5

回答by Basil Bourque

tl;dr

tl;博士

To keep Map< Integer , String >in an order sorted by key, use either of the two classes implementing the SortedMap/NavigableMapinterfaces:

要保持Map< Integer , String >按键排序的顺序，请使用实现SortedMap/NavigableMap接口的两个类之一：

• TreeMap
• ConcurrentSkipListMap

• TreeMap
• ConcurrentSkipListMap

If manipulating the map within a single thread, use the first, TreeMap. If manipulating across threads, use the second, ConcurrentSkipListMap.

如果在单个线程中操作地图，请使用第一个TreeMap. 如果跨线程操作，请使用第二个，ConcurrentSkipListMap。

For details, see the table below and the following discussion.

有关详细信息，请参阅下表和以下讨论。

Details

细节

Here is a graphic table I made showing the features of the ten Mapimplementations bundled with Java 11.

这是我制作的图表，显示了Map与 Java 11 捆绑在一起的十个实现的特性。

The NavigableMapinterface is what SortedMapshould have been in the first place. The SortedMaplogically should be removed but cannot be as some 3rd-party map implementations may be using interface.

该NavigableMap接口是什么SortedMap应该已经摆在首位。在SortedMap逻辑上应该被删除，但不能作为某些第三方地图实现可以使用接口。

As you can see in this table, only two classes implement the SortedMap/NavigableMapinterfaces:

正如您在此表中看到的，只有两个类实现了SortedMap/NavigableMap接口：

• TreeMap
• ConcurrentSkipListMap

• TreeMap
• ConcurrentSkipListMap

Both of these keep keys in sorted order, either by their natural order (using compareTomethod of the Comparable(https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/Comparable.html) interface) or by a Comparatorimplementation you pass. The difference between these two classes is that the second one, ConcurrentSkipListMap, is thread-safe, highly concurrent.

无论是在有序这些保持键，或者通过它们的自然顺序（使用compareTo的方法Comparable（https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/ Comparable.html) 接口) 或通过Comparator您传递的实现。这两个类之间的区别在于，第二个类ConcurrentSkipListMap是线程安全的、高并发的。

See also the Iteration ordercolumn in the table below.

另请参阅下表中的迭代顺序列。

• The LinkedHashMapclass returns its entries by the order in which they were originally inserted.
• EnumMapreturns entries in the order by which the enum class of the key is defined. For example, a map of which employee is covering which day of the week (Map< DayOfWeek , Person >) uses the DayOfWeekenum class built into Java. That enum is defined with Monday first and Sunday last. So entries in an iterator will appear in that order.

• 该LinkedHashMap班由它们被顺序返回其条目最初插入。
• EnumMap按照定义键的枚举类的顺序返回条目。例如，关于哪个员工涵盖一周中的哪一天的地图 ( Map< DayOfWeek , Person >) 使用DayOfWeekJava 内置的enum 类。该枚举定义为首先是星期一，最后是星期日。因此，迭代器中的条目将按该顺序出现。

The other six implementations make no promise about the order in which they report their entries.

其他六个实现对它们报告条目的顺序没有保证。