Is map/collection order stable between calls?

Question

If I have a hash map and iterate over the objects repeatedly, is it correct that I'm not guaranteed the same order for every call? For example, could the following print two lines that differ from each other:

Map<String,Integer> map = new HashMap<String,Integer>()
  {{ put("a", 1); put("b", 2); put("c", 3); }};
System.out.println(map);
System.out.println(map);

And is this the case for sets and collections in general? If so, what's the best way in case you have to iterate twice over the same collection in the same order (regardless of what order that is)? I guess converting to a list.

Answer 1

you're correct, the order of a map is not guaranteed. you might want to look at something like TreeMap if you need the order to stay the same between calls.

having said that, chances are that code will print out the same thing twice, it's just not guaranteed.

Answer 2

The contracts of Map and Set do not make any guarantees about iteration order, but those of SortedSet and SortedMap (implemented by TreeMap and TreeSet) do.

Furthermore, even the non-sorted implementations generally behave deterministically and have a repeatable iteration order for each specific instance, as long as it's not modified in any way. However, that's an implementation detail and should not be relied upon.

Answer 3

When using a HashMap, there's no guarantee that the iteration order will be the same on each iteration.

Instead, consider a LinkedHashMap, which is a hash table with a predictable iteration order.

Answer 4

I don't think any of the existing answers are quite speaking to exactly what you're asking about. Sure, a HashMap with certain contents may not iterate in the same way as a different one with equal contents, or in a different VM invocation, or running on different JDK versions, etc. But you're just asking whether that exact instance, if not modified, will iterate the same way as itself.

This is a good example of a de facto specification. It's true that it is not present in the letter of the spec that this will be the case. However, every single JDK collection behaves this way (provided, in the case of an access-ordered LinkedHashMap, that you iterate all the way through each time). And it is difficult to conceive of a collection implementation that would not have this property. I've implemented and reviewed many collections and there was just once that I considered a collection that would iterate differently each time; it was an extremely strange case and I ended up throwing out the whole idea because iterating differently each time was just too damn weird (that is, violated that de facto specification I mentioned).

So I say go ahead and depend on it. That's not a blanket recommendation to depend on any old unspecified behavior you want. But in this case, it's just not going to hurt you.

Answer 5

While the library spec does not guarantee that the order remains the same over time, it probably will be identical as long as the underlying data structure (i.e., the arrays that implement the hash table) are not altered. So as long as you don't insert or remove items from the hash table, it's not unreasonable to assume that the entry order will not change.

Looking at a typical implementation of HashMap shows this to be the case, such as the one at: http://www.docjar.com/html/api/java/util/HashMap.java.html

That being said, it's not something your code should rely on.