javascript - 为什么 Javascript ===/== 字符串相等有时具有常数时间复杂度，有时具有线性时间复杂度？

Question

在我发现常见/最新的 Javascript 实现使用字符串实习来提高性能后(Do common JavaScript implementations use string interning?)，我认为字符串的 === 将获得常量 O(1) 时间。所以我对这个问题给出了错误的答案:

JavaScript string equality performance comparison

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

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

var str1 = "stringwithmillionchars";//存储在地址51242

var str2 = "stringwithmillionchars";//存储在地址12313

“stringwithmillionchars”将存储在内存地址 201012 中并且 str1 和 str2 都将“指向”这个地址 201012。然后可以使用某种散列来确定该地址以映射到内存中的特定位置。

所以在做的时候

"stringwithmillionchars"=== "stringwithmillionchars"

看起来像

getContentOfAddress(51242)===getContentOfAddress(12313)

或201012 === 201012

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

JSPerfs/性能更新:

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

http://jsperf.com/eqaulity-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";

Answer 1

基于字符串 a 和 b 的所有性能测试(参见原帖)，a === b 操作采用:

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

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