Iteration order of java.util.HashMap.values()

Question

Is it guaranteed that keys and values in standard implementations of java.util.Map are returned in the same order? For example, if map contains mapping x1 -> y1 and x2 -> y2, then if keySet() iteration yields x1, x2, is it guaranteed that values() iteration will yield y1, y2 and not y2, y1? I haven't seen anywhere guaranteed that this is true, but it seems to work. Could anyone give confirm or deny this premise and give counterexample?

public class MapsTest {
    @Test
    public void hashMapKeysAndValuesAreInSameOrder() {
        assertKeysAndValuesAreInSameOrder(new HashMap<>());
    }

    @Test
    public void treeMapKeysAndValuesAreInSameOrder() {
        assertKeysAndValuesAreInSameOrder(new TreeMap<>());
    }

    private void assertKeysAndValuesAreInSameOrder(Map<Integer, Integer> map) {
        Random random = new Random();
        IntStream.range(0, 100000).map(i -> random.nextInt()).forEach(i -> map.put(i, i));
        assertEquals(new ArrayList<>(map.keySet()), new ArrayList<>(map.values()));
    }
}

I don't think you can rely on it since the documentation of `values()` does not mention this point. — Alexis C., Oct 19 '15 at 21:23
I guess this feature is part of public contract despite the fact that it's not documented. By the way, I just remembered Linus Torvald's posts "We never break userspace". — Vytenis Bivainis, Oct 19 '15 at 21:29

score 6 · Answer 1 · edited May 23 '17 at 12:24

From the doc of 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.

If you look at its code, you will find out that once you call put(), eventually hash is calculated, entry object is created and added into a bucket array. I have over simplified the purpose of the code just to explain what happens behind the scene.

If you want guaranteed order, use LinkedHashMap or TreeMap depending on your requirements

Also check,

Difference between HashMap, LinkedHashMap and TreeMap

score 4 · Answer 2 · edited May 23 '17 at 12:16

Interesting question. I gave it a shot. and it seems the RELATIVE ordering of the keys remains in sync with the values.

import java.util.*;
public class MapClass {
public static Map<String, Integer> map = new HashMap<>();

  public static void main (String[] args){
    map.put("first", 1);
    map.put("second", 2);
    map.put("third", 3);
    map.put("fourth", 4);
    map.put("fifth", 5);

    System.out.println(map.keySet());
    System.out.println(map.values());

    map.put("sixth", 6);
    System.out.println(map.keySet());
    System.out.println(map.values());

    map.remove("first");
    System.out.println(map.keySet());
    System.out.println(map.values());
  }
}

I get:

[third, fifth, fourth, first, second]
[3, 5, 4, 1, 2]
[sixth, third, fifth, fourth, first, second]
[6, 3, 5, 4, 1, 2]
[sixth, third, fifth, fourth, second]
[6, 3, 5, 4, 2]

This simple example seems to show that while a HashMap will not preserve the order of insertion, it seems it does preserve the relative ordering of keys and values.

keyset() and values() does not guarantee any order though, but it seems in practice that it'll return the same order for multiple invocations. As the comment on there says, even if you could rely on it, it's questionable whether you should.

score 3 · Answer 3 · answered Oct 19 '15 at 21:11

3

From the HashMap docs:

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.

answered Oct 19 '15 at 21:11

Scott Johnson

288
2
12

1

I saw this sentence but in my opinion it doesn't say anything about the relationship of order of keys() and values(). – Vytenis Bivainis Oct 19 '15 at 21:18
It could, but it doesn't. I wonder if anyone could give me an example. – Vytenis Bivainis Oct 19 '15 at 21:31
I thought ConcurrentModificationException would be thrown. And these maps are not thread-safe, so concurrency is not an issue for me. – Vytenis Bivainis Oct 19 '15 at 21:40

GeertPt · Answer 4 · 2015-10-19T21:33:32.557

2

Looking at http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java#HashMap.values%28%29, I'd guess it works because both the KeyIterator and ValueIterator extend HashIterator.

But that's only if you don't change the HashMap in the mean time, e.g. adding and removing items between calling keySet() and values(), because that can change the bucket size, and the HashIterator will behave differently.

edited Oct 19 '15 at 21:33

answered Oct 19 '15 at 21:25

GeertPt

16,398
2
37
61

Tests still pass with `...forEach(i -> { map.put(i, i); map.values(); }` – Vytenis Bivainis Oct 19 '15 at 21:30
If you do System.out.println(map.keySet());, then add a 100000 items, remove all 100000 again, and then print the map.values(), you might have different results... – GeertPt Oct 19 '15 at 21:39
Same story with `TreeMap`? All iterators extend `PrivateEntryIterator` http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/TreeMap.java#TreeMap.EntryIterator – Vytenis Bivainis Feb 01 '17 at 22:26
A TreeMap is a SortedMap. So it's required to keep the same order over all it's iterators. http://docs.oracle.com/javase/7/docs/api/java/util/SortedMap.html "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. (This interface is the map analogue of SortedSet.)" – GeertPt Feb 02 '17 at 09:20
This post is about relative order of keys() and values(), not about absolute order of keys(). – Vytenis Bivainis Feb 02 '17 at 16:58

Iteration order of java.util.HashMap.values()

4 Answers4