Why String.equals() doesn't use hashCode() equality check under the hood?

Question

Why not using hashCode() under the hood of equals() to pre-check for equality first?

Quick draft tests:

@Fork(value = 1)
@Warmup(time = 1)
@Measurement(time = 1)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@State(Scope.Benchmark)

public class Main {

  @Param({
    "o", // differ size
    "oooooooooooooooooo1", // same size, differ last symbol
    "oooooooooooooooooo2" // same content
  })
  String string1;

  @Param({
    "oooooooooooooooooo2"
  })
  String string2;

  @Benchmark
  public void stringEquals(Blackhole bh) {
    bh.consume(string1.equals(string2));
  }

  @Benchmark
  public void myEquals(Blackhole bh) {
    bh.consume(myEquals(string1, string2));
  }

  boolean myEquals(String str1, String str2){
    if (str1.hashCode()==str2.hashCode()) {
      return str1.equals(str2);
    }
    return false;
  }
}

Results:

Benchmark                    (string1)            (string2)  Mode  Cnt   Score   Error  Units
Main.myEquals                        o  oooooooooooooooooo2  avgt    5   5.552 ± 0.094  ns/op
Main.myEquals      oooooooooooooooooo1  oooooooooooooooooo2  avgt    5   5.626 ± 0.173  ns/op
Main.myEquals      oooooooooooooooooo2  oooooooooooooooooo2  avgt    5  14.347 ± 0.234  ns/op
Main.stringEquals                    o  oooooooooooooooooo2  avgt    5   6.441 ± 1.076  ns/op
Main.stringEquals  oooooooooooooooooo1  oooooooooooooooooo2  avgt    5  13.596 ± 0.348  ns/op
Main.stringEquals  oooooooooooooooooo2  oooooooooooooooooo2  avgt    5  13.663 ± 0.126  ns/op

As you can see we got great speedup for the case of "same size, differ last symbol".

I think under the hood of String.equals() check for hashCode() equality should replace check for length() equality as it takes the same time:

  @Benchmark
  public void emptyTest(Blackhole bh) {
    bh.consume(0);
  }

  @Benchmark
  public void stringLength(Blackhole bh) {
    bh.consume(string2.length());
  }

  @Benchmark
  public void stringHashCode(Blackhole bh) {
    bh.consume(string2.hashCode());
  }

Benchmark                      (string2)  Mode  Cnt  Score   Error  Units
Main.emptyTest       oooooooooooooooooo2  avgt    5  3.702 ± 0.086  ns/op
Main.stringHashCode  oooooooooooooooooo2  avgt    5  4.832 ± 0.421  ns/op
Main.stringLength    oooooooooooooooooo2  avgt    5  5.175 ± 0.156  ns/op

PS I have a feeling my measurements method might be wrong, so any comments are welcome. Also, the hash is saved inside String and that also might produce some misleading results...

UPD1: As @AdamSiemion mentioned we need to recreate string every time a benchmarked method is called to avoid cashing of hash code:

  String str1, str2;

  @Setup(value = Level.Invocation)
  public void setup(){
    str1 = string1;
    str2 = string2;
  }

  @Benchmark
  public void stringEquals(Blackhole bh) {
    bh.consume(str1.equals(str2));
  }

  @Benchmark
  public void myEquals(Blackhole bh) {
    bh.consume(myEquals(str1, str2));
  }

Benchmark                    (string1)            (string2)  Mode  Cnt   Score   Error  Units
Main.myEquals                        o  oooooooooooooooooo2  avgt    5  29.417 ± 1.430  ns/op
Main.myEquals      oooooooooooooooooo1  oooooooooooooooooo2  avgt    5  29.635 ± 2.053  ns/op
Main.myEquals      oooooooooooooooooo2  oooooooooooooooooo2  avgt    5  37.628 ± 0.974  ns/op
Main.stringEquals                    o  oooooooooooooooooo2  avgt    5  29.905 ± 2.530  ns/op
Main.stringEquals  oooooooooooooooooo1  oooooooooooooooooo2  avgt    5  38.090 ± 2.933  ns/op
Main.stringEquals  oooooooooooooooooo2  oooooooooooooooooo2  avgt    5  36.966 ± 1.642  ns/op

So, we still have almost 30% speedup for the case of "same size, differ last symbol".

UPD2 As @DanielPryden mentioned str1 = string1 will not create new String. So we need to explicitly do so:

  @Setup(value = Level.Invocation)
  public void setup(){
    str1 = new String(string1);
    str2 = new String(string2);
  }

