Maintaining order in HashMap

Question

I have a list which I convert to a map to do some work. After that, i convert the map back again to a list, but this time the order is random. I need the same initial order retained in my second list.

the obvious reason is that a HashMap doesn't maintain order. But I need to do something so that it does. I cannot change the Map implementation.How can I do that ?

Consider the given code:

import java.util.*;
public class Dummy {

public static void main(String[] args) {
    System.out.println("Hello world !");
    List<String> list = new ArrayList<String>();
    list.add("A");list.add("B");list.add("C");
    list.add("D");list.add("E");list.add("F");

    Map<String,String> map = new HashMap<String, String>();

    for(int i=0;i<list.size();i=i+2)
        map.put(list.get(i),list.get(i+1));

    // Use map here to do some work

    List<String> l= new ArrayList<String>();
    for (Map.Entry e : map.entrySet()) {
        l.add((String) e.getKey());
        l.add((String) e.getValue());
    }
  }
}

For ex - Initially, when I printed the list elements, it printed out

A B C D E F 

Now, when I print the elements of List l, it printed out

E F A B C D

Answer 1

HashMap itself doesn't maintain insertion order - but LinkedHashMap does, so use that instead.

As documented... HashMap:

This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

And LinkedHashMap:

Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).

Answer 2

Use LinkedHashMap instead of HashMap to maintain order.

Map<String,String> map = new LinkedHashMap<String, String>();

Answer 3

Why can't you change the Map implementation (to LinkedHashMap for example)?

If there's a logical ordering, you could sort the List with a custom Comparator.

Answer 4

HashMap doesn't preserve order of insertion

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

Use LinkedHashMap if you want to preserve order of keys

Answer 5

Consider making your items sortable. In the case of strings, there is already a natural ordering; alphabetical. You can make objects that use the sortable class, and therefore you can use sorting algorithms to put these objects in a nice order, no matter what order you get them in from hash!

Answer 6

It's time for a LinkedHashMap, it is meant exactly to preserve insertion order.

Mind that even a TreeMap exists, which allows you to keep your desired order by using Comparable interface. It is not an hash map anymore, but a tree.

Answer 7

If you truly are unable to switch to another Map implementation (LinkedHashMap is exactly what you want), then the only other possibility is to retain the original List, and use it to create the new List from the Map.

public <T> List<T> listFromMapInOrder(final Map<T, T> map, final List<T> order) {
    List<T> result = new ArrayList<T>();
    for (T key : order) {
        if (map.containsKey(key)) {
            result.add(key);
            result.add(map.get(key));
        }
    }
    return result;
}

But I would refactor the code until it was possible to switch to a LinkedHashMap.