Is the Order of Values Retrieved from a Hashmap the Insertion Order

Is the order of values retrieved from a HashMap the insertion order

The values are printed in the order in which they have been inserted. Is this true in general? I was expecting the values to be printed in random order.

The HashMap API does not define the order of iteration.

However, if you look at the implementation of HashMap, you can deduce that there is a complex transient relationship between the iteration order, the keys' hash values, the order in which the keys were inserted and the size of the hashtable. This relationship gets scrambled if the hashtable resizes itself.

In your case, you are using Integer keys which means that the hash values of the keys are the key values themselves. Also, you inserted the entries in key order. This leads (fortuitously!) to the iteration order matching the insertion order. But if you kept inserting more keys, you would find that the iteration order "wraps around". Then as the table goes through a series of resizes, the order will get progressively more and more scrambled.

In short, what you are seeing is an artefact of the hashtable implementation, and not something that you can (or should) sensibly make use of. Not least because it could change from one Java release to the next.

Hashmap + Insertion Order

I have executed below code and for 10,000 times response is returned in same ordered.

That's just what happens to occur with the version you're using and the values you're inserting. There's no guarantee it will continue to occur, or that insertion order is maintained if you add different values, or if you remove items then add others.

Basically, it's not saying that it definitely won't be in a particular order - it's saying that you absolutely should not rely on it being in that order.

Also note that if you expected insertion order to be maintained, your examples already demonstrate that it's not. The output shows items not being presented in insertion order.

LinkedHashMap will maintain insertion order, by maintaining a linked list of entries alongside the hash map internally. (An exception here is that there's a constructor which allows you to specify that items will be presented in access order rather than insertion order, which is usually used when you want this as the basis of a cache.)

Hashmap put(), is it always ordering?

HashMap doesn't preserve the order of insertion. However if you use the values 0 to 10 in order, these happen to be hashed to the buckets 0 to 10 internally and placed in an array in that order. When you iterate of the HashMap you are looking at these buckets in order. Note: this implementation could change in the future and this might not happen.

The default size of a HashMap is 16 and with a load factor of 0.7 you can add 11 values without it resizing. This means when you view these values, the current implementation happens to place 0 to 10 in sorted order.

If you only need the values 0 to 10 be in order, I suggest using an array, instead of a HashMap.

HashMap order of insertion

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

65 1
66 2
67 3
68 4
69 5

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.

How does Java order items in a HashMap or a HashTable?

java.util.HashMap is unordered; you can't and shouldn't assume anything beyond that.

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.util.LinkedHashMap uses insertion-order.

This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).

java.util.TreeMap, a SortedMap, uses either natural or custom ordering of the keys.

The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

Iteration Order of HashMap key same or not

If you don't make any changes to the HashMap between the two iterations, you'll likely see the same iteration order (even though it's not guaranteed), since this is a deterministic data structure. However, adding or removing entries between the two iterations will probably change the iteration order.

If you want to rely on the iteration order, use LinkedHashMap, in which (by default) the keys are iterated in the order they were first added to the Map.

If you want to iterate over the keys in some specific order, you can use TreeMap instead (where the keys are ordered according to their natural ordering or the supplied Comparator).

Does HashMap keeps its order (not insertion order)

Yes. It will keep its order if no new items are added. An idle map does not just decide to rearrange itself. But that order is non deterministic and can change once items are added.

Is the order guaranteed for the return of keys and values from a LinkedHashMap object?

The Map interface provides three
collection views, which allow a map's contents to be viewed as a set
of keys, collection of values, or set
of key-value mappings. The order of
a map is defined as the order in which
the iterators on the map's collection
views return their elements. Some map
implementations, like the TreeMap
class, make specific guarantees as to
their order; others, like the
HashMap class, do not.

-- Map

This linked list defines the iteration
ordering, which is normally the order
in which keys were inserted into the
map (insertion-order).

-- LinkedHashMap

So, yes, keySet(), values(), and entrySet() (the three collection views mentioned) return values in the order the internal linked list uses. And yes, the JavaDoc for Map and LinkedHashMap guarantee it.

That is the point of this class, after all.

---

Related Topics