• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

HashMap data ordering

 
Ranch Hand
Posts: 117
Mac Chrome Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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?

 
Bartender
Posts: 4179
22
IntelliJ IDE Python Java
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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."
 
Paul Mrozik
Ranch Hand
Posts: 117
Mac Chrome Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
How do they get the deer to cross at the signs? Or to read this tiny ad?
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic