CODEWITHSUNDEEP
java
Vytenis Bivainis
Vytenis Bivainis

Reputation: 2366

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

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()));
    }
}

Upvotes: 4

Views: 1594

Answers (4)

GeertPt
GeertPt

Reputation: 17874

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.

Upvotes: 2

Siddhartha
Siddhartha

Reputation: 4464

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.

Upvotes: 4

sam
sam

Reputation: 2033

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

Upvotes: 6

Scott Johnson
Scott Johnson

Reputation: 288

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.

Upvotes: 3

Related Questions