Does an ArrayList created from the keySet() of LinkedHashMap preserves the order of insertion?

Question

I get data something like

{"Employee 1 of ABC", "ABCX"}, {"Employee 2 of ABC", "ABCY"}, {"Employee 3 of ABC", "ABCZ"}

from database through a RefCursor.

I have a case where I need to preserve the order in which data is read from the database. Since my data is kind of 'key-value' ,I thought of using a implementation of Map which is ordered. Hence chose LinkedHashMap

//defined as a static map inside a common utlity class
public class Common{
public static final LinkedHashMap<String, String> empMap = new   LinkedHashMap<String, String>();
}

//rs is the resultset
if (rs != null) {
            while (rs.next()) {
                key = rs.getString("name_text");
                value = rs.getString("id");
                Common.empMap.put(key, value);
            }
}

I have to pass the keys to the client, in the same order in which it was retrieved from the database (Cursor).

List<String> empList = new ArrayList<String>(Common.empMap.keySet());

keySet() - The documentation says "Returns a Set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa"

What I expect is that Since ArrayList is also an ordered collection, I should get the keys in the same way in which it was retrieved/inserted into the Map.

When I do a sample test program, I am getting as expected.

public class LinkedMap {    
    public static void main(String[] args) {
        LinkedHashMap<String, String> map = new LinkedHashMap<String, String>();        
        map.put("Employee 1 of ABC", "ABCX");
        map.put("Employee 2 of ABC", "ABCY");
        map.put("Employee 3 of ABC", "ABCZ");   
        ArrayList<String> list = new ArrayList<String>(map.keySet());   
        System.out.println(list);   
    }
}

output: [Employee 1 of ABC, Employee 2 of ABC, Employee 3 of ABC]

However my question is , if this is guaranteed output or is it that I am getting just randomly, and it might vary(?),

update 09/14/2019

I am separating the answer from the question to avoid any confusion.

I like how the variable type is the most specific `LinkedHashMap`, instead of a vague `Map` :) — ZhongYu, Sep 29 '15 at 22:03
I think , having the interface or the concrete class reference doesn't make a difference to my use case. But I must admit that it was a mistake to use the concrete class rather than interface. Or do you feel different? — spiderman, Sep 29 '15 at 23:16
no, I think it's best to use the most specific type for local/instance variables. — ZhongYu, Sep 29 '15 at 23:22

score 4 · Accepted Answer · answered Sep 29 '15 at 19:55

It is guaranteed.

Even though the Set interface in itself doesn't guarantee any order (well, LinkedHashSet does), the fact that the Map implementation itself guarantees insertion ordering pretty much guarantees that you will get the keys in this order as well. The interface returned by .keySet() just happens to be a Set since, well, keys in a Map are guaranteed to be unique.

If it weren't, consider what would happen in this situation:

// case 1
for (final Map.Entry<K, V> entry: map.entrySet()) {
    // entry.getKey(), entry.getValue()
}

// case 2
for (final K key: map.keySet()) {
    V value = map.get(key);
}

If these two codes had two different behaviors, uh...

Thank you +1, "The interface returned by .keySet() just happens to be a Set" - thinking of this `Set` was what confused me — spiderman, Sep 29 '15 at 20:12
Well, what if those two pieces of code iterated in a different order? Or even .values()? — fge, Sep 30 '15 at 09:01

score 2 · Answer 2 · answered Sep 29 '15 at 19:57

2

Yes, it is guaranteed.

In the Oracle JDK, the class LinkedHashMap reimplements the method newKeyIterator() which returns an instance of a class inheriting LinkedHashIterator. That one is ordered.

answered Sep 29 '15 at 19:57

nrainer

2,542
2
23
35

very valid one, +1 I dived into it to see this :) – spiderman Oct 01 '15 at 01:17

score 1 · Answer 3 · answered Sep 29 '15 at 20:06

The other answers explain that LinkedHashMap#keySet().iterator() iterates in specified order, so let me just add:

ArrayList Javadoc says about ArrayList(Collection):

Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.

So it is guaranteed that the ArrayList items will be in the same order.

score 1 · Answer 4 · answered Sep 29 '15 at 20:06

The iteration order of a LinkedHashSet is guaranteed to be the same as the order in which keys are inserted (supposing you do not use the special constructor that allows you to request ordering by most-recent access instead). You can find this in its documentation.

I suppose you could argue that the iteration order guarantee applies only to the entry set, not to the other views, but the docs don't support that well (inasmuch as they refer to the iteration order), and in practice the collection views do share a common iteration order.

For its part, the constructor ArrayList(Collection) is documented to fill the list in the order that elements are returned by the specified Collection's iterator.

score 1 · Answer 5 · edited May 23 '17 at 12:03

1

As explained in this question Does entrySet() in a LinkedHashMap also guarantee order? and noted in the JavaDocs, iteration type operations are defined to be in the insertion order for LinkedHashMap. This affects the keySet as it does the entrySet.

The constructor of ArrayList will insert into the List in the iterator's order.

Those two conditions combined, means the API guarantees this behavior.

edited May 23 '17 at 12:03

Community

1
1

answered Sep 29 '15 at 20:17

Spacy

111
3

Good one, +1 for the references – spiderman Sep 29 '15 at 23:20

score 0 · Answer 6 · answered Sep 14 '19 at 10:22

Thank you all, Each one of you contributed valid points.

To summarize all answers,

It is guaranteed that the order is maintained.

As per Javadocs,

LinkedHashMap is 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)

ie: LinkedHashMap will iterate in the order in which the entries were put into the map.

So LinkedHashMap#keySet() will give me the same order in which the keys were inserted to the map, because the LinkedHashMap#keySet().iterator() iterates in specified order.

Going deep to the implementation of iterator() we can see that,

LinkedHashMap implements the method newKeyIterator() which returns an instance of a class inheriting LinkedHashIterator, taking care of the 'ordering'

// These Overrides alter the behavior of superclass view iterator() methods
Iterator<K> newKeyIterator()   { return new KeyIterator();   } ...  

private class KeyIterator extends LinkedHashIterator<K> {...

private abstract class LinkedHashIterator<T> implements Iterator<T> { ...

For this: ArrayList<String> list = new ArrayList<String>(map.keySet()); The constructor ArrayList(Collection) is documented to fill the list in the order that elements are returned by the specified Collection's iterator.

Does an ArrayList created from the keySet() of LinkedHashMap preserves the order of insertion?

6 Answers6