44

When LinkedHashMap.keySet() is called, will the order of the Set returned be the same as the order the keys were added in?

Armand
  • 23,463
  • 20
  • 90
  • 119
  • For those coming from PHP, let me help them by pointing out that a LinkedHashMap behaves very much like a PHP array. – Walter Tross Oct 02 '17 at 17:14

2 Answers2

51

Yes.

See: LinkedHashMap:

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

and from the HashMap#keySet documentation:

The set [returned] is backed by the map, so changes to the map are reflected in the set, and vice-versa.

Arne Evertsson
  • 19,693
  • 20
  • 69
  • 84
Tom Tresansky
  • 19,364
  • 17
  • 93
  • 129
  • 4
    @Tom thanks, I'm still not convinced that this is explicit. Why wouldn't LinkedHashMap.keySet() return a subclass of Set with fixed ordering? – Armand Aug 16 '10 at 09:39
  • 5
    Because if it returned a SortedSet, then LinkedHashMap would be adding the requirement that its keys are of a type which implements Comparable, or that a comparator function be supplied. This is NOT required by Map. Check out the SortedSet documentation: http://download.oracle.com/javase/6/docs/api/java/util/SortedSet.html. Not having this requirement allows even keys which do not implement Comparable to be used in a LinkedHashMap, which is the more general case. LinkedHashMap's implementation might even return a SortedSet if its keys ARE Comparable, but it simply isn't REQUIRED to. – Tom Tresansky Aug 16 '10 at 17:56
  • 1
    Of course, the contract of LinkedHashMap says that it maintains INSERTION ordering, which may not be the NATURAL ordering. So in that case, a SortedSet wouldn't work at all---the keys simply wouldn't be sorted in that manner. – Tom Tresansky Aug 17 '10 at 11:05
  • @Tom I didn't mention `SortedSet` and there could be an implementation of Set which implied order other than natural order. – Armand Aug 17 '10 at 16:48
  • @Alison: I mentioned `SortedSet` because what is a subclass of `Set` with a fixed ordering other than a `SortedSet`? – Tom Tresansky Aug 31 '10 at 18:56
  • @Tom `LinkedHashSet`? This might seem a more logical assumption in this case. – Armand Sep 01 '10 at 09:13
  • But `LinkedHashSet` does not implement `SortedSet'. – Tom Tresansky Sep 29 '10 at 19:56
  • 2
    @Tom exactly - you asked for an ordered `Set` which does not implement `SortedSet`, and I provided an example. – Armand Feb 19 '11 at 22:23
  • 2
    @Alison It does return a subclass of Set with fixed ordering, if you look at the source code. The HashSet's keySet() method uses a custom Set class which reads off of an iterator. The LinkedHashMap overrides that iterator to read from it's own linked list of map entries. http://www.docjar.com/html/api/java/util/HashMap.java.html http://www.docjar.com/html/api/java/util/LinkedHashMap.java.html – Roman Sep 04 '12 at 21:02
  • 4
    @Roman thanks, nice info. I wonder if this could change in future, and if it could be dependant on the Java implementation (i.e. Oracle vs others) – Armand Sep 05 '12 at 06:07
  • 1
    Is keySet order debatable? http://stackoverflow.com/a/10387318/231382 – Hernán Eche Jan 24 '13 at 13:37
  • 2
    "...which is _normally_ the order..." isn't terribly precise (it could have meant sometimes it's random!). The important line from the LinkedHashMap javadoc is in the opening sentence: "with _predictable iteration order_". – bacar Sep 20 '13 at 09:11
  • I agree @bacar, I don't know why they say _normally_. I'm very curious why they put it that way... – spectrum Feb 04 '19 at 21:35
40

Yes. The exception is that when a key is reinserted, it appears in the order in which it was first inserted to the list.

Arne Evertsson
  • 19,693
  • 20
  • 69
  • 84
relet
  • 6,819
  • 2
  • 33
  • 41
  • 4
    +1 Good catch on that corner case. – Tom Tresansky Aug 13 '10 at 15:09
  • 5
    Actually, the exception is for when the key is **reinserted**, not deleted and reused. The case is when you call `put(key, value)` for a key that was already in the map. (The javadoc explains this clearly.) – Stephen C Aug 13 '10 at 15:26