.includes()算法和速度？

Question

我很想知道.includes()方法使用的算法是什么？它是否使用像Rabin-Karp那样的模块化哈希算法？

在不了解它的方法和速度的情况下，我有些犹豫使用.includes()。我找到的文档在讨论时没有具体说明（例如：https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/String/includes）。

- Babra Cunningham

---

我一直以为它底层使用的是indexOf，但我不确定... - Luan Nico

很可能只是语法糖，底层使用与 indexOf 相同的方法，但实际实现方式取决于供应商。 - adeneo

实现未定义。你正在要求对每个JavaScript引擎的源代码进行分析。 有些会表现得比你期望的更好，有些则会表现得更差。 - Norguard

请查看您上面提到的链接中的 polyfill -- 它展示了一个示例实现（有些天真）：https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array/includes - Clark

Answer 1

鉴于不同的引擎可能以不同的方式实现.includes，因此很难对实现进行全面的陈述。但是，通过做一些基准测试（因为测试可能是确定的唯一方法），应该可以了解它的速度。

在使用Node 7.0测试三个不同函数时：
1. includes()，传递一个顺序数组
2. 基本for循环，传递一个顺序数组
3. has()，传递一个从顺序数组创建的预先创建的集合

我得到的结果表明，数组本身的长度似乎并不重要（正如所希望的那样），但所需数字距离起点的距离很重要。对于在索引小于20左右的数字，for循环似乎略快（大约快15％？）。对于较大的索引值，includes()超过for循环（从索引500开始看，速度似乎快了2-3倍）。但是，对于在后面索引值（从索引800开始）查找数字，.has()显然更快（速度快25-30倍），其大小对速度影响似乎不大（但创建集合需要时间）。

尽管这些是有限的测试，但许多因素可能会影响它们。有趣的结果之一是，如果从传入的数组创建了一个集合（而不是任何其他数组），则似乎即使未将该集合传递到函数中，它似乎也会增加includes()的速度，并略微减慢for循环函数的速度。我想这是某种缓存，可以以某种方式使.includes()受益？

- Immaterial

Answer 2

Rabin-Karp 算法是一种字符串搜索算法，但您已经链接了数组 includes() 算法，与字符串搜索不同，它不依赖于序列。 ECMA specification 描述了它的行为方式，强制实现：按升序对每个元素应用 SameValueZero。鉴于这种描述，任何正常算法的时间复杂度都将是 O(n)，空间复杂度为 O(1)。

另一方面，String.indexOf 没有如此挑剔的规范，V8 使用 Boyer-Moore-Horspool 字符串搜索 实现。

- tmcw