Java Class that implements Map and keeps insertion order?

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 elements.

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.

---

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 

---

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.

---

You can use LinkedHashMap to main insertion order in Map

The important points about Java LinkedHashMap class are:

It contains only unique elements. A LinkedHashMap contains values based on the key. It may have one null key and multiple null values. It is same as HashMap instead maintains insertion order public class LinkedHashMap extends HashMap implements Map

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

---

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.

---

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");

---

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.

---

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

---