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

Question

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.

Answer 1

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!

Answer 2

It uses 0 to indicate "I haven't worked out the hashcode yet". The alternative would be to use a separate Boolean flag, which would take more memory. (Or to not cache the hashcode at all, of course.)

I don't expect many strings hash to 0; arguably it would make sense for the hashing routine to deliberately avoid 0 (e.g. translate a hash of 0 to 1, and cache that). That would increase collisions but avoid rehashing. It's too late to do that now though, as the String hashCode algorithm is explicitly documented.

As for whether this is a good idea in general: it's an certainly efficient caching mechanism, and might (see edit) be even better with a change to avoid rehashing values which end up with a hash of 0. Personally I would be interested to see the data which led Sun to believe this was worth doing in the first place - it's taking up an extra 4 bytes for every string ever created, however often or rarely it's hashed, and the only benefit is for strings which are hashed more than once.

EDIT: As KevinB points out in a comment elsewhere, the "avoid 0" suggestion above may well have a net cost because it helps a very rare case, but requires an extra comparison for every hash calculation.

Answer 3

I think there's something important that the other answers so far are missing: the zero value exists so that the hashCode-caching mechanism works robustly in a multi-threaded environment.

If you had two variables, like cachedHashCode itself and an isHashCodeCalculated boolean to indicate whether cachedHashCode had been calculated, you'd need thread synchronization for things to work in a multithreaded environment. And synchronization would be bad for performance, especially since Strings are very commonly reused in multiple threads.

My understanding of the Java memory model is a little sketchy, but here's roughly what's going on:

1. When multiple threads access a variable (like the cached hashCode), there's no guarantee that each thread will see the latest value. If a variable starts on zero, then A updates it (sets it to a non-zero value), then thread B reads it shortly afterwards, thread B could still see the zero value.

2. There's another problem with accessing shared values from multiple threads (without synchronization) - you can end up trying to use an object that's only been partly initialized (constructing an object is not an atomic process). Multi-threaded reads and writes of 64-bit primitives like longs and doubles are not necessarily atomic either, so if two threads try to read and change the value of a long or a double, one thread can end up seeing something weird and partially set. Or something like that anyway. There are similar problems if you try to use two variables together, like cachedHashCode and isHashCodeCalculated - a thread can easily come along and see the latest version of one of those variables, but an older version of another.

3. The usual way to get around these multi-threading issues is to use synchronization. For example, you could put all access to the cached hashCode inside a synchronized block, or you could use the volatile keyword (although be careful with that because the semantics are a little confusing).

4. However, synchronization slows things down. Bad idea for something like a string hashCode. Strings are very often used as keys in HashMaps, so you need the hashCode method to perform well, including in multi-threaded environments.

5. Java primitives that are 32-bits or less, like int, are special. Unlike, say, a long (64-bit value), you can be sure that you will never read a partially initialized value of an int (32 bits). When you read an int without synchronization, you can't be sure that you'll get the latest set value, but you can be sure that the value you do get is a value that has explicitly been set at some point by your thread or another thread.

