Runtime complexity of String.equals() in Java
java, string
Solution
In theory it depends on the implementation, however I don't think the differences are dramatic, for `OpenJDK 7u40-b43`, this is the implementation,
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) {
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;
}
As you can see, it's O(n), but there are optimizations to make it Ω(1) in any of the these cases:
- the strings are the same object; or
- the thing you checking is not a string; or
- the string lengths are different.
Problem
I'm wondering how Java implements the String.equals() method and what the runtime complexity of such an operation is. Is each individual character checked (leading to O(N) where N is the length) or is there some kind of efficient way of comparing the two that would give O(1)? EDIT: As I see the other question and the answers, I'm wondering if Java has some kind of interning automatically, for example cashing some value upon initialization of the String or on the first call to compareTo or equals to allow almost all calls to be O(1). If I'm understanding correctly the answer is that one must actively intern the String and Java does nothing behind the scenes.