Why does a HashMap sometimes print in natural order

Question

I was going through the introduction of Hash Map in Java and I came across that Hash Maps are unordered and unsorted. So we should get the mappings in an arbitrary order of the keys when printing the using System.out.println(HM). For example, the following code

HashMap<Integer,String> HM = new HashMap<>();
HM.put(16,"hello16");
HM.put(6, "hello6");
HM.put(1, "hello1");

prints {16=hello16, 1=hello1, 6=hello6} which is an apparently random order of keys. But when I replace the HM.put(16,"hello16"); with HM.put(15,"hello15");, it prints the mappings in the natural order of the keys, which is surprising and seems unlikely by chance:

{1=hello1, 6=hello6, 15=hello15}

I asked a friend and he said that it's related to the initial capacity (=16) of the HashMap but he couldn't explain it clearly. Can anyone explain this difference in the output with this particular example.

It doesn't really matter why this occurs, as you shouldn't rely on it. In Java 9, the insertion order of `Set#of` and `Map#of` was randomized for this reason. — Jacob G., Nov 17 '17 at 18:40
"So we should get the mappings in random order of the keys" - no. HashMap does not promise a random order. It makes no promises at all about what the order will be. — user2357112, Nov 17 '17 at 18:43
Today it might be ordered by internal buckets. Next release, it could be randomized like Go. On someone else's machine, it might be insertion-ordered like the new Python dict implementation. — user2357112, Nov 17 '17 at 18:45
"Seems unlikely by chance": You have a 1 in 6 chance of 3 values being in natural order, and you spent one chance and didn't get it. — chrylis -cautiouslyoptimistic-, Nov 17 '17 at 19:13

score 9 · Accepted Answer · answered Nov 17 '17 at 18:40

9

The hashCode of an Integer is the value itself. Your HashMap has 16 buckets, which means that the bucket that a value is assigned to is key % 16, which is a number from 0 to 15.

If your keys are in the range 0 to 15, then the bucket number is the key. Things only get messy when you use keys > 15 or < 0.

When you print a HashMap, the entries appear in bucket order. That is, a key in bucket 0 gets printed first, if there is one; then a key in bucket 1 and so on. In the case of your HashMap where all the keys are between 0 and 15, this is exactly the same as key order.

answered Nov 17 '17 at 18:40

Dawood ibn Kareem

77,785
15
98
110

1

One should not rely on that order or the bucket size. This is an internal implementation detail and could change over time (from version to version). – tobain Nov 17 '17 at 18:45
1

@tobain You're absolutely correct. But the question was, why does this happen with OP's current code. – Dawood ibn Kareem Nov 17 '17 at 18:54

score 1 · Answer 2 · answered Nov 17 '17 at 18:49

The code prints {16=hello16, 1=hello1, 6=hello6} which is random order of keys

The order may appear arbitrary, but it is deterministic. The order is based on three factors:

The values of hash codes for the keys,
The number of buckets in the hash table, and
The order the keys are inserted (for deciding the order of items with identical hash keys)

Enumerating hash table entries goes by hash bucket. Since the number of hash buckets is lower than the range of possible hash codes, the value of hash code translates into the index of hash bucket indirectly. Java implementation applies a supplemental hash function on top of the hash key, and then uses bitwise & to get the actual index:

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
...
static int indexFor(int h, int length) {
    return h & (length-1);
}

You can see from the indexFor code that length is expected to be a power of two (that's why they can use & (length-1) instead of % length expression). In your case this is important, because hash codes for integers match values of the corresponding integers. Assuming a capacity of 16 buckets, 16 would translate to bucket zero, while 15 would translate to bucket 15 (buckets are numbered from zero).

That's why the value for 15 moves from the front to the back in your example.

score 0 · Answer 3 · answered Nov 17 '17 at 18:39

HashMap uses the keys' hashCode to throw the map entries in an indexed array of buckets. The retrieval order is more or less arbitrary. As Strings of the same length, only differing in last char, have in general a hash code equal to X + last char, there is an order in them.

An other Map implementing class TreeMap is a SortedMap, and keeps the entries in order of the keys.

A yet other Map implementation is the LinkedHashMap where the order is in order of putting the entries in the map.

Why does a HashMap sometimes print in natural order

3 Answers3