Order of values retrieved from a HashMap

Question

Hi all,

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 random order.

Thanks.

ps: using java 6

Answer 1

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.

Answer 2

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.)

Answer 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

Answer 4

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, the hash values of the keys are the key values themselves, and you inserted the entries in key order. So it just happens that the iteration order matches the insertion order. But if you keep inserting more keys, you will find that order wraps around and then gets progressively more scrambled.

The short of it is that you are seeing artifact of the hashtable implementation, and not something that you can (or should) make use of.

Answer 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.

Answer 6

Hi all,

Thank you for your answers.

I figured that when I give the keys in an acending order, the result is printed in the order in which the values are inserted(in an ascending order as well). However, when the keys are given in a random order, the values are printed in a another random order.

Thanks.

Edit: Thanks, Stephen. I get it now.