Java中String.equals()的运行时复杂性

Question

我想知道Java如何实现String.equals()方法以及这种操作的运行时复杂性.是检查每个单独的字符(导致O(N),其中N是长度)还是有某种有效的方法来比较两个会给出O(1)？

编辑:当我看到另一个问题和答案时,我想知道Java是否会自动进行某种实习,例如在String初始化时或在第一次调用compareTo或等于允许几乎所有调用时兑现一些值是O(1).如果我正确理解答案是必须积极实施String并且Java在幕后不做任何事情.

Answer 1

理论上它取决于实现,但我不认为差异是戏剧性的,因为OpenJDK 7u40-b43这是实现,

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

因此,它最有可能是O(n),但如果有以下情况,则有优化使其成为O(1):

• 字符串是同一个对象; 要么
• 你检查的东西不是字符串; 要么
• 字符串长度不同.