The hashCode caching mechanism in java.lang.String is set up to rely on point 5 above. You might understand it better by looking at the source of java.lang.String.hashCode(). Basically, with multiple threads calling hashCode at once, hashCode might end up being calculated multiple times (either if the calculated value is zero or if multiple threads call hashCode at once and both see a zero cached value), but you can be sure that hashCode() will always return the same value. So it's robust, and it's performant too (because there's no synchronization to act as a bottleneck in multi-threaded environments).

Like I said, my understanding of the Java memory model is a little sketchy, but I'm pretty sure I've got the gist of the above right. Ultimately it's a very clever idiom for caching the hashCode without the overhead of synchronization.

Answer 4

0 isn't cached as the implementation interprets a cached value of 0 as "cached value not yet initialised". The alternative would have been to use a java.lang.Integer, whereby null implied that the value was not yet cached. However, this would have meant an additional storage overhead.

Regarding the probability of a String's hash code being computed as 0 I would say the probability is quite low and can happen in the following cases:

• The String is empty (although recomputing this hash code each time is effectively O(1)).
• An overflow occurs whereby the final computed hash code is 0 (e.g. Integer.MAX_VALUE + h(c1) + h(c2) + ... h(cn) == 0).
• The String contains only Unicode character 0. Very unlikely as this is a control character with no meaning apart from in the "paper tape world" (!):

From Wikipedia:

Code 0 (ASCII code name NUL) is a special case. In paper tape, it is the case when there are no holes. It is convenient to treat this as a fill character without meaning otherwise.

Answer 5

This turns out to be a good question, related to a security vulnerability.

"When hashing a string, Java also caches the hash value in the hash attribute, but only if the result is different from zero. Thus, the target value zero is particularly interesting for an attacker as it prevents caching and forces re-hashing."

Answer 6

Ten years after and things have changed. I honestly can't believe this (but the geek in me is ultra-happy).

As you have noted there are chances where some String::hashCode for some Strings is zero and this was not cached (will get to that). A lot of people argued (including in this Q&A) why there was no addition of a field in java.lang.String, something like : hashAlreadyComputed and simply use that. The problem is obvious : extra-space for every single String instance. There is btw a reason java-9 introduced compact Strings, for the simple fact that many benchmarks have shown that this is a rather (over)used class, in the majority of the applications. Adding more space? The decision was : no. Especially since the smallest possible addition would have been 1 byte, not 1 bit (for 32 bit JMVs, the extra space would have been 8 bytes : 1 for the flag, 7 for alignment).

So, Compact Strings came along in java-9, and if you look carefully (or care) they did add a field in java.lang.String : coder. Didn't I just argue against that? It's not that easy. It seems that the importance of compact strings out-weighted the "extra space" argument. It is also important to say that extra space matters for 32 bits VM only (because there was no gap in alignment). In contrast, in jdk-8 the layout of java.lang.String is:

java.lang.String object internals:
 OFFSET  SIZE     TYPE DESCRIPTION                           VALUE
  0    12          (object header)                           N/A
 12     4   char[] String.value                              N/A
 16     4      int String.hash                               N/A
 20     4          (loss due to the next object alignment)
 Instance size: 24 bytes
 Space losses: 0 bytes internal + 4 bytes external = 4 bytes total

Notice an important thing right there:

Space losses : ... 4 bytes total.

Because every java Object is aligned (to how much depends on the JVM and some start-up flags like UseCompressedOops for example), in String there is a gap of 4 bytes, un-used. So when adding coder, it simply took 1 byte without adding additional space. As such, after Compact Strings were added, the layout has changed:

java.lang.String object internals:
 OFFSET  SIZE     TYPE DESCRIPTION                           VALUE
  0    12          (object header)                           N/A
 12     4   byte[] String.value                              N/A
 16     4      int String.hash                               N/A
 20     1     byte String.coder                              N/A
 21     3          (loss due to the next object alignment)
 Instance size: 24 bytes
 Space losses: 0 bytes internal + 3 bytes external = 3 bytes total

coder eats 1 byte and the gap was shrank to 3 bytes. So the "damage" was already made in jdk-9. For 32 bits JVM there was an increase with 8 bytes : 1 coder + 7 gap and for 64 bit JVM - there was no increase, coder occupied some space from the gap.

And now, in jdk-13 they decided to leverage that gap, since it exists anyway. Let me just remind you that the probability to have a String with zero hashCode is 1 in 4 billion; still there are people that say : so what? let's fix this! Voilá: jdk-13 layout of java.lang.String:

java.lang.String object internals:
OFFSET  SIZE      TYPE DESCRIPTION                            VALUE
  0    12           (object header)                           N/A
 12     4    byte[] String.value                              N/A
 16     4       int String.hash                               N/A
 20     1      byte String.coder                              N/A
 21     1   boolean String.hashIsZero                         N/A
 22     2           (loss due to the next object alignment)
 Instance size: 24 bytes
 Space losses: 0 bytes internal + 2 bytes external = 2 bytes total

And here it is : boolean String.hashIsZero. And here it is in the code-base:

public int hashCode() {
    int h = hash;
    if (h == 0 && !hashIsZero) {
        h = isLatin1() ? StringLatin1.hashCode(value)
                       : StringUTF16.hashCode(value);
        if (h == 0) {
            hashIsZero = true;
        } else {
            hash = h;
        }
    }
    return h;
}

Wait! h == 0 and hashIsZero field? Shouldn't that be named something like : hashAlreadyComputed? Why isn't the implementation something along the lines of :

    @Override
    public int hashCode(){
        if(!hashCodeComputed){
            // or any other sane computation
            hash = 42;
            hashCodeComputed = true;
        }

        return hash;
    }

Even if I read the comment under the source code:

    // The hash or hashIsZero fields are subject to a benign data race,
    // making it crucial to ensure that any observable result of the
    // calculation in this method stays correct under any possible read of
    // these fields. Necessary restrictions to allow this to be correct
    // without explicit memory fences or similar concurrency primitives is
    // that we can ever only write to one of these two fields for a given
    // String instance, and that the computation is idempotent and derived
    // from immutable state

It only made sense after I read this. Rather tricky, but this does one write at a time, lots more details in the discussion above.

Answer 7

• Why doesn't String's hashCode() cache 0?

The value zero is reserved as meaning "the hash code is not cached".

• What is the probability that a Java string hashes to 0?

According to the Javadoc, the formula for a String's hashcode is:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

using int arithmetic, where s[i] is the ith character of the string and n is the length of the string. (The hash of the empty String is defined to be zero as a special case.)

My intuition is that the hashcode function as above gives a uniform spread of String hash values across the range of int values. A uniform spread that would mean that the probability of a randomly generated String hashing to zero was 1 in 2^32.

• What's the best way to avoid the performance penalty of recomputing the hash value every time for strings that hash to 0?

The best strategy is to ignore the issue. If you are repeatedly hashing the same String value, there is something rather strange about your algorithm.

• Is this the best-practice way of caching values? (i.e. cache all except one?)

This is a space versus time trade-off. AFAIK, the alternatives are:

• Add a cached flag to each String object, making every Java String take an extra word.

• Use the top bit of the hash member as the cached flag. That way you can cache all hash values, but you only have half as many possible String hash values.

• Don't cache hashcodes on Strings at all.

I think that the Java designers have made the right call for Strings, and I'm sure that they have done extensive profiling that confirms the soundness of their decision. However, it does not follow that this would always be the best way to deal with caching.

(Note that there are two "common" String values which hash to zero; the empty String, and the String consisting of just a NUL character. However, the cost of calculating the hashcodes for these values is small compared with the cost of calculating the hashcode for a typical String value.)

Answer 8

Well folks, it keeps 0 because if it is zero length, it will end up as zero anyways.

And it doesn't take long to figure out that the len is zero and so must the hashcode be.

So, for your code-reviewz! Here it is in all it's Java 8 glory:

 public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

As you can see, this will always return a quick zero if the string is empty:

  if (h == 0 && value.length > 0) ...

Answer 9

The "avoid 0" suggestion seems appropriate to recommend as best practice as it helps a genuine problem (seriously unexpected performance degradation in constructible cases that can be attacker supplied) for the meager cost of a branch operation prior to a write. There is some remaining 'unexpected performance degradation' that can be exercised if the only things going into a set hash to the special adjusted value. But this is at worst a 2x degradation rather than unbounded.

Of course, String's implementation can't be changed but there is no need to perpetuate the problem.