Skip to content
Advertisement

Why doesn’t String’s hashCode() cache 0?

I noticed in the Java 6 source code for String that hashCode only caches values other than 0. The difference in performance is exhibited by the following snippet:

public class Main{
   static void test(String s) {
      long start = System.currentTimeMillis();
      for (int i = 0; i < 10000000; i++) {
         s.hashCode();
      }
      System.out.format("Took %d ms.%n", System.currentTimeMillis() - start);
   }
   public static void main(String[] args) {
      String z = "Allocator redistricts; strict allocator redistricts strictly.";
      test(z);
      test(z.toUpperCase());
   }
}

Running this in ideone.com gives the following output:

Took 1470 ms.
Took 58 ms.

So my questions are:

  • Why doesn’t String’s hashCode() cache 0?
  • What is the probability that a Java string hashes to 0?
  • What’s the best way to avoid the performance penalty of recomputing the hash value every time for strings that hash to 0?
  • Is this the best-practice way of caching values? (i.e. cache all except one?)

For your amusement, each line here is a string that hash to 0:

pollinating sandboxes
amusement & hemophilias
schoolworks = perversive
electrolysissweeteners.net
constitutionalunstableness.net
grinnerslaphappier.org
BLEACHINGFEMININELY.NET
WWW.BUMRACEGOERS.ORG
WWW.RACCOONPRUDENTIALS.NET
Microcomputers: the unredeemed lollipop...
Incentively, my dear, I don't tessellate a derangement.
A person who never yodelled an apology, never preened vocalizing transsexuals.

Advertisement

Answer

You’re worrying about nothing. Here’s a way to think about this issue.

Suppose you have an application that does nothing but sit around hashing Strings all year long. Let’s say it takes a thousand strings, all in memory, calls hashCode() on them repeatedly in round-robin fashion, a million times through, then gets another thousand new strings and does it again.

And suppose that the likelihood of a string’s hash code being zero were, in fact, much greater than 1/2^32. I’m sure it is somewhat greater than 1/2^32, but let’s say it’s a lot worse than that, like 1/2^16 (the square root! now that’s a lot worse!).

In this situation, you have more to benefit from Oracle’s engineers improving how these strings’ hash codes are cached than anyone else alive. So you write to them and ask them to fix it. And they work their magic so that whenever s.hashCode() is zero, it returns instantaneously (even the first time! a 100% improvement!). And let’s say that they do this without degrading the performance at all for any other case.

Hooray! Now your app is… let’s see… 0.0015% faster!

What used to take an entire day now takes only 23 hours, 57 minutes and 48 seconds!

And remember, we set up the scenario to give every possible benefit of the doubt, often to a ludicrous degree.

Does this seem worth it to you?

EDIT: since posting this a couple hours ago, I’ve let one of my processors run wild looking for two-word phrases with zero hash codes. So far it’s come up with: bequirtle zorillo, chronogrammic schtoff, contusive cloisterlike, creashaks organzine, drumwood boulderhead, electroanalytic exercisable, and favosely nonconstruable. This is out of about 2^35 possibilities, so with perfect distribution we’d expect to see only 8. Clearly by the time it’s done we’ll have a few times that many, but not outlandishly more. What’s more significant is that I’ve now come up with a few interesting band names/album names! No fair stealing!

Advertisement