69

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.

Improve this question
2
  • 8
    Just use a LinkedHashMap. Commented Sep 30, 2015 at 14:19
  • @Raedwald Okay, but she did ask about insertion order multiple times, and it seems like LinkedHashMap is probably worth looking at. Commented Nov 20, 2017 at 16:17

7 Answers 7

Reset to default
96

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

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.
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.
There is a difference between "we don't guarantee the order" and "we guarantee the order will look and/or actually be random". There's no reason for OP to expect that the data will look random.
84

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

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 artifact of the hash table implementation and the specific hashCode method. It is not something that you can (or should) sensibly make use of. Not least because it can change (and has changed) from one Java release to the next!

1 - Or in Java 8 or later, if congestion of a particular hash bucket / hash chain causes it to switch from a simple list to a red-black tree. Deep implementation detail. If you are curious, read the source code!

Improve this answer

Comments

11

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

Improve this answer

Comments

7

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

Improve this answer

Comments

1

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.

Improve this answer

Comments

1

The Answer by Stephen C is correct, explaining the details behind what you saw.

In addition, as of Java 21 there is another way to view the matter. Java 21 brought us sequenced collections.

SequencedMap

Map implementations with a defined encounter order are now represented by the interface SequencedMap, as of Java 21+.

Maps whose entries are ordered based on the content of the key have long been represented by the interface SortedMap and its successor NavigableMap. But these two interfaces did not cover other orders. Specifically these did not cover the LinkedHashMap that tracks insertion-order.

The new SequencedMap interface covers all of these. Every map interface and implementation built into Java with a defined encounter order is covered by SequencedMap.

So we can answer your question “Does HashMap maintain an encounter order based on insertion?” merely by glancing at the Javadoc for SequencedMap. That interface’s Javadoc lists three concrete implementations, and HashMap is not one of them. So, no, HashMap does not maintain an encounter order.

SequencedMap < Integer , String > sequencedMap = new LinkedHashMap<>() ; // Maintains insertion-order.
Improve this answer

Comments

-1

No, the order is not preserved in case of HashMap (if you want sorted implementation.) In case you want keys to be sorted, you can use TreeMap.

for example - {[3=1],[2=50],[20=4],[14=1]} -> HashMap

for TreeMap, you get - {[2=50],[3=1],[14=1],[20=4]} -> TreeMap

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.