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!

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

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 

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

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 6

You could try my Linked Tree Map implementation.

Answer 7

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 8

You can use LinkedHashMap to main insertion order in Map

The important points about Java LinkedHashMap class are:

1. It contains onlyunique 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