5

For a given type of Map, are there any guarantees that iterating over the Collection views returned by the keySet, values and entries methods are iterated in the same order?

Background: I'm wondering whether transforming 

public static void doSomethingForEachEntry(Map<String, Integer> someMap) {

    for (String key : someMap.keySet()) {
        doSomething(someMap.get(key));
    }       
}

to

public static void doSomethingForEachEntry(Map<String, Integer> someMap) {

    for (Integer value : someMap.values()) {
        doSomething(value);
    }       
}

is guaranteed to keep iteration order unchanged.

Boann
  • 48,794
  • 16
  • 117
  • 146
Hulk
  • 6,399
  • 1
  • 30
  • 52
  • It seems the question in the title and in your post is not the same. What exactly do you want to know? If the ordering of the keys return is the same as the ordering of the values? Or if the ordering on the second call will be the same as on the first call? – Tunaki Jan 25 '16 at 10:04
  • 1
    You shouldn't rely on the order of iteration (unless you are using some ordered Map, such as TreeMap). For example, if you are using a HashMap, even if for the current state of the Map, both `values()` and `keySet()` give the same order of iteration, after adding elements to the HashMap the order may change. – Eran Jan 25 '16 at 10:06
  • @Tunaki My question is if the ordering of the keys will be the same as the order of the values in the sense that both of my code snippets would process values in the same order. – Hulk Jan 25 '16 at 10:13
  • 1
    @Hulk the docs say *The **order of a map** is defined as the order in which the iterators on the map's collection views return their elements.* which to me means they all share an order. Was about to post an answer, but it got closed while I was typing. https://docs.oracle.com/javase/8/docs/api/java/util/Map.html – CupawnTae Jan 25 '16 at 10:16
  • 1
    @CupawnTae I reopened it. – Boann Jan 25 '16 at 11:39
  • @Boann thanks, answer posted – CupawnTae Jan 25 '16 at 11:54
  • @Eran I know that modifying the Map will change the order of the Map - I'm only asking if the views share the same order between modifications. (and I'm aware that even a `get` may change the order in case of a `LinkedHashMap` set to `access-order`-mode, in which case my first code-snippet would behave in... probably unexpected ways) – Hulk Jan 25 '16 at 15:39

2 Answers2

7

While it is true that you can't rely on a specific ordering unless the Map implementation explicitly defines it, there is a sentence in the API documentation that implies there is a single shared ordering for the map and all its collection views:

The order of a map is defined as the order in which the iterators on the map's collection views return their elements.

(my emphasis)

For this to be satisfied, a map has an inherent order (even though it may not be specified, and may change as the map is modified), and all collection views must correspond to this order. Whether that constitutes a guarantee, and in particular whether all third-party map implementations will honour it, is another question.

It's also worth noting that these are explicitly defined in the Map interface as views that are backed by the map, (e.g. if you remove an element from the keySet, the corresponding Map entry must be removed from the map). This means in reality it's less likely that you'll get different orderings from a correct Map implementation than it would be if for example you made shallow copies of the collection views.

Having said all that, if the question is "is this a safe refactor?" then the answer is "yes, as long as the original code isn't itself broken". If the method relies on a specific ordering, and therefore a specific Map implementation, the method should be declared to accept only that type of Map. Otherwise, you have a potential timebomb if the underlying Map implementation changes down the line (and I have seen software break in real life because of this with a JDK update).

If a particular caller is relying on a specific ordering because it knows it's passing an ordered Map implementation, that's fine and that order will be preserved after your refactor.

CupawnTae
  • 14,192
  • 3
  • 29
  • 60
  • 1
    Good points. And I have not found any counter-example yet. I've added tests for all `Map`- Types used in my codebase, but it would be good to know if this transformation (which is suggested by static analysis tools and would likely increase both readability and performance) is guaranteed to be safe. – Hulk Jan 25 '16 at 13:58
  • @Hulk added some musings on the "guaranteed to be safe" question - nothing you're not already aware of, but worth saying anyway – CupawnTae Jan 26 '16 at 10:15
  • After some more research, I tend to agree. For [SortedMaps](https://docs.oracle.com/javase/8/docs/api/java/util/SortedMap.html) there is the additional gurantee *A Map that further provides a total ordering on its keys. The map is ordered according to the natural ordering of its keys, or by a Comparator typically provided at sorted map creation time. **This order is reflected when iterating over the sorted map's collection views (returned by the entrySet, keySet and values methods)**. Several additional operations are provided to take advantage of the ordering.* – Hulk Jan 26 '16 at 10:39
  • [LinkedHashMap](https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html) is not a `SortedMap` and does not explicitly mention the different views, but explicitly defines an iteration order without limiting it to a certain view, so it is probably reasonable to assume this applies to all views. – Hulk Jan 26 '16 at 10:48
0

Iteration order depends on the specific implementation of Map you use. Refer to the documentation if you know the Map type. If you don't then don't rely on any iteration order.

dzidzitop
  • 385
  • 2
  • 11