This week's book giveaway is in the Jobs Discussion forum.
We're giving away four copies of Soft Skills and have John Sonmez on-line!
See this thread for details.
The moose likes Beginning Java and the fly likes HashMap data ordering Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Soft Skills this week in the Jobs Discussion forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "HashMap data ordering" Watch "HashMap data ordering" New topic
Author

HashMap data ordering

Paul Mrozik
Ranch Hand

Joined: Feb 10, 2013
Posts: 117

I've been messing around with Collections and I'm having trouble understanding the output of my program here.

All the program is supposed to do is insert data into a HashMap and then print it. The Country class, used as the key here, has equals() and hashCode() overridden. The hashCode() method returns the id value that the country is initialized with. So if you look at the code snippet below, the id for United States is 82 and so also becomes the hash code value.



And the output:


France (34): Francois Hollande (1) Hashcode: 34
Brazil (19): Dilma Rouseff (6) Hashcode: 19
United Kingdom (21): David Cameron (3) Hashcode: 21
Germany (96): Joachim Gauck (2) Hashcode: 96
United States (82): Barack Obama (4) Hashcode: 82
Australia (24): Julia Gillard (5) Hashcode: 24



Now, I thought that the data inside the HashMap is ordered by the hash code, but it looks totally random to me in the output.

Here's what I totally don't understand though. Once I change the initialization values for the different countries, so that we have:



The output is now:


France (1): Francois Hollande (1) Hashcode: 1
United States (2): Barack Obama (4) Hashcode: 2
Germany (3): Joachim Gauck (2) Hashcode: 3
Brazil (4): Dilma Rouseff (6) Hashcode: 4
United Kingdom (5): David Cameron (3) Hashcode: 5
Australia (6): Julia Gillard (5) Hashcode: 6


This time the data is printed out in order. Why?

Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4181
    
  21

Paul Mrozik wrote:...Now, I thought that the data inside the HashMap is ordered by the hash code, ...

That is your problem right there. The HashMap is unordered. From the API: "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."


Steve
Paul Mrozik
Ranch Hand

Joined: Feb 10, 2013
Posts: 117

Makes perfect sense. Here's the exercise from Thinking in Java:

9. Fill a HashMap with key-value pairs. Print the results to show ordering by hash code. Extract the pairs, sort by key, and place the result into a LinkedHashMap. Show that the insertion order is maintained.


I must have misunderstood something here. Since I'm asked to sort by key later, then something different was meant by show ordering by hash code.
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Paul Mrozik wrote:Makes perfect sense. Here's the exercise from Thinking in Java:

9. Fill a HashMap with key-value pairs. Print the results to show ordering by hash code. Extract the pairs, sort by key, and place the result into a LinkedHashMap. Show that the insertion order is maintained.


I must have misunderstood something here. Since I'm asked to sort by key later, then something different was meant by show ordering by hash code.


Yeah, it is a little unclear. Presumably the author meant something like, "to show that ordering is based on the hashcode (though not necessarily in a predictable way) as opposed to insertion order." The key point being not that it will be in increasing order of hashcode (obviously it's not) but that it won't be based on insertion order.

And it almost certainly is based on hashcode (which you can verify yourself by examining the source in src.zip in the JDK downlaod). The thing is, there's a second hashing going on.

The range of hashcode is all possible int values. A little over 4 billion possibilities. The way HashMap works is that the hashcode determines which bucket our entry goes in, where a bucket is just a list of the elements that have the same hashcode. It wouldn't make sense for the map to create 4 billion buckets, so it creates some smaller number, and re-hashes our key's hashcode value into a range that matches the number of buckets. I would assume the iteration order then just goes through the buckets in their index order, and then within a bucket it goes through that bucket's elements in insertion order. Just a guess, but it seems the most natural approach. The second hash is a pretty messy combination of bit-fiddling and dark spells from the elder gods, so mere mortals can't tell just by looking at a group of entries which ones will go in which buckets.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: HashMap data ordering