Java Class that implements Map and keeps insertion order?
Asked Answered
Z

9

613

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!

Zelig answered 25/3, 2009 at 21:22 Comment(3)
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.Lamination
I took the liberty to change the title, since not using hashes is not actually the problem, but keeping the insertion order.Junoesque
Similar Question, Java Ordered MapTanah
B
919

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.

Broadleaved answered 25/3, 2009 at 21:23 Comment(8)
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?Proclus
@CoryKendall: Does TreeMap not work? It is supposed to be sorted by keys, not by values.Broadleaved
My mistake, I thought Sets were unsorted.Proclus
@CoryKendall: They can be, but aren't always.Broadleaved
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!Oceanic
I believe LinkedHashMap does not implement NavigableMap or SortedMap.Pelpel
A LinkedHashMap keeps the keys in the order they were LAST ACCESSED, not "inserted". Very annoying when that's not what you want.Kreager
@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.Broadleaved
C
61

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 
Conakry answered 8/5, 2017 at 21:26 Comment(0)
W
20

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.

Warrior answered 27/8, 2010 at 15:50 Comment(0)
M
8

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

Mavismavra answered 2/5, 2018 at 5:29 Comment(1)
"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.Rollins
K
6

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.

Kamchatka answered 26/3, 2009 at 21:4 Comment(0)
C
4

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");
Chary answered 30/10, 2019 at 10:52 Comment(0)
M
1

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.

Maibach answered 25/3, 2009 at 21:29 Comment(0)
P
1

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

Pyroxene answered 9/11, 2017 at 8:36 Comment(0)
G
0

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.

Gnomic answered 26/2 at 10:38 Comment(0)

© 2022 - 2024 — McMap. All rights reserved.