Java Class That Implements Map and Keeps Insertion Order

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

java maintain insertion order in map

You're looking for a LinkedHashMap. Pro tip: If you go to the JavaDoc for an interface like Map, there's a "All Known Implementing Classes" section where you can see a list of all implementations in the JDK, and see if any meet your needs...

Hashmap + Insertion Order

I have executed below code and for 10,000 times response is returned in same ordered.

That's just what happens to occur with the version you're using and the values you're inserting. There's no guarantee it will continue to occur, or that insertion order is maintained if you add different values, or if you remove items then add others.

Basically, it's not saying that it definitely won't be in a particular order - it's saying that you absolutely should not rely on it being in that order.

Also note that if you expected insertion order to be maintained, your examples already demonstrate that it's not. The output shows items not being presented in insertion order.

LinkedHashMap will maintain insertion order, by maintaining a linked list of entries alongside the hash map internally. (An exception here is that there's a constructor which allows you to specify that items will be presented in access order rather than insertion order, which is usually used when you want this as the basis of a cache.)

How to preserve insertion order in HashMap?

LinkedHashMap is precisely what you're looking for.

It is exactly like HashMap, except that when you iterate over it, it presents the items in the insertion order.

How to Maintain order of insertion

Here are the characteristic differences of some important Map implementations:

LinkedHashMap: "with predictable iteration order [...] which is normally the order in which keys were inserted into the map (insertion-order)."
HashMap: "makes no guarantees as to the order of the map"
TreeMap: "is sorted according to the natural ordering of its keys, or by a Comparator"
- i.e. it's a SortedMap

So it looks like LinkedHashMap is what you need in this case.

Here's a snippet to illustrate the differences; it also shows a common way to iterate over all entries of a Map, and how using an interface to refer to objects allow great flexibility of choice of implementation.

import java.util.*;
public class MapExample {
    public static void main(String[] args) {
        populateThenDump(new HashMap<String,Integer>());
        populateThenDump(new TreeMap<String,Integer>());
        populateThenDump(new LinkedHashMap<String,Integer>());
    }
    static void populateThenDump(Map<String,Integer> map) {
        System.out.println(map.getClass().getName());

        map.put("Zero",  0);
        map.put("One",   1);
        map.put("Two",   2);
        map.put("Three", 3);
        map.put("Four",  4);

        for (Map.Entry<String,Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " => " + entry.getValue());
        }
    }
}

The output of the above snippet is (as seen on ideone.com):

java.util.HashMap          // unordered, results may vary
Three => 3
Zero => 0
One => 1
Four => 4
Two => 2
java.util.TreeMap          // ordered by String keys lexicographically
Four => 4
One => 1
Three => 3
Two => 2
Zero => 0
java.util.LinkedHashMap    // insertion order
Zero => 0
One => 1
Two => 2
Three => 3
Four => 4

Java Ordered Map

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.

Hashmap put(), is it always ordering?

HashMap doesn't preserve the order of insertion. However if you use the values 0 to 10 in order, these happen to be hashed to the buckets 0 to 10 internally and placed in an array in that order. When you iterate of the HashMap you are looking at these buckets in order. Note: this implementation could change in the future and this might not happen.

The default size of a HashMap is 16 and with a load factor of 0.7 you can add 11 values without it resizing. This means when you view these values, the current implementation happens to place 0 to 10 in sorted order.

If you only need the values 0 to 10 be in order, I suggest using an array, instead of a HashMap.

Maps (collection) that maintains insertion Order in java

You should use LinkedHashMap for this purpose..Visit Android Docs and Java Docs for more details.

Should I use LinkedHashMap or TreeMap if I insert and access in order?

Use a TreeMap. Not for any performance reasons, but because it can be assigned to SortedMap (or NavigableMap), and that communicates clearly your intent that the map has a defined order.

Java Class That Implements Map and Keeps Insertion Order