Do keys and values in an an unordered hash map line up when iterated independently?

Question

I have seen answers touching this topic but wanted to find if anybody has any example where keyset and values lists that you derive from hash map would have the keys and values in different order. I understand the entries itself can have undefined order in hash map, but could the lists of keys and values be out of order with respect to each other?

Here is a short snippet for clarification:

public class App {
    public static void main(String[] args) {
        Map<String,String> stateCapitols = new HashMap<>();
        stateCapitols.put("AL", "Montgomery");
        stateCapitols.put("AK", "Juneau");
        stateCapitols.put("CO", "Denver");
        stateCapitols.put("FL", "Tallahassee");
        stateCapitols.put("Indiana", "Indianapolis");

        stateCapitols.keySet().stream().forEach(System.out::println);
        System.out.println();
        stateCapitols.values().stream().forEach(System.out::println);
    }
}

Would there be any way AL might appear in same place as Denver (or any other value) in the above example?

Answer 1

Let's look again at the Java SE API language regarding iteration order in the Map contract:

Some map implementations, like the TreeMap class, make specific guarantees as to their order; others, like the HashMap class, do not.

And HashMap:

This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

Since it is explicitly stated that HashMap iterators do not have an order, it cannot be assumed that the iteration will be stable even between calls to the same method, let alone between calls to the different methods keySet() and values().

Helpfully, Map has a method entrySet() that does exactly what you need: it iterates over map contents in a way that pairs up keys and values. It is the method to use any time you need to rely on both parts of the pair.

With changes to Java licensing now in effect, people and organizations that had assumed they would probably always use Oracle's implementation of Java are now looking to alternative implementations. Relying on the unwritten details of a single implementation is extremely dangerous, even more so now than before Oracle's licensing and pricing changes.

Answer 2

HashMap makes no guarantees about its iteration order. It is possible in principle (that is, it is allowed by the specification) for the order in which keys, for example, to change from one iteration to the next, even if the map's contents have not changed, or for the iteration order of keys to differ from the iteration order of the corresponding values.

This is stated in the HashMap specification:

This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

In practice, the iteration order of HashMap is stable from one iteration to the next, and even from one JVM invocation to the next, if the HashMap is initialized and populated exactly the same way. However, it is unwise for an application to depend on this. Creating a HashMap with a different initial size or load factor can influence the iteration order, even if the map is populated with the same contents. The HashMap implementation does change from time to time, and this also affects iteration order. Such changes occur even in patch or bugfix releases of the JDK. Unfortunately, history has shown that applications break when the iteration order changes. Therefore, robust applications should strive to avoid making any dependencies on HashMap iteration order.

This is pretty hard to do in practice. I'm aware of one (non public) version of the JDK that has a testing mode that randomizes iteration order of HashMaps. That potentially helps flush out such dependencies.

If you need to correlate keys and values of a HashMap while iterating it, get the entrySet() of the HashMap and iterate that. It provides map entries (key-value pairs) so the relationship between keys and values is preserved.

Alternative Map implementations in the JDK provide well-defined iteration ordering. TreeMap and ConcurrentSkipListMap order their entries based on a provided comparison method. LinkedHashMap provides iteration order based on insertion order. (It also provides a mode where iteration is by access order, which is sometimes useful, but whose behavior is often surprising.)

Note that the unmodifiable collections introduced in Java 9 (Set.of, Map.of, etc.) provide randomized iteration order. The order will differ from one run of the JVM to the next. This should help applications avoid making inadvertent dependencies on iteration order.