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

Question

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

基本上,如果我做了stringOne.equals(stringTwo),它的表现如何？

谢谢.

Answer 1

最坏的情况是O(n),除非两个字符串是相同的对象,在这种情况下它是O(1).

(尽管在这种情况下,n指的是从第一个字符开始的两个字符串中匹配字符的数量,而不是字符串的总长度).

Answer 2

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

通常,证明两个不同的字符串相等是O(n)因为您可能需要比较每个字符.

然而,这只是最糟糕的情况:有许多快捷方式意味着该equals()方法在平均/典型情况下可以比这更好:

• 这是O(1)如果字符串是相同的:他们是同一个对象的定义,以便相等,以结果为真
• 这是O(1),如果你可以检查预先计算哈希码,这可以证明两个字符串不相等(很明显,它不能帮助证明两个字符串是平等的,因为许多字符串散列相同的散列码).
• 这是O(1),如果字符串是不同的长度(他们不可能是相等的,所以结果是假)
• 您只需要检测一个不同的字符即可证明字符串不相等.因此,对于随机分布的字符串,实际上是O(1)比较两个字符串的平均时间.如果您的字符串不是完全随机的,则结果可能介于两者之间O(1),O(n)具体取决于数据分布.

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

除此之外:这是依赖于实现的,因此精确的性能特征将取决于所使用的Java版本.但是,据我所知,所有当前的主要Java实现都会执行上面列出的优化,因此您可以期待equals()Strings的性能非常快.

最后一招:如果使用String interning,则所有相等的Strings将映射到同一个对象实例.然后你可以使用极快的==检查对象标识代替equals(),保证是O(1).这种方法有缺点(您可能需要实施很多字符串,导致内存问题,并且您需要严格记住实际计划使用此方案的任何字符串)但在某些情况下它非常有用.