Is the order guaranteed for the return of keys and

Question

I know LinkedHashMap has a predictable iteration order (insertion order). Does the Set returned by LinkedHashMap.keySet() and the Collection returned by LinkedHashMap.values() also maintain this order?

Answer 1

Don't get confused with LinkedHashMap.keySet() and LinkedHashMap.entrySet() returning Set and hence it should not guarantee ordering !

Set is an interface with HashSet,TreeSet etc beings its implementations. The HashSet implementation of Set interface does not guarantees ordering. But TreeSet does. Also LinkedHashSet does.

Therefore it depends on how Set has been implemented in LinkedHashMap to know whether the returning Set reference will guarantee ordering or not. I went through the source code of LinkedHashMap, it looks like this:

private final class KeySet extends AbstractSet<K> {...}
public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E> {...}

Thus LinkedHashMap/HashMap has its own implementation of Set i.e. KeySet. Thus don't confuse this with HashSet.

Also, the order is maintained by how the elements are inserted into the bucket. Look at the addEntry(..) method of LinkedHashMap and compare it with that of HashMap which highlights the main difference between HashMap and LinkedHashMap.

Answer 2

I don't think you can presume the ordering of keySet() and values().

I can easily write an implementation of LinkedHashMap that returns you unordered keySet() and values(), as long as I stick to the contract of these two methods that are defined in Map, and overridden in HashMap.

Answer 3

You can assume so. The Javadoc says 'predictable iteration order', and the only iterators available in a Map are those for the keySet(), entrySet(), and values().

So in the absence of any further qualification it is clearly intended to apply to all of those iterators.

Answer 4

Looking at the source, it looks like it does. keySet(), values(), and entrySet() all use the same entry iterator internally.

Answer 5

The Map interface provides three collection views, which allow a map's contents to be viewed as a set of keys, collection of values, or set of key-value mappings. The order of a map is defined as the order in which the iterators on the map's collection views return their elements. Some map implementations, like the TreeMap class, make specific guarantees as to their order; others, like the HashMap class, do not.

-- Map

This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).

-- LinkedHashMap

So, yes, keySet(), values(), and entrySet() (the three collection views mentioned) return values in the order the internal linked list uses. And yes, the JavaDoc for Map and LinkedHashMap guarantee it.

That is the point of this class, after all.

Answer 6

Looking at the interface it returns a plain Set and not an SortedSet. So there are no guarantees.

Before assuming an implicit guarantee by looking at the implementation (always a bad idea) also look at the implementations in all other Java implementations :)

You could better create for instance a TreeSet with the keySet in the constructor.