为什么Javascript ===/== 字符串相等有时具有恒定时间复杂度，有时具有线性时间复杂度？

在我发现常见/最新的 Javascript 实现正在使用 String Interning 来提高性能之后（常见的 JavaScript 实现是否使用字符串驻留？）， 我想===对于字符串将得到常数 O(1) 时间。所以我对这个问题给出了错误的答案：

JavaScript 字符串相等性能比较

由于根据该问题的 OP，它是 O(N)，因此将字符串输入加倍会使等式所需的时间加倍。他没有提供任何 jsPerf 因此需要更多调查，

所以我使用字符串实习的场景是：

var str1 = "stringwithmillionchars"; //stored in address 51242

var str2 = "stringwithmillionchars"; //stored in address 12313

“stringwithmillionchars”将被存储一次，假设在内存地址 201012 中 str1 和 str2 都将“指向”这个地址 201012。然后可以通过某种哈希来确定该地址，以映射到内存中的特定位置。

所以在做的时候

"stringwithmillionchars" === "stringwithmillionchars"

看起来像

getContentOfAddress(51242)===getContentOfAddress(12313)

or 201012 === 201012

这将需要 O(1)/常数时间

JSPerfs/性能更新：

即使字符串长 16 倍，JSPerf 似乎也显示恒定时间？请看一看：

http://jsperf.com/eqauality-is-constant-time

上面的字符串可能太小： 这可能显示线性时间（感谢 sergioFC），字符串是用循环构建的。我尝试不使用函数 - 仍然是线性时间/我改变了一点http://jsfiddle.net/f8yf3c7d/3/ .

根据https://www.dropbox.com/s/8ty3hev1b109qjj/compare.html?dl=0（sergioFC 制作的 12MB 文件）当您有一个字符串并且已经在引号中分配了值时，无论 t1 和 t2 有多大（例如 5930496 个字符），它都会花费 0-1 毫秒/瞬时时间。

似乎当您使用 for 循环或函数构建字符串时，该字符串不会被保留。因此，只有当您直接分配带有引号的字符串时，才会发生实习，例如var str = "test";

基于字符串 a 和 b 的所有性能测试（参见原始帖子）操作a === b takes:

• 常数时间 O(1)如果琴弦被拘留。从例子看来，实习only发生在直接分配的字符串上，例如var str = "test";如果您使用 for 循环或函数通过串联来构建它，则不会。

• 线性时间 O(N)因为在所有其他情况下，首先比较两个字符串的长度。如果相等，那么我们就逐个字符进行比较。否则他们当然不平等。 N 是字符串的长度。