31

What's the quickest to compare two strings in Java?

Is there something faster than equals?

EDIT: I can not help much to clarify the problem.

I have two String which are sorted alphabetically and EXACTLY the same size

Example: abbcee and abcdee

Strings can be long up to 30 characters

12
  • 12
    Why would equals() be slow for you?
    – BoltClock
    Sep 27, 2010 at 16:01
  • 6
    Have you profiled your app, and was the conclusion that the hotspot in your code was caused by String.equals(...)? If you haven't profiled your app, why do you think String.equals(...) is (or could be) a problem?
    – Bart Kiers
    Sep 27, 2010 at 16:04
  • 4
    His question does not state that equals is slow. Just wondering if there is something faster than equals().
    – Sagar
    Sep 27, 2010 at 16:05
  • 2
    his question does state that equals is slow (or at least that it's not fast) when he says 'or something faster than equals'
    – KevinDTimm
    Sep 27, 2010 at 16:21
  • 1
    Agreed - as it stands, this is a bad question. If you want something faster than equals(), then either you have some very specific performance requirements backed by measurements (in which case these must be posted before any appropriate answers can be given), or you actually don't (have unusual performance requirements), in which case you should just use equals(). Implying "equals isn't fast enough" without any justification gives people nothing to work with. Sep 27, 2010 at 16:55

7 Answers 7

36

I don't expect that Sun Oracle hasn't already optimized the standard String#equals() to the max. So, I expect it to be already the quickest way. Peek a bit round in its source if you want to learn how they implemented it. Here's an extract:

public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof String) {
        String anotherString = (String)anObject;
        int n = count;
        if (n == anotherString.count) {
            char v1[] = value;
            char v2[] = anotherString.value;
            int i = offset;
            int j = anotherString.offset;
            while (n-- != 0) {
                if (v1[i++] != v2[j++])
                    return false;
            }
            return true;
        }
    }
    return false;
}
10
  • 1
    This looks pretty optimized to me.... it would be theoretically possible to optimize it further for the OP's specific constraints (e.g. using the knowledge that the strings are already of equal length, and higher likelihood of different characters in the middle of the string), but you obviously can't do that in practice because the class is final and the fields are private .... +1 for digging out the source!
    – mikera
    Sep 27, 2010 at 18:26
  • I don't understand why they didn't compare the hashcode before doing a whole string compare. That would be faster.
    – Stephan
    Mar 24, 2012 at 9:39
  • 10
    @Stephan: that would have been more inefficient. The hashCode() loops over all characters of the string to perform the calculation. If the hashCode() was after all not the same, then the equals() would basically need to loop over all characters for the second time.
    – BalusC
    Dec 21, 2012 at 16:14
  • 6
    @BalusC That's only a part of the truth. Once calculated, the hashCode() method stores the hash code into an int, so the next comparison will be really fast.
    – Stephan
    Jan 4, 2013 at 8:33
  • 2
    Please note that String::equals and many other String methods are intrinsics, replaced by the compiler with a pre-baked blob of assembley for the particular architecture. The Java code is only relevant before the intrinsic is in place, so hardly ever. Nov 9, 2016 at 15:18
28

Compare Strings of same length faster using the hashcode:

public static boolean equals(final String s1, final String s2) {
return s1 != null && s2 != null && s1.hashCode() == s2.hashCode()
    && s1.equals(s2);
}

You can test it, my results are for 4000000 compare operations including identical, equal and different strings:

String.equals(String):  177081939
equals(String, String):  44153608

Note: Calculating the hashCode of a new string object takes some computation time and afterwards the hashCode is stored in the object. So my suggested improvement will only be faster than the default compare if string objects are reused. In my application I am using String constants and store strings in collections. Multiple comparisons of strings using my method are actually faster for me, but it may not be in general.

If the method is used with new strings all the time like compare("a", "b"), it won't be an improvement.

So the fastest way of comparing strings depends on:

  • Whether your string objects are reused (like from a collection) or are always new (like from an input stream)
  • Whether your strings have different lengths
  • Whether your strings differ at the start or the end of the string
  • Your programming style, how much constants are used
  • Your use of String.intern()

Ignoring those facts, the majority of all programs will be fine with String.equals().

7
  • +1 I've been using this for a lot of "word crunching" and the perf is fantastic
    – xchiltonx
    Dec 16, 2013 at 22:08
  • 9
    I think it's worth mentioning that there might be some hashcode collisions, so there is a very, very slim chance that comparing hashes will return false positives. This explains the fact that you still have to use equals. For this reason, I think this will be slower if the majority of your strings are equal.
    – Nepoxx
    Oct 22, 2014 at 18:56
  • 1
    Why did you add "of some length"?
    – Flow
    Feb 27, 2015 at 17:17
  • 2
    How is this faster? You still use s1.equals(s2).
    – vedi0boy
    Dec 16, 2015 at 17:05
  • I believe there would be hardly any performance improvement....for more info check stackoverflow.com/questions/14262431/… Jan 11, 2016 at 14:50
