Thursday, March 22, 2007

HashMap Behavior in JDK6

It is important to read the documentation. Lots of people don't seem to do this, and they get bitten by it.

The iterator for java.util.HashSet is documented as follows:

Returns an iterator over the elements in this set. The elements are returned in no particular order.

Of course, I've now seen code that ignores this, so I thought I would draw a few underlines for the kind of folks who miss it. I wish to state for the record that I did not write this code.

It turns out that HashSets (and HashMaps) don't just use the user-defined hashCode as the hash value for objects they are passed. They rehash the number that method returns with their own hash function, to defend against poor quality hash functions. This makes a lot of sense, as many people write bad hash functions.

Anyway, this means that when they change this function, objects will hash to different places. Then, when iterators visit these items, they will be visited in a different order.

I wouldn't be posting this unless they had changed it between JDK5 and JDK6, of course. For a quick illustration:

import java.util.HashSet;

public class Test {
  public static void main(String [] args) {
   HashSet<string> set = new HashSet<string>();
   set.add("axons");
   set.add("bandrils");
   set.add("chumblies");
   System.out.println(set);
  }
}

Run that in JDK5, and it will print "[chumblies, bandrils, axons]". Run it in JDK6, and it will print "[axons, bandrils, chumblies]".

If you are having trouble switching from JDK5 to JDK6, and this comes up in your code, smack your forehead with your palm, say, "duh!", and move on with your life.

8 comments:

Anonymous said...

The order can also change if the capacity is changed.

LinkedHashMap can be useful.

mk said...

Just to clarify:

This discussion concerns an internal hashcode and doesn't relate to the HashSet/HashMap's own publicly visible hashcode() method. In other words, if you had code like this:


HashSet set = new HashSet();
set.add("foo");
set.add("bar");
System.out.println("hash is: " + set.hashCode());


Then you should still see the same value in any version of the JDK.

Jeremy Manson said...

Mickey --

It's not a good idea to rely on behavior like that. The value returned by a hashCode invocation isn't documented to be the same across multiple implementations.

In other words, the value printed out by that program might coincidentally the same in any two versions of the JDK, but they could change it tomorrow without violating any rules.

Having said that, it is true that the behavior you were describing and the behavior I was describing are two different things.

Raghavan alias Saravanan M said...

Good catch! It seemed to be satisfying the very own doubt of mine at the moment and Mr. Google helped me land here!

Its because of the uncertainty of the ordering of elements in hashmap - to put in a simple way! Still, my question is a little different. If time permits, pay a visit here -> http://www.coderanch.com/t/431661/Java-General-intermediate/java/HashMap-JDK-Vs-JDK-strange

Cheers,
Raghavan alias Saravanan M.

Jeremy Manson said...

@Raghavan: To simplify it, the way HashMaps work, in effect, is that there are n linked lists, numbered from 0 to n-1. In Sun's JDK5, the hashCode() % n is used to decide what linked list the element was added. Thus, they will be added to the same linked lists in the same order every time. In JDK6, they apply a function to the hashCode() to make it more evenly distributed, but the resulting list is still uniquely determined based on the hashCode, so elements will still be added to the same linked lists in the same order every time.

Anurag Saxena said...

In Sun's JDK5, the hashCode() % n is used to decide what linked list the element was added.

Jeremy its not hashCode() % n. Its rather hashCode() & n. The two operators may give different results. n is the number of entry buckets in hashmap.

mk said...

This now-ancient topiccame up in a discussion the other day, so a long-belated correction to Jeremy's comment that "the value printed out might coincidentally be the same in any two versions of the JDK, but they could change it tomorrow without violating any rules."

In the specific case of a HashSet of Strings, it *is* guaranteed to return the same hashCode on any JDK because both the Set interface and the String class explicitly document how their hashCodes must be calculated. Every "correct" JDK must return exactly the same well-defined value. (Theoretically, either contract *could* be changed in a future version of Java, but practically speaking, such a change would be so massively disruptive that it's hard to imagine why they would ever do such a thing.)

However, Jeremy's warning against relying on the values of hashCode implementations that do *not* advertise how they are calculated is certainly sound advice.

Jeremy Manson said...

Well defined hashCodes don't solve this problem. Java's HashMap/HashSet implementations don't necessarily treat hashCode in the same way from implementation to implementation. Hash-based collections in the JDK currently rehash your hash code so that it won't be as predictable:

http://hg.openjdk.java.net/jdk9/jdk9/jdk/file/1d41042b9e4f/src/java.base/share/classes/java/util/HashMap.java#l336

At Google, we are looking at permanently rejiggering Hash-based collections so that iteration happens differently at each program invocation. That will make it much harder to make this mistake. This is probably worth a follow-up post at some point.