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

Question

I am trying figure out the order in which the values in a HashMap are/can be retrieved. Heres the code snippet for the same.

import java.util.HashMap;

public class HashMapExample {

   public static void main(String[] args) {
       HashMap<Integer, String> hashmap = new HashMap<Integer, String>();
       hashmap.put(1, "apple" );
       hashmap.put(2, "lemon" );
       hashmap.put(3, "orange" );
       hashmap.put(4, "banana" );
       hashmap.put(5, "litchi" );
       hashmap.put(6, "mango" );
       hashmap.put(7, "papaya" );

       System.out.println(hashmap.size());

       for (String key : hashmap.values()) {
           System.out.println(key);
       }
   }
}

output:

7
apple
lemon
orange
banana
litchi
mango
papaya

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 an arbitrary order. This is using Java 6.

Solution 1

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.

Solution 2

From the Javadoc: HashMap "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."

If you need consistent ordering, you can use LinkedHashMap (for insertion/access order), or TreeMap (for comparision order). Please note, that these maintain the order of the keys, not the values.

Solution 3

A LinkedHashMap is what you're after. From the doco, it differs from HashMap in that it maintains a doubly-linked list running through all of its entries

Solution 4

Try LinkedHashMap if order is important... see from JavaDoc

public class LinkedHashMap extends HashMap

Hash table and linked list implementation of the Map interface, with predictable iteration 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). Note that insertion order is not affected if a key is re-inserted into the map. (A key k is reinserted into a map m if m.put(k, v) is invoked when m.containsKey(k) would return true immediately prior to the invocation.)

Solution 5

A related collection is java.util.concurrent's ConcurrentSkipListMap. A skiplist allows you to traverse the entries in key order and also look them in random order (but not as fast as a HashMap).

There's a nice skiplist demo applet.

View more solutions

Comments

[Stephen C]

I think the OP was asking why the HashMap appears to preserving insertion order in his use-case. It is clear that he was expecting the iteration order to be more random.

[C. K. Young]

Although the ordering is for the keys, most of these maps actually store key/value entries (Map.Entry). Thus, values will most usually also appear in the same order as their associated keys.