Insertion Order for a HashMap

[Nitin Pathak]

Out of curiosity, I was wondering what is the order of traversal of a HashMap as it is definitely NOT the insertion order!

[Joanne Neal]

Have you read the Javadoc for the HashMap class ?
[ December 17, 2008: Message edited by: Joanne Neal ]

[Sridhar Santhanakrishnan]

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

I tried out an example and have come to an assumption that the order probably remains definite upto a certain point of time.
Tried debugging the code sample and find that it stores the entries as an array.

And the traversal order is the reverse order of the array from the last to the first.

[Nitin Pathak]

Hey Joanne! Yes, I did gave a glance but wanted to just get an idea from the Ranchers about their experience with the HashMap, whether this is the by-product of performance, hash function and so on.

Thank you for your post!

[Nitin Pathak]

Originally posted by Sridhar Santhanakrishnan:


I tried out an example and have come to an assumption that the order probably remains definite upto a certain point of time.

Thanks Sridhar! My experience of a definite pattern was constant until recently I generated larger keys and equally complex values; and the pattern broke right after 2 entries.

[Sridhar Santhanakrishnan]

Tried out using upto 6 digit key value pairs and still find that the order of traversal is the reverse order of the array (as probably the HashMap is stored).


Did you find a similar behaviour Nitin?

[Nitin Pathak]

My key was more than 10 characters, as far as I can recall. Let me check for the shorter versions of key lengths (as long as 6 chars). Would be posting my results shortly

[Campbell Ritchie]

Chances are, the order will depend on the size of the collection; if you have a 0.75f load factor, it will change from capacity 0x10 (16) to capacity 0x20 (32) when you get to (or maybe beyond, not sure which) size 0xc (12).
Under size 0xc it will sort on hashCode() & 0xf and from size 0xc to size 0x18 (24) it will sort on hashCode() & 0x1f.

So I would expect the retrieval order to change whenever the capacity changes.

[Nitin Pathak]

Thanks Campbell for the informative post! That clears things up since, I kept blaming the hashCode() for my lack of answers to it.

[Henry Wong]

As a side note to this topic -- if you want insertion order during traversals, you csn use the LinkedHashMap class.

Henry

[Rob Spoor]

Originally posted by Henry Wong:
As a side note to this topic -- if you want insertion order during traversals, you csn use the LinkedHashMap class.

Henry

But be careful if you have created it specifying it should use access order - the get method modifies your map and if you do that while iterating you will get a ConcurrentModificationException:

for (Object key: map.keySet())
{
    Object value = map.get(key); // modifies while iterating; exception!
}

If you do this, then always iterate using the entries if you need both the keys and values:

for (Map.Entry entry: map.entrySet())
{
    Object key = entry.getKey();
    Object value = entry.getValue();
}

[Nitin Pathak]

Loud and clear! But, referring to Javadoc for ConcurrentModificationException, this extends RuntimeException. If this is the case for get() operation over a LinkedHashMap instance, doesn't it make sense for the compiler to suggest the quick fixes (in other words, why doesn't it throw the exception at the compile time)?

[Campbell Ritchie]

Because it is difficult for the compiler to predict whether an iterator and a get() or put() are happening at the same time. Particularly in a threaded environment.