HashMap order of insertion

Question

Why does the HashMap retrieve in an ordered manner, when it is know that HashMap stores and retrieves element in an unordered manner

HashMap m = new HashMap();
m.put("A", 1);
m.put("B", 2);
m.put("C", 3);
m.put("D", 4);
m.put("E", 5);

Set keySet = m.keySet();
Iterator it = keySet.iterator();
while(it.hasNext())
{
    System.out.println(m.get(it.next()));
}

OUTPUT - 1 2 3 4 5

*"when it is know that HashMap stores and retrieves element in an unordered manner"* Just to make that clear: this doesn't mean that `HashMap` will jumble your elements just to be unordered. It just means that you can't rely on any order. It still can happen that you can get and "ordered" output. — Tom, Feb 23 '16 at 20:48

score 3 · Answer 1 · answered Feb 23 '16 at 20:32

3

In short: you got lucky. HashMap generally returns elements in an arbitrary nonsensical order, and this case happened to be one where all the elements came out in order.

answered Feb 23 '16 at 20:32

Louis Wasserman

191,574
25
345
413

But everytime i run this. It gives me the same order – Arijit Dasgupta Feb 23 '16 at 20:35
1

HashMap's implementation relies on the keys' hashCode, which for strings will be the same for each run. Try changing your keys and see what happens. – Steve Kuo Feb 23 '16 at 20:36
1

@ArijitDasgupta It's not random, it's just not specified. The implementation makes no guarantees. It's not the run that got lucky, it's your choice of keys that got lucky. – Louis Wasserman Feb 23 '16 at 20:37

Sleiman Jneidi · Accepted Answer · 2016-02-23T21:43:54.383

3

It just happened that hashCodes of A B C D E are ordered increasingly in this particular case.

 while(it.hasNext())
 {
    String next = it.next();
    System.out.println(next.hashCode() + " "+ m.get(next));
 }

Will produce the following

However, this doesn't mean that every time you have an increasingly ordered set of hash codes, map-entries will be stored in their hashCodes' order.

edited Feb 23 '16 at 21:43

answered Feb 23 '16 at 20:38

Sleiman Jneidi

22,907
14
56
77

Just because the hashes are ordered doesn't mean they're ordered in the actual `HashMap`. There's some more messing around with the hash code before it actually gets used as the index. – Louis Wasserman Feb 23 '16 at 20:56
sure, the mod hash and the hash table size plays a role, I don't know how to word this though :( – Sleiman Jneidi Feb 23 '16 at 20:58
1

That's pretty much why I didn't try. The messing about can take any form, and _does_ vary between different Java implementations; the order for these elements would be different in different Java versions. That's why I deliberately left it open-ended why these elements got put in the right order: because there was never any guarantee that they'd stay in the right order. – Louis Wasserman Feb 23 '16 at 20:59
1

it looks like http://stackoverflow.com/a/2144822/869736 actually has a pretty great answer. I'm inclined to mark this as a duplicate just for that answer being really good. – Louis Wasserman Feb 23 '16 at 21:05

score 0 · Answer 3 · answered Feb 23 '16 at 20:43

Because of 2 things:

The implementation of String's hashCode() method.

This is the implementation of hashCode() for String:

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

For one-character strings, it's simply the Unicode value of that character. Those letters (A-E) have consecutive values (65-69).

The HashMap class modifies the hash a little bit, but in this case with such low values, the value is unaffected.

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

The default number of buckets in a HashMap is 16.

HashMap will reduce the hash code modulo the number of buckets to find the bucket number for the key. In this case, the bucket number are all sequential -- 1, 2, 3, 4, 5. So, the iterator iterated over the buckets in order.

If any of these things were to happen, some of which are not in the HashMap contract and are not in your control, then the iteration order may change.

Add other keys that don't have the same quotient modulo 16, e.g. "Z", "a", "AA".
Create a map with a smaller default capacity.
Java decides to mess with the hash method internal to HashMap.
Java decides to mess with the algorithm mapping the hash code to the bucket number internal to HashMap.
Java decides to mess with the hashCode method in String.

HashMap order of insertion

3 Answers3

Related