0

I'm learning about HashMaps in Java and I'm confused about the iteration order. The documentation states that HashMap doesn't guarantee any specific iteration order, but in my simple test, the order seems to remain consistent:

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. Java 11 Docs

import java.util.HashMap; public class HashMapDemo { public static void main(String[] args) { HashMap<String, String> dishes = new HashMap<>(); // Adding more elements with complex keys dishes.put("dish-1234", "Pho"); dishes.put("dish-5678", "Spicy Beef Noodle Soup"); dishes.put("dish-9012", "Broken Rice"); dishes.put("dish-3456", "Banh Mi"); dishes.put("dish-7890", "Hu Tieu"); dishes.put("dish-2345", "Mi Quang"); dishes.put("dish-6789", "Crab Noodle Soup"); dishes.put("dish-0123", "Rolled Rice Cake"); System.out.println("First time:"); dishes.forEach((id, name) -> System.out.println(id + ": " + name)); // Create new HashMap with same data HashMap<String, String> dishes2 = new HashMap<>(); dishes2.putAll(dishes); System.out.println("\nSecond time (New HashMap):"); dishes2.forEach((id, name) -> System.out.println(id + ": " + name)); } }

Output:

First time: dish-7890: Hu Tieu dish-3456: Banh Mi dish-2345: Mi Quang dish-1234: Pho dish-0123: Rolled Rice Cake dish-5678: Spicy Beef Noodle Soup dish-9012: Broken Rice dish-6789: Crab Noodle Soup Second time (New HashMap): dish-7890: Hu Tieu dish-3456: Banh Mi dish-2345: Mi Quang dish-1234: Pho dish-0123: Rolled Rice Cake dish-5678: Spicy Beef Noodle Soup dish-9012: Broken Rice dish-6789: Crab Noodle Soup

I understand that if I need guaranteed order, I should use LinkedHashMap or TreeMap, but I'm trying to understand the actual behavior of HashMap. I read some documentation talk about re-size and re-hashing, maybe it's too hard to understand for me.

I also read some post say this problem, but I can not re-produce

How can I understand this?

Improve this question
5
  • 8
    it also makes no guarantees that the order will change over time; and you have not tested all implementations neither did you cover ALL time -- probably (not guaranteed) you will get the same content if the map is created the same way Commented Nov 23, 2024 at 16:49
  • 1
    example where inserting an element ("seven") changes the output order: IDEone inserting up to "six" does not change the order of previous elements (relative to each other, maybe the new element is inserted (in iterator order) between two existing ones, but after inserting "seven" the order of previous elements is changed (e.g. "four" and "one" were last , moved to 2nd and 3rd position) - certainly additional buckets were created Commented Nov 23, 2024 at 17:06
  • 1
    or this ! Same content iterated in different order after adding and removing the same element (based on previous example) Commented Nov 23, 2024 at 17:15
  • The fact that there are no guarantees as to the order of the map does not prohibit some examples from being consistent with each other. The "no guarantees" clause is a warning you should not depend on consistency. Commented Nov 23, 2024 at 20:29
  • 1
    Try making this change: HashMap<String, String> dishes2 = new HashMap<>(2000); Commented Nov 23, 2024 at 20:34

4 Answers 4

Reset to default
8

Behavior may vary

trying to understand the actual behavior of HashMap

You are trying to understand the internal implementation details of HashMap. Don’t.

Whatever behavior you may observe, that behavior may vary.

  • The behavior may vary at runtime. The implementation programmers may have written the behavior to change depending on the quantity of elements, or their types, or their content. The iteration order may even change each time you loop through the map.
  • The behavior may vary with any new release. The programmers are free to change their implementation at any time, as long as they comply with the contract promised in the Javadoc.

The Javadoc is the contract

If the Javadoc says you cannot count on a particular order, then do not depend on a particular order.

If the Javadoc does not promise thread-safety, then do not expect thread-safety.

The Javadoc is the formal contract, the agreement between you and the implementation programmers. Do not make assumptions, do not use your intuition. What you read in the Javadoc describes the expected behavior. Anything beyond the Javadoc may exist, may not exist, or may vary, but should never be expected by you.

SequencedMap

For a particular order, use an implementation of SequencedMap. Implementations bundled with Java: ConcurrentSkipListMap, LinkedHashMap, and TreeMap. To learn about the Sequenced Collections API added to Java 21, read JEP 431, and see excellent talk by Stuart Marks.

Java offers two other ordered map interfaces: NavigableMap (Java 6+) and SortedMap (Java 2+), both implemented by two of those three classes named above: ConcurrentSkipListMap and TreeMap.

Consider using TreeMap first, if thread-safety is not a concern. Very large amounts of data may perform better with ConcurrentSkipListMap.

Diagram of Map class hierarchy in Java 21+, by Basil Bourque, 2024-11

Mermaid coding:

--- title: Java Map hierarchy --- classDiagram Map <|-- SequencedMap SequencedMap <|-- SortedMap SortedMap <|-- NavigableMap NavigableMap <|-- ConcurrentNavigableMap NavigableMap <|.. TreeMap : implements ConcurrentNavigableMap <|.. ConcurrentSkipListMap : implements SequencedMap <|.. LinkedHashMap : implements class Map { <<interface>> } class SequencedMap { <<interface>> } class NavigableMap { <<interface>> } class SortedMap { <<interface>> } class ConcurrentNavigableMap { <<interface>> } class TreeMap { } class ConcurrentSkipListMap { } class LinkedHashMap { }

Third-parties

You may find third-party implementations of ordered maps, such as in Google Guava or Eclipse Collections.

Curiosity

If curiosity drives you to learn about the implementation details of HashMap, learn the basic concepts such as at Wikipedia, then study the open source code on GitHub.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

3

This is explainable. First some relevant facts:

  1. You are using a key type (String) that has a hashCode method whose algorithm is specified, and that is guaranteed to give the same hashcode value for all runs1.

  2. You are inserting the same key / value pairs in precisely the same order each time.

Given the above, the implementation of HashMap that you are using is going to give you a consistent order for the keys. If you were prepared to analyze the source code, you would be able to see why.

However, this is an artifact of the current implementation ... and the way that you are using it.

  • If you switched to a different JVM with a different HashMap implementation, you might get a different ordering. (Especially if you inserted many more distinct keys.)

  • If you changed the key to a type whose hashCode could be different for different runs, then the ordering would be different. For example, if you used StringBuffer instead of String2.

What your real mistake is here is a misunderstanding of what the javadoc is saying. When it says "this class makes no guarantees as to the order of the map", it is not saying that the ordering WILL be inconsistent. What it is saying is that it COULD be inconsistent.

Note that "could be inconsistent" logically implies "could be consistent".

So the fact that you have found a scenario where you (appear to3) get a consistent order is not surprising. And it doesn't contradict the javadoc!

1 - Indeed, the algorithm is the same for all versions of Java.
2 - This is for demo purposes only: it is the wrong thing to do for other reasons.
3 - Your test is not sufficient to show that your platform will give consistent orderings if, for example, the keys are dynamic, or there are a huge number of key value pairs, or the insertions are done in a different sequence.

Improve this answer

Comments

1

First of all hash maps is a standard computer science data structure. There are variations, but it is worthwhile looking into Wikipedia and such.

The data structure HashMap (in java) uses fixed sized buckets (arrays) in which the items are stored by an index being the item's hash key modulo the array size. When two different items collide by getting the same index rehashing must be done, a next index taken. This means that with growing hash maps restructuring of the buckets may happen. Hence:

Over time the order is not guaranteed.

You could artificially keep filling a HashMap till the item order starts changing. After some addition the order will fail.

For instance (untested):

List<String> order = new ArrayList<>(); Map<String, String> map = new HashMap<>(); for (;;) { key = ... read from dictionary String oldKey = map.put(key, value): if (oldKey == null) { // Time to check the order: List<String> nextOrder = new ArrayList<>(map.keySet()); for (int i = 0; i < nextOrder.size(); ++i) { if (i == order.size() || !order.get(i).equals(nextOrder.get(i)) { if (nextOrder.get(i).equals(key)) { orders.add(i, key); } else { System.out.println("Order changed"); return; } } } } }
Improve this answer

Comments

1

Here is some explanation on what goes on under the hood.

  1. The insertion of elements in a HashMap is not dependent on the order in which they are added. Instead, it relies on the hash code of the key and the availability of slots in the map’s internal array.
  2. If the computed slot for a key is already occupied (due to a hash collision), the HashMap resolves this by either chaining or probing. This resolution process does not preserve insertion order and can involve traversing or modifying multiple slots.
  3. When the map’s capacity is exceeded, a new, larger map is created, and all existing entries are rehashed and redistributed. This rehashing process ignores the original insertion order entirely.
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.