13

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

基本上，如果我做了 stringOne.equals(stringTwo) 这表现如何？

谢谢。

4

3 回答 3

18

The other answers here are over-simplistic.

In general, proving that two different Strings are equal is O(n) because you may have to compare each character.

However this is only a worst-case: there are many shortcuts that mean that the equals() method can perform much better than this in the average / typical cases:

  • It's O(1) if the Strings are identical: they are the same object so equal by definition so the result is true
  • It's O(1) if you are able to check pre-computed hashcodes, which can prove that two Strings are not equal (obviously, it can't help prove that two Strings are equals because many Strings hash to the same hashcode).
  • It's O(1) if the Strings are of different lengths (they can't possibly be equal, so the result is false)
  • You only need to detect one different character to prove that Strings are not equal. So for randomly distributed Strings, it is actually average O(1) time to compare two Strings. If your Strings aren't completely random, then the result may be anywhere between O(1) and O(n) depending on the data distribution.

As you can see, the exact performance depends on the distribution of the data.

Apart from that: this is implementation dependent so exact performance characteristics will depend on the version of Java used. However, to my knowledge, all the current main Java implementations do the optimisations listed above so you can expect equals() performance on Strings to be pretty fast.

A final trick: If you use String interning then all Strings that are equal will be mapped to the same object instance. Then you can use the extremely fast == check for object identity in place of equals(), which is guaranteed to be O(1). This approach has downsides (you may need to intern a lot of Strings, causing memory issues, and you need to strictly remember to intern any Strings that you plan to use with this scheme) but it is extremely useful in some situations.

于 2014-02-26T03:21:34.947 回答
14

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

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

于 2013-01-27T21:07:41.500 回答
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)

于 2019-02-25T15:37:50.750 回答