Java Class that implements Map and keeps insertion order?

Question

I'm looking for a class in java that has key-value association, but without using hashes. Here is what I'm currently doing:

1. Add values to a Hashtable.
2. Get an iterator for the Hashtable.entrySet().
3. Iterate through all values and:
   1. Get a Map.Entry for the iterator.
   2. Create an object of type Module (a custom class) based on the value.
   3. Add the class to a JPanel.
4. Show the panel.

The problem with this is that I do not have control over the order that I get the values back, so I cannot display the values in the a given order (without hard-coding the order).

I would use an ArrayList or Vector for this, but later in the code I need to grab the Module object for a given Key, which I can't do with an ArrayList or Vector.

Does anyone know of a free/open-source Java class that will do this, or a way to get values out of a Hashtable based on when they were added?

Thanks!

• John Gardner: You don't need to use entryset/map.entry. you can iterate over keys and values by using hashtable.keys as an enumeration or by using hashtable.keyset.iterator.
• Joachim Sauer: I took the liberty to change the title, since not using hashes is not actually the problem, but keeping the insertion order.
• Basil Bourque: Similar Question, Java Ordered Map

Answer 1

I suggest a LinkedHashMap or a TreeMap. A LinkedHashMap keeps the keys in the order they were inserted, while a TreeMap is kept sorted via a Comparator or the natural Comparable ordering of the keys.

Since it doesn't have to keep the elements sorted, LinkedHashMap should be faster for most cases; TreeMap has O(log n) performance for containsKey, get, put, and remove, according to the Javadocs, while LinkedHashMap is O(1) for each.

If your API that only expects a predictable sort order, as opposed to a specific sort order, consider using the interfaces these two classes implement, NavigableMap or SortedMap. This will allow you not to leak specific implementations into your API and switch to either of those specific classes or a completely different implementation at will afterwards.

• Cory Kendall: This won't work for me because, as per javadocs, this only gives ordered values (through the values() call). Is there a way to get ordered Map.Entry instances?
• Michael Myers: @CoryKendall: Does TreeMap not work? It is supposed to be sorted by keys, not by values.
• Muundruul: Please note: The sorting of a TreeMap is based on the natural order of the keys: "The map is sorted according to the natural ordering of its keys". The LinkedHashMap is sorted bij insert order. Big difference!
• navkast: I believe LinkedHashMap does not implement NavigableMap or SortedMap.
• Michael Myers: @AlexR: That is only true if the LinkedHashMap was created using the special constructor which is provided for that purpose. By default, iteration is in insertion order.

Answer 2

LinkedHashMap will return the elements in the order they were inserted into the map when you iterate over the keySet(), entrySet() or values() of the map.

Map<String, String> map = new LinkedHashMap<String, String>();
map.put("id", "1");
map.put("name", "rohan");
map.put("age", "26");
for (Map.Entry<String, String> entry : map.entrySet()) {
 System.out.println(entry.getKey() + " = " + entry.getValue());
}

This will print the elements in the order they were put into the map:

id = 1
name = rohan 
age = 26 

• Abhijit Sarkar: Good straightforward answer. I didn't find this single line in the LinkedHashMap Javadoc.

Answer 3

If an immutable map fits your needs then there is a library by google called guava (see also guava questions)

Guava provides an ImmutableMap with reliable user-specified iteration order. This ImmutableMap has O(1) performance for containsKey, get. Obviously put and remove are not supported.

ImmutableMap objects are constructed by using either the elegant static convenience methods of() and copyOf() or a Builder object.

Answer 4

You can use LinkedHashMap to main insertion order in Map

The important points about Java LinkedHashMap class are:

1. It contains only unique elements.

2. A LinkedHashMap contains values based on the key.

3. It may have one null key and multiple null values.

4. It is same as HashMap instead maintains insertion order

   public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> 
   

But if you want sort values in map using User-defined object or any primitive data type key then you should use TreeMap For more information, refer this link

• swpalmer: "It contains only unique elements" is misleading - you can have the same value object in the map associated with different keys. It is the keys that must be unique.

Answer 5

You can maintain a Map (for fast lookup) and List (for order) but a LinkedHashMap may be the simplest. You can also try a SortedMap e.g. TreeMap, which an have any order you specify.

Answer 6

Either You can use LinkedHashMap<K, V> or you can implement you own CustomMap which maintains insertion order.

You can use the Following CustomHashMap with the following features:

• Insertion order is maintained, by using LinkedHashMap internally.
• Keys with null or empty strings are not allowed.
• Once key with value is created, we are not overriding its value.

HashMap vs LinkedHashMap vs CustomHashMap

