java - 2个字符串的java中.equals的时间复杂度是多少？

Question

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

基本上，如果我执行 stringOne.equals(stringTwo)，它的性能如何？

谢谢。

Answer 1

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

一般来说，证明两个不同的字符串相等是 O(n)，因为您可能必须比较每个字符。

然而，这只是最坏的情况:有许多捷径意味着 equals() 方法在平均/典型情况下可以比这表现得更好:

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

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

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

最后一个技巧:如果您使用String interning，那么所有相等的字符串都将映射到同一个对象实例。然后，您可以使用极快的 == 检查对象身份来代替 equals()，保证 O(1) .这种方法有缺点(您可能需要实习很多字符串，导致内存问题，并且您需要严格记住实习您计划用于此方案的任何字符串)但它在某些情况下非常有用。