Benchmark                    (string1)            (string2)  Mode  Cnt   Score   Error  Units
Main.myEquals                        o  oooooooooooooooooo2  avgt    5  61.662 ± 3.068  ns/op
Main.myEquals      oooooooooooooooooo1  oooooooooooooooooo2  avgt    5  85.761 ± 7.766  ns/op
Main.myEquals      oooooooooooooooooo2  oooooooooooooooooo2  avgt    5  92.156 ± 8.851  ns/op
Main.stringEquals                    o  oooooooooooooooooo2  avgt    5  30.789 ± 0.731  ns/op
Main.stringEquals  oooooooooooooooooo1  oooooooooooooooooo2  avgt    5  38.602 ± 1.212  ns/op
Main.stringEquals  oooooooooooooooooo2  oooooooooooooooooo2  avgt    5  38.921 ± 1.816  ns/op

So, now we have what was expected: using hashCode() will always be slower then equals(). And that has a total sense (as @Carcigenicate mentioned in comments below): hashCode() need to do full traversal through char[] to produce the hash. I thought it might be some intrinsic under the hood of hashCode() that make it faster, but it has not.

Therefore, it's still possible to get some speed up of equals() if make a check for precalculated hash existence and compare them:

public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof String) {
        String anotherString = (String)anObject;
        int n = value.length;
        if (n == anotherString.value.length
           // new code begins
            && (hash==0 || anotherString.hash==0 || hash==anotherString.hash)) {
           // new code ends
            char v1[] = value;
            char v2[] = anotherString.value;
            int i = 0;
            while (n-- != 0) {
                if (v1[i] != v2[i])
                    return false;
                i++;
            }
            return true;
        }
    }
    return false;
}

We'll get some small(?) slowdown in case of equal strings (for checking hash fields), but also will get a speedup in case of strings with the same length but different content and already precalculated hashes.

Unfortunately, I can't test it as I can't change the source code of String class.

Answer 1

Your performance tests calling hashCode() thousands of times (using jmh) do not make sense because String hash code is cached:

/** Cache the hash code for the string */
private int hash; // Default to 0

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;
}

So once String hash code is computed, calling hashCode() has almost no cost - contrary to the majority of the Java classes which recompute the hash code every time hashCode() is called.

Usually it is equals() which is faster than hashCode() as it is usually uses a short-circuit evaluation. For example, if you have a call with 10 fields, and the values in first fields of the two provided instances differ equals() will not inspect the remaining 9 fields, while hashCode() (usually) be computed from all the 10 fields.

Answer 2

I agree that comparing the hashCode (only if already calculated) looks like it might boost up performance, as String objects are immutable.

Considerations:

1. The boost is only for when the hashCode already exists (was already calculated). If the hashCode wasn't already calculated, calculating might take longer than comparing the chars of 2 strings. This because, when comparing, we can stop as soon as we see a difference. For example, when comparing "aaxxxxxxxxxx" to "aazzzzzzzzzzz", we can stop after the second char if the strings aren't equal. But calculating hashCode will need a traversal over all chars.

2. Perhaps the writers' decision was based on stats regarding how Strings are used. They might have seen that the additional comparison of the hashCode might slow the system.

   For example, if most strings are used withing hash maps/tables, than the hashCode is already compared and used. All the strings left to compare have the same hashCode, so there's no need to compare the hashCodes again.

3. The hash field might be calculated in several threads simultaneously for the same object, especially if equals() uses it. This needs to be taken into consideration.

4. Another consideration is the memory usage. Perhaps there's an optimization in the JVM to not use memory if an int field is zero? Once it's not zero, might it raise the memory consumption?

It would have been nice to have a way to tweak and measure this (String is final). Perhaps using some bytecode manipulation or using a different classloader...

Here's the code tweak for what was suggested (OpenJDK and Oracle look the same):

public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }

    if (anObject instanceof String) {
        String anotherString = (String)anObject;
        int n = value.length;
        if (n == anotherString.value.length) {

            // THE HASHCODE TWEAK
            if (hash != 0 &&
                anotherString.hash != 0 &&
                hash == anotherString.hash)
            {
                return true;
            }

            char v1[] = value;
            char v2[] = anotherString.value;
            int i = 0;
            while (n-- != 0) {
                if (v1[i] != v2[i])
                    return false;
                i++;
            }
            return true;
        }
    }
    return false;
}