5

I had tries different combinations for string comparison (code here):

1. s1.equals(s2)
2. s1.length() == s2.length() && s1.hashCode() == s2.hashCode() && s1.equals(s2)
3. s1.hashCode() == s2.hashCode() && s1.equals(s2);
4. s1.length() == s2.length() && s1.equals(s2);

I used strings of 40 chars length, in 10000000000L iterations and before any iteration I reinitialized the strings.

for equal stings I got:

equal: 2873 milis ???
equal: 21386 milis
equal: 7181 milis
equal: 2710 milis ???

for same size strings but last char different I got:

different: 3011 milis
different: 23415 milis
different: 6924 milis
different: 2791 milis

for different sizes, almost same strings but one char added at the end for s2:

different size: 3167 milis
different size: 5188 milis
different size: 6902 milis
different size: 2951 milis

seems to me it is best to use first a string.length() comparison before equals().

But this will not matter almost at all because this is the case where I have 10^10 string comparisons with 40 chars length and what is bizarre for me is the case where for equal strings I have a better speed when I compare the string length first.

1
  • 7
    I think there's something wrong with your data. When you're comparing Strings of the same length, how could algorithm 4 (comparing length, then using .equals()) be faster than algorithm 1 (comparing only using .equals()). For these cases algorithm 4 is doing an unnecessary String length comparison that will always return true.
    – Tyler
    Oct 12, 2015 at 23:40
4

If you can show that it's a significant bottleneck, which would surprise me, you could try

s1.hashCode() == s2.hashCode() && s1.equals(s2)

It might be a bit faster. It mightn't.

5
  • This was my first idea, too. Since string are immutual (is this really spelled right?) you're basically comparing constant ints here, which should be fast. Could be a problem only if the objects are equal most of the time, you could dynamically swap the implementation then. Too sad I don't have the jdk on this machine, would love to profile that now. Sep 28, 2010 at 8:35
  • 1
    Yes, it is faster. But you need to do a null check before.
    – Stephan
    Mar 24, 2012 at 9:38
  • 1
    I doubt that would be faster unless you cache hashcode in some way. I think equals is faster than computing a hash code.
    – jontro
    Apr 16, 2013 at 10:23
  • both strings should calculate their hashcodes before (which happens only if the string was used as key in hashmap) also 0 hash still valid value. Jul 22, 2018 at 0:01
  • @jontro Hashcodes are not computed on every call for String. As String is invariant, they can be precomputed, or cached, internally, and indeed they are.
    – user207421
    Aug 19, 2023 at 4:11
3

It depends what you need. I think equals() is really optimized but perhaps you need something else faster than equals(). Take a look at this post.

1

Simple answer

String.equals(Object)

I'm pretty sure (this answer has some references) and it's very likely that the JIT will have an intrinsic for String#equals, which means it would be able to replace the call with specially crafted machine code for the architecture your JVM is currently running on.

0

As always, you will need to benchmark for your application / environment. And unless you have already profiled and idetified this as a performance bottleneck, it's probably not going to matter ("premature optimization is the root of all evil").

Having said that:

a.equals(b) is really fast for Strings. It's probably one of the most tightly optimized pieces of code in the Java platform. I'd be very surprised if you can find any faster way of comparing two arbitrary strings.

There are special cases where you can cheat and use (a==b) safely, e.g. if you know that both Strings are interned (and therefore value identity implies object identity). In that case it may be slightly faster than a.equals(b) - but again this depends on compiler/JVM implementation. And it's very easy to shoot yourself in the foot if you don't know what you are doing.....

4
  • p.s. I have just micro-benchmarked this, and (a==b) does beat a.equals(b) by a factor of about 2-4 times (30ns vs. 70-110ns) in my environment (Eclipse on Sun Java 1.6). YMMV, and usual caveats about micro-benchmarking do of course apply :-)
    – mikera
    Sep 27, 2010 at 16:39
  • Looking at the implementation code posted by @BalusC, I can see absolutely no heavy optimizations, nothing at all to warrant your statement. Granted, optimizing this already trivial code isn’t easy. But low-level, what could have been done to optimize is to move from char-wise to int-wise comparison (obviously this requires low-level tricks not readily available in Java, and it might not be faster after all). Sep 27, 2010 at 17:00
  • Hmmm It looks extremely tightly optimized to me, to the extent that e.g. they are re-using the string length as a negative loop counter (which is a classic low-level optimization). I can't see personally see any additional optimization that could be made, short of abandoning pure Java and dropping to a specialized native implementation (and it's possible that the JIT does this anyway....)
    – mikera
    Sep 27, 2010 at 18:11
  • You can use equals() and intern strings safely. The equals() method does check for identity.
    – Stephan
    Mar 24, 2012 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.