28

I'm trying to put some key values in Map and trying to retrieve them in same sequence as they were inserted. For example below is my code

import java.util.*;
import java.util.Map.Entry;

public class HashMaptoArrayExample {

    public static void main(String args[])

    {
   Map<String,Integer> map=  new HashMap<String,Integer>();

   // put some values into map

   map.put("first",1);
   map.put("second",2);
   map.put("third",3);
   map.put("fourth",4);
   map.put("fifth",5);
   map.put("sixth",6);
   map.put("seventh",7);
   map.put("eighth",8);
   map.put("ninth",9);



    Iterator iterator= map.entrySet().iterator();
       while(iterator.hasNext())
       {
           Entry entry =(Entry)iterator.next();   
           System.out.println(" entries= "+entry.getKey().toString());
       }

    }
}

I want to retrieve the keys as below

first second third fourth fifth sixth .....

But it's displaying in some random order as below in my output

OUTPUT

ninth eigth fifth first sixth seventh third fourth second
JavaGeek
  • 1,535
  • 9
  • 39
  • 63
  • Duplicated ?? http://stackoverflow.com/questions/663374/java-ordered-map – Manuel Salvadores Jan 27 '11 at 11:45
  • java.util.LinkedHashMap and never/ever use java.util.HashMap unless you have a very strong reason for (i.e. reduced memory footprint and lack of iteration). imo, HashMap is the worst data structure in java.util (perhaps beaten by java.util.Stack only) – bestsss Jan 27 '11 at 11:49
  • @msalvadores Not exactly. That one was about entries being sorted (alphabetically, for example), this one is about them being returned in the same order they were added to the map. – biziclop Jan 27 '11 at 11:49
  • 3
    @bestsss: I take the opposite approach: use the simplest type which meets your requirements. Unless you *need* to maintain insertion order, why use a more complex (and costly) type? The vast majority of the time, HashMap does me fine. It does exactly what it says on the tin, and no more - why do you dislike it so much? – Jon Skeet Jan 27 '11 at 11:52
  • @Jon Skeet Well, in a nutshell that's what he said too. Never ever use a `HashMap`, except when it is appropiate. :) – biziclop Jan 27 '11 at 11:54
  • @Jon Skeet: it costs 2 extra references per key/value (i.e 16 bytes on x64 which is still far less than the bucket itself), but it has *predictable* and *faster* iteration. Due to predictable iteration, it allows for queuing processing, if need be. It's absolutely rare you'd need just get/put and no sync - mostly configs and they'd be better off having proper iteration. On top of that: the HashMap design in java is a bit lacking since the tree alike ones (w/ linked list for buckets) impose cache-miss on collision and bucket access overall. – bestsss Jan 27 '11 at 11:58
  • 1
    @bestsss: On the contrary, I relatively rarely iterate over a map - I'm much more likely to just use it for get/put. More importantly, when I use `HashMap` instead of `LinkedHashMap` I'm effectively *expressing* the fact that I don't care about ordering. – Jon Skeet Jan 27 '11 at 12:05
  • @Jon Skeet: ..continued: the other part is exactly the tree alike structure. Java collection framework designers opted for w/ 2^n bucket[] size instead of prime number one. 2^n doesn't need 'mod(%)' but 'and(&)' ['mod' is like 30cpu clocks, 'and' like 1] so it's good when no collisions happen. LinkedLists are probably the slowest data type to iterate through since it's very much cache-miss prone. So when there are collisions the HashMap drops performance badly. IdentityHashMap has the linear probe design which is overall faster and has *no allocation* on put. – bestsss Jan 27 '11 at 12:08
  • 1
    @bestsss: Yes, but then `IdentityHashMap` is often not what you want in terms of behaviour ;) Personally my main beef with the map classes in Java is that there's no equivalent of .NET's `IEqualityComparer` which lets you generalise the equality relationship. – Jon Skeet Jan 27 '11 at 12:12
  • @Jon Skeet: as for iteration, it's not the map main duty but it tends to happen, I like to make sure the order is preserved and impose queue alike priorities. As a small plus it makes debugging easier as well (since you can monitor the put order) – bestsss Jan 27 '11 at 12:13
  • 2
    @bestsss: Maybe we write very different apps :) I like to use the most appropriate type for my actual requirements. Using a more fully-featured type suggests I probably *need* those extra features... which can make it harder to find a different type when my requirements expand later. – Jon Skeet Jan 27 '11 at 12:15
  • @Jon Skeet: as for IdentityHashMap I am talking only about the internal design of the hashing+map (e.g Tree based vs Linear probe, need to look for Knut's chapter). Sometimes I also miss Hashprovider+EqualityComparer but they require really *herioc* inlining form the VM to avoid the virtual call (that can drop performance like 4-5 times) – bestsss Jan 27 '11 at 12:16

2 Answers2

67

You can't do this with HashMap, which doesn't maintain an insertion order anywhere in its data. Look at LinkedHashMap, which was designed precisely to maintain this order.

Jon Skeet
  • 1,421,763
  • 867
  • 9,128
  • 9,194
  • Thanks a lot. It worked great. One last question. Instead of using iterator.hasNext() can i use advanced for loop – JavaGeek Jan 27 '11 at 11:54
  • @Sukumar: Absolutely: `for (Map.Entry<..,..> entry : map.entrySet()) { ... }`. – Jon Skeet Jan 27 '11 at 12:07
  • 1
    sure you can (for x : y) is effectively compiled to iterator; hasNext(), next() – bestsss Jan 27 '11 at 12:19
  • LinkedHashMap doesn't have a method to get a specific index. In my case, I want to get the last number inserted. Can any existing DataStructures do that? – CodyBugstein Jun 28 '13 at 20:07
4

HashMap is a hash table. It means that the order in which keys are inserted is irrelevant, as they are not stored in this order. The moment you insert another key, the information about what was the last key is forgotten.

If you want to remember the insertion order, you need to use a different data structure.

Ilya Kogan
  • 21,995
  • 15
  • 85
  • 141