Runtime complexity of String.equals() in Java [duplicate]

Question

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.

Answer 1

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.

Answer 2

String.equals first compares the reference. If the reference is the same as this, then true is returns. Of if the input param to compare is not String type, false is returned. Then length is compared, if length of the two String are not the same, false is returned. Only in these there case, the complexity is O(1).

Otherwise, the method will compare each character of the two String, which means it has O(n) complexity.