CODEWITHSUNDEEP
javaiterationlinkedhashmap
user256239
user256239

Reputation: 18027

Is the order guaranteed for the return of keys and values from a LinkedHashMap object?

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?

Upvotes: 205

Views: 63734

Answers (6)

M. Justin
M. Justin

Reputation: 21399

Starting with Java 21, the documentation for LinkedHashMap is more explicit about the ordering of the collection view methods than in prior versions of Java. It makes it clear that all its collection view methods use the same order — the encounter order of the map.

  • entrySet: "The encounter order of the view matches the encounter order of entries of this map."
  • keySet: "The encounter order of the keys in the view matches the encounter order of mappings of this map."
  • values: "The encounter order of values in the view matches the encounter order of entries in this map."

This is also documented in the SequencedMap interface which LinkedHashMap implements starting with Java 21:

The view collections provided by the keySet, values, entrySet, sequencedKeySet, sequencedValues, and sequencedEntrySet methods all reflect the encounter order of this map.

The encounter order of a LinkedHashMap is specified to be insertion-order, unless the map was created as an access-order LinkedHashMap (using the special access-order constructor).

So as of Java 21, the answer is clearly documented that yes, keySet, values, and entrySet will return their elements in the same order for a LinkedHashMap (either insertion or encounter order, depending on how the map was constructed).

Prior versions of Java did have the same behavior, but the documentation around this behavior was less explicit.

Therefore, regardless of the version of Java, the order of the three collection view methods are the same as the encounter order of the map.

Upvotes: 1

as.tek
as.tek

Reputation: 995

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.

Upvotes: 8

user207421
user207421

Reputation: 311054

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.

Upvotes: 6

Powerlord
Powerlord

Reputation: 88846

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.

Upvotes: 279

Uri
Uri

Reputation: 89859

AFAIK it is not documented so you cannot "formally" assume so. It is unlikely, however, that the current implementation would change.

If you want to ensure order, you may want to iterate over the map entires and insert them into a sorted set with an order function of your choice, though you will be paying a performance cost, naturally.

Upvotes: 0

sblundy
sblundy

Reputation: 61434

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

Upvotes: 13

Related Questions