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

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

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

然而，这只是一个最坏的情况：有许多快捷方式意味着该方法在平均/典型情况下可以比这好得多：equals()

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

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

除此之外：这与实现有关，因此确切的性能特征将取决于所使用的Java版本。但是，据我所知，当前所有主要的Java实现都进行了上面列出的优化，因此您可以期望Strings的性能非常快。equals()

最后一个技巧：如果您使用字符串实习，则所有相等的字符串都将映射到同一对象实例。然后，您可以使用极快的检查对象标识来代替 ，这保证是 。这种方法有缺点（您可能需要实习大量字符串，从而导致内存问题，并且您需要严格记住要将计划与此方案一起使用的任何字符串进行实习），但在某些情况下它非常有用。==equals()O(1)

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

（尽管在本例中，n 是指从第一个字符开始的两个字符串中的匹配字符数，而不是字符串的总长度）。