Java Ordered Map

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?

So as explanation-by-code, I'm looking for something that behaves like my fictitious 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);
}

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

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

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

> 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?

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 ordering or have it specified by a Comparator.

LinkedHashMap maintains the order of the keys.

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

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

You can leverage NavigableMap interface that may be accessed and traversed in either ascending or descending key order. This interface is intended to supersede the 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.

There are three most useful implementations of it: TreeMap, ImmutableSortedMap, and 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)

tl;dr

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

• TreeMap
• ConcurrentSkipListMap

… or third-party implementations. Perhaps in Google Guava or Eclipse Collections (I’ve not checked).

If manipulating the map within a single thread, use the first, TreeMap. If manipulating across threads, use the second, 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 Map implementations bundled with Java 11.

The NavigableMap interface is the successor to SortedMap. The SortedMap logically should be removed but cannot be as some 3rd-party map implementations may be using interface.

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

• TreeMap
• ConcurrentSkipListMap

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

See also the Iteration order column in the table below.

• The LinkedHashMap class returns its entries by the order in which they were originally inserted.
• EnumMap returns 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 DayOfWeek enum class built into Java. That enum is defined with Monday first and Sunday last. So entries in an iterator will appear in that order.

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

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

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

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

I have used Simple Hash map, linked list and Collections to 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

Modern Java version of Steffi Keran's answer

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<>();
        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<Map.Entry<String, Integer>> list = new LinkedList<>(map.entrySet());
        // sort the linked list using Collections.sort()
        list.sort(Comparator.comparing(Map.Entry::getValue));
        list.forEach(System.out::println);
    }
}