How String equals Method Works
The equals
method is declared in Object class and hence is inherited by all
classes in Java. The purpose of equals method is to provide logical
equality. The default implementation of equals method is:
public boolean equals(Object obj) {
return (this == obj);
}
Thus the default behavior of equals method is same as == operator. equals method in String class checks if the two strings have same characters or not. But this check is performed intelligently. The algorithm for checking the Strings for equality involves:
a) If the String objects are equals as per == operator, true is returned.
b) If the == returns false then each character of both the strings are compared and if a difference if found, immediately false is returned.
c) If after comparing all characters of both the strings, no difference is found in characters and length of strings, true is returned.
Please note that the equals method in String class in Java is case-sensitive. The complete code for equals method is reproduced here for reference:
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;
}Also the compareTo method in String class is consistent with equals method.
(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)
Comments
Tomasz Nurkiewicz replied on Fri, 2012/11/23 - 2:55am
Point c) is not clear, it suggests that characters are compared first and if all of them are equal and length of strings is the same, strings are considered equal. In reality the string length is compared first, which is important both from implementation simplicity and from performance perspective.
Also please explain what does it mean that equals is consistent with compareTo (it might not be obvious). Finally the source code is poorly formatted.
Mike P(Okidoky) replied on Fri, 2012/11/23 - 10:40am
First, thank goodness that Java doesn't have operator overloading. You'd never be able to trust what you'd be looking at unless you'd constantly be brushing up on what the implementation does.
Hashcode could be used to quickly eliminate unequal strings. I think the upsides outweigh the downsides using hashcode (which can trigger a first-time calculation).
Last, the code visually looks like a horrid blob of goo. I'd have written it like this:The compiler and JVM ought to be able to optimize this to be as efficient as manually trying to grasp at trying to "cache" member fields, etc.
public boolean equals(Object obj) { if (this == obj) return true; if (obj instanceof String) { String str = (String)obj; if (count != str.count) return false; if (hashCode() != str.hasCode()) return false; for (int i = offset, j = strl.offset - i, k = offset + count; i < k; i++) { if (value[i] != str.value[i + j]) return false; } return true; } return false; }And then my pet peeve is the awful K&R bracing style that Java developers use. Clearly, Alman style looks cleaner and you can browse up and down code and interpret it quicker and more efficiently. Saving vertical space should not be a motivation. I know this is a religious argument, but I can't for the life of me understand why people "like" K&R bracing style.
Stig Christensen replied on Sun, 2012/11/25 - 9:03am
in response to:
Mike P(Okidoky)
hasCode() would make it very expensive on large strings in many cases.
I guess if you wanted the fast lookup you would have a HashSet or the like anyway.
Mike P(Okidoky) replied on Sun, 2012/11/25 - 10:57am
in response to:
Stig Christensen
No it wouldn't. The values are cached and requires walking through all the characters only once. Sets and Maps also invoke hashCode. That's the whole point of hash codes in the first place, a quick rough signature.
Stig Christensen replied on Sun, 2012/11/25 - 11:54am
in response to:
Mike P(Okidoky)
You misunderstand me - and I know the hash code is cached.
In many cases you will not compare the same String many times, therefore hashCode() would be expensive. If you compare two very large Strings there is a good chance that equals() would return after the 1st char and that is fast! Hash would be slow.
If you do a lot of comparisons you would put them in a Hashset anyway, and String would then use the hashCode() as expected.
I think this is why String equals is written without hasCode(). It should not heart performance on a simple comparison.
Mike P(Okidoky) replied on Sun, 2012/11/25 - 12:32pm
in response to:
Stig Christensen
Actually, I just remembered something. A little while back, I was looking at improving both equals and compareTo. I had actually contemplated doing a hybrid comparison and hashCode generation.
But I although agree with that one should not trigger a hashCode on just an equals call, there are still ways to improve it. The hybrid generate while comparing maybe maybe not. But checking if a hashCode is available on both sides could work.
if (hash != 0 && anotherString.hash != 0 && hash != anotherString.hash) return false;
Could first compare first (few) characters to give a possible string inequality the change to conclude it's not equals before spending the time on hash comparison above.
Another option is to make some native code for it. System.arraycopy() has become native a while back. Perhaps System.arraycmp() might come in handy...
Wait... Arrays has public static boolean equals(char[] a, char[] a2)...
Doesn't accommodate an offset and isn't native...