的时间复杂性是什么。java中的2个字符串等于？

Question

我想知道Java中的. equals运算符对于两个字符串的时间复杂度（大O）是多少。

基本上，如果我做了stringOne.equals（stringTwo），它的性能如何？

谢谢

Answer 1

为了补充优秀答案，我们可以查看代码：

public boolean equals(Object anObject) {
    if (this == anObject) { // O(1)
        return true;
    }
    if (anObject instanceof String) //O(1)  {
        String anotherString = (String)anObject;
        int n = value.length;
        if (n == anotherString.value.length) { // O(1)
            char v1[] = value;
            char v2[] = anotherString.value;
            int i = 0;
            while (n-- != 0) {  // O(n)
                if (v1[i] != v2[i]) //O(1)
                    return false;
                i++;
            }
            return true;
        }
    }
    return false;
}

最佳情况：O（1）

最坏情况：O（n）

Answer 2

最坏的情况是O（n），除非两个字符串是同一个对象，在这种情况下是O（1）。

（虽然在这种情况下，n是指两个字符串中从第一个字符开始的匹配字符数，而不是字符串的总长度）。

Answer 3

这里的其他答案过于简单化了。

通常，证明两个不同的字符串相等是O（n），因为您可能需要比较每个字符。

然而，这只是一种最坏的情况：有许多快捷方式，这意味着在一般/典型情况下，equals（）方法可以执行得更好：

• 如果字符串相同，则为O（1）：它们是相同的对象，因此根据定义相等，因此结果为真
• 如果您能够检查预先计算的哈希码，这可以证明两个字符串不相等（显然，它无法帮助证明两个字符串是相等的，因为许多字符串散列到同一个哈希码）。
• 如果字符串长度不同，则为O（1）（它们不可能相等，因此结果为false）
• 您只需要检测一个不同的字符来证明字符串不相等。因此，对于随机分布的字符串，比较两个字符串实际上是平均的O（1）时间。如果您的字符串不是完全随机的，那么结果可能介于O（1）和O（n）之间，具体取决于数据分布。

如您所见，确切的性能取决于数据的分布。

除此之外：这取决于实现，因此确切的性能特征将取决于使用的Java版本。然而，据我所知，所有当前的主要Java实现都进行了上面列出的优化，因此您可以期望equals（）在字符串上的性能非常快。

最后一个技巧：如果使用字符串内部处理，那么所有相等的字符串都将映射到同一个对象实例。然后，您可以使用极快的检查对象标识来代替保证为0（1）的检查对象标识。这种方法有缺点（可能需要插入大量字符串，导致内存问题，并且需要严格记住插入计划用于此方案的任何字符串），但在某些情况下它非常有用。