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.