interface CustomMap<K, V> extends Map<K, V> {
 public boolean insertionRule(K key, V value);
}
@SuppressWarnings({ "rawtypes", "unchecked" })
public class CustomHashMap<K, V> implements CustomMap<K, V> {
 private Map<K, V> entryMap;
 // SET: Adds the specified element to this set if it is not already present.
 private Set<K> entrySet;
 public CustomHashMap() {
 super();
 entryMap = new LinkedHashMap<K, V>();
 entrySet = new HashSet();
 }
 @Override
 public boolean insertionRule(K key, V value) {
 // KEY as null and EMPTY String is not allowed.
 if (key == null || (key instanceof String && ((String) key).trim().equals("") ) ) {
 return false;
 }
 // If key already available then, we are not overriding its value.
 if (entrySet.contains(key)) { // Then override its value, but we are not allowing
 return false;
 } else { // Add the entry
 entrySet.add(key);
 entryMap.put(key, value);
 return true;
 }
 }
 public V put(K key, V value) {
 V oldValue = entryMap.get(key);
 insertionRule(key, value);
 return oldValue;
 }
 public void putAll(Map<? extends K, ? extends V> t) {
 for (Iterator i = t.keySet().iterator(); i.hasNext();) {
 K key = (K) i.next();
 insertionRule(key, t.get(key));
 }
 }
 public void clear() {
 entryMap.clear();
 entrySet.clear();
 }
 public boolean containsKey(Object key) {
 return entryMap.containsKey(key);
 }
 public boolean containsValue(Object value) {
 return entryMap.containsValue(value);
 }
 public Set entrySet() {
 return entryMap.entrySet();
 }
 public boolean equals(Object o) {
 return entryMap.equals(o);
 }
 public V get(Object key) {
 return entryMap.get(key);
 }
 public int hashCode() {
 return entryMap.hashCode();
 }
 public boolean isEmpty() {
 return entryMap.isEmpty();
 }
 public Set keySet() {
 return entrySet;
 }
 public V remove(Object key) {
 entrySet.remove(key);
 return entryMap.remove(key);
 }
 public int size() {
 return entryMap.size();
 }
 public Collection values() {
 return entryMap.values();
 }
}

Usage of CustomHashMap:

public static void main(String[] args) {
 System.out.println("== LinkedHashMap ==");
 Map<Object, String> map2 = new LinkedHashMap<Object, String>();
 addData(map2);
 System.out.println("== CustomHashMap ==");
 Map<Object, String> map = new CustomHashMap<Object, String>();
 addData(map);
}
public static void addData(Map<Object, String> map) {
 map.put(null, "1");
 map.put("name", "Yash");
 map.put("1", "1 - Str");
 map.put("1", "2 - Str"); // Overriding value
 map.put("", "1"); // Empty String
 map.put(" ", "1"); // Empty String
 map.put(1, "Int");
 map.put(null, "2"); // Null
 for (Map.Entry<Object, String> entry : map.entrySet()) {
 System.out.println(entry.getKey() + " = " + entry.getValue());
 }
}

O/P:

== LinkedHashMap == | == CustomHashMap ==
null = 2 | name = Yash
name = Yash | 1 = 1 - Str
1 = 2 - Str | 1 = Int
 = 1 |
 = 1 |
1 = Int |

---

If you know the KEY's are fixed then you can use EnumMap. Get the values form Properties/XML files

EX:

enum ORACLE {
 IP, URL, USER_NAME, PASSWORD, DB_Name;
}
EnumMap<ORACLE, String> props = new EnumMap<ORACLE, String>(ORACLE.class);
props.put(ORACLE.IP, "127.0.0.1");
props.put(ORACLE.URL, "...");
props.put(ORACLE.USER_NAME, "Scott");
props.put(ORACLE.PASSWORD, "Tiget");
props.put(ORACLE.DB_Name, "MyDB");

Answer 7

In case you are looking for a way to initialize and fill the map preserving order, you could try LinkedHashMap with double braces initialization:

public class Example {
 private final Map<String, Integer> numbers = new LinkedHashMap<>() {{
 put("one", 1);
 put("two", 2);
 put("three", 3);
 }};
}

It looks a bit ugly, but it is the only way to fill the map preserving order in one line. Use it for example in a field declaration. You can keep together initialization and population of the map, no need to create custom utils method.

Without double braces but using streams:

public class Example {
 private final Map<String, Integer> numbers = Stream.of(
 Map.entry("one", 1),
 Map.entry("two", 2),
 Map.entry("three", 3)
 ).collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (a, b) -> a, LinkedHashMap::new));
}

You can also extract this logic to utility method:

public class Utils {
 @SafeVarargs
 public static <K, V> Map<K, V> orderedMap(Map.Entry<K, V>... entries) {
 if (entries == null || entries.length == 0)
 return Map.of();
 return Stream.of(entries).collect(Collectors.toUnmodifiableMap(
 Map.Entry::getKey,
 Map.Entry::getValue,
 (a, b) -> {
 // check for duplicated keys
 throw new RuntimeException("Duplicates found: " + a + ", " + b);
 },
 LinkedHashMap::new));
 }
}
public class Example {
 private final Map<String, Integer> numbers = Utils.orderedMap(
 Map.entry("one", 1),
 Map.entry("two", 2),
 Map.entry("three", 3)
 );
}

Java has good Map.of() method, but lacks OrderedMap.of() and SortedMap.of().

• user85421: isn't LinkedHashMap already proposed by the accepted answer (from 15 years ago) and some other (older) answers?
• alaster: @user85421 My answer compliments original with double braces initialization
• user85421: which (double braces) has nothing to do with the question - keeping insertion order - and is most often not considered a good practice at all (not only my opinion) -- Why create a new (anonymous) class just to initialize a list ??!! It is not adding any new functionality to it. (kind of building a new car with open door, instead of opening the door of the already existing car :-/ )
• user85421: ( What is Double Brace initialization in Java? , Efficiency of Java "Double Brace Initialization"? , Double brace initialization with nested collections , ... )
• alaster: Agree. I'm frustrated java doesn't have map literals or static methods like OrderedMap.of. What is your choise if you need to define ordered map with values in a field?

Answer 8

I don't know if it is opensource, but after a little googling, I found this implementation of Map using ArrayList. It seems to be pre-1.5 Java, so you might want to genericize it, which should be easy. Note that this implementation has O(N) access, but this shouldn't be a problem if you don't add hundreds of widgets to your JPanel, which you shouldn't anyway.

Answer 9

Whenever i need to maintain the natural order of things that are known ahead of time, i use a EnumMap

the keys will be enums and you can insert in any order you want but when you iterate it will iterate in the enum order (the natural order).

Also when using EnumMap there should be no collisions which can be more efficient.

I really find that using enumMap makes for clean readable code. Here is an example

Answer 10

Since Java 21, one can use SequencedMap to indicate that the keys are in a defined order.

Java 21 offeres these implementation:

• java.util.Collections.UnmodifiableSequencedMap
• java.util.LinkedHashMap

Resulting code:

SequencedMap<String, String> demo = new LinkedHashMap<>();

There is also ReversedLinkedHashMapView, but this is uncommon.

---

In case you want to get more preformance and less memory consuption, explore Ecipse Collections:

MutableOrderedMap<String, Integer> map =
 OrderedMapAdapter.adapt(new LinkedHashMap<>());

The offer more examples at https://github.com/eclipse-collections/eclipse-collections/blob/master/README_EXAMPLES.md.

• Donald Raab: Eclipse Collections most likely won't give a performance or memory benefit in this particular example, as the implementation of MutableOrderedMap interface is simply wrapping a LinkedHashMap. The MutableOrderedMap interface is a richer interface, and like SequencedMap communicates that there is an order to the Map.

Answer 11

LinkedHashMap is used for maintaing insertion order. The LinkedHashMap class of the Collections framework is the Hashtable and LinkedList implementation of the Map interface. It stores its entries in a Hashtable and uses a doubly-linked list internally to maintain the insertion order.

Ex: Java program to find FirstNonRepeatingCharacter. In the below example first non-repeating character is 't'.

Code Sample 1:

String str = "Stress";
Chracter ch = str.toLowerCase().chars().mapToObj(c -> Chracter.valueOf((char)c).collect(Collectors.groupingBy(Function.identity(), LinkedHashMap::new, Collectors.couting()))).entrySet().stream().filter(entry -> entry.getValue() == 1).map(entry -> entry.getKey()).findFirst().get();

Code Sample 2:

String str = "Stress";
Chracter ch = str.toLowerCase().chars().mapToObj(c -> Chracter.valueOf((char)c).collect(Collectors.groupingBy(Function.identity(), Collectors.couting()))).entrySet().stream().filter(entry -> entry.getValue() == 1).map(entry -> entry.getKey()).findFirst().get();

in the code sample 1 I used LinkedHashMap which maintains insertion hence getting the expected result where as in code sample 2 we are not maintaining any insertion order hence it fails.

• user85421: isn't LinkedHashMap already proposed by the accepted answer (from 15 years ago) and some other (older) answers?