java中2个字符串的.equals的时间复杂度是多少？
我想知道Java中.equals运算符的时间复杂度（大O）是两个字符串。
基本上，如果我做了stringOne.equals（stringTwo），它的表现如何？
谢谢。
最坏的情况是O（n），除非两个字符串是相同的对象，在这种情况下它是O（1）。
（尽管在这种情况下，n指的是从第一个字符开始的两个字符串中匹配字符的数量，而不是字符串的总长度）。
这里的其他答案过于简单化了。
通常，certificate两个不同的字符串相等是O(n)因为您可能必须比较每个字符。
然而，这只是最糟糕的情况：有许多快捷方式意味着equals()方法在平均/典型情况下可以比这更好：
- 如果字符串相同则为
O(1)：它们是相同的对象，因此定义相同，结果为真 - 它是
O(1)如果你能够检查预先计算的哈希码，这可以certificate两个字符串不相等 （显然，它无法certificate两个字符串是相等的，因为许多字符串哈希到相同的哈希码）。 - 如果字符串具有不同的长度（它们不可能相等，那么结果是错误的）是
O(1)） - 您只需要检测一个不同的字符来certificate字符串不相等。 因此，对于随机分布的字符串，它实际上是比较两个字符串的平均
O(1)时间。 如果您的字符串不是完全随机的，那么结果可能是O(1)和O(n)之间的任何位置，具体取决于数据分布。
如您所见，确切的性能取决于数据的分布 。
除此之外：这取决于实现，因此精确的性能特征将取决于所使用的Java版本。 但是，据我所知，所有当前的主要Java实现都执行上面列出的优化，因此您可以期望Strings上的equals()性能非常快。
最后一招：如果使用String interning，则所有相等的Strings将映射到同一个对象实例。 然后你可以使用极快==检查对象标识代替equals() ，保证为O(1) 。 这种方法有缺点（您可能需要实施很多字符串，导致内存问题，并且您需要严格记住实际计划使用此方案的任何字符串）但在某些情况下它非常有用。
这在O（n）中很容易实现，并且在不到这一点时是不可能的，所以它应该是它。