How to avoid items being re-ordered when put into java HashMap

Question

I'm creating a new Map and pushing strings into it (no big deal) -but I've noticed that the strings are being re-ordered as the map grows. Is it possible to stop this re-ordering that occurs so the items in the map retain the order the were put in with?

Map<String,String> x = new HashMap<String, String>();
x.put("a","b");
x.put("a","c");
x.put("a","d");

x.put("1","2");
x.put("1","3");
x.put("1","4");

//this shows them out of order sadly...
for (Map.Entry<String, String> entry : x.entrySet()) {
    System.out.println("IN THIS ORDER ... " + entry.getValue());
}

If it sorted its not a hash map would be more accurate. A hash map places entries is a random pattern. LinkedHashMap hides this by also remembering either the order you added them or the order they were last used. However they will still be placed in a random order in its underlying store. — Peter Lawrey, Sep 06 '11 at 21:28
What I mean is that the hashmap storage algorithm sorts entries by their hash to allow for O(log n) hash lookup (or rather, the sorting happens as a side effect of the way a hashmap stores its entries). Sorting by hash is not a random pattern, even though it may look like one due to the arbitrary nature of hash values. — tdammers, Sep 07 '11 at 07:47
@tdammers Probably a typo there -- Hashmaps strive for **O(1)** lookup on average; _treemaps_ strive for O(log n) lookup. — Ray Toal, Sep 07 '11 at 16:31
@Ray Toal: point taken - although the argument as it is stands. — tdammers, Sep 07 '11 at 17:32
@tdammers yes your argument is definitely spot on. I was just nitpicking. — Ray Toal, Sep 07 '11 at 17:48

score 24 · Accepted Answer · answered Sep 06 '11 at 19:09

24

If you care about order, you can use a SortedMap. The actual class which implements the interface (at least for most scenarios) is a TreeMap. Alternatively, LinkedHashMap also maintains its order, while still utilizing a hashtable-based container.

answered Sep 06 '11 at 19:09

dlev

48,024
5
125
132

2

Note that adding '7' to a search for the JavaDoc of a class will usually result in a link that points directly to the *latest* docs. – Andrew Thompson Sep 06 '11 at 19:33

score 16 · Answer 2 · answered Sep 06 '11 at 19:10

16

You can keep it with LinkedHashMap.

answered Sep 06 '11 at 19:10

ssedano

8,322
9
60
98

score 9 · Answer 3 · edited May 23 '17 at 12:16

9

A HashMap in java is not sorted http://download.oracle.com/javase/1,5.0/docs/api/java/util/HashMap.html. If you want predictable iteration order use a LinkedHashMap instead: http://download.oracle.com/javase/1.4.2/docs/api/java/util/LinkedHashMap.html

Heres a good discussion on the difference: How is the implementation of LinkedHashMap different from HashMap?

edited May 23 '17 at 12:16

Community

1
1

answered Sep 06 '11 at 19:10

bittersweetryan

3,383
5
28
42

Note that adding '7' to a search for the JavaDoc of a class will usually result in a link that points directly to the *latest* docs. – Andrew Thompson Sep 06 '11 at 19:33

score 4 · Answer 4 · answered Sep 06 '11 at 19:13

The previous answers are correct in that you should use an implementation of Map that maintains ordering. LinkedHashMap and SortedMap each do these things.

However, the takeaway point is that not all collections maintain order and if order is important to you, you should choose the appropriate implementation. Generic HashMaps do not maintain order, do not claim to do so and cannot be set to do so.

How to avoid items being re-ordered when put into java HashMap

4 Answers4

Linked

Related