javascript - JavaScript 中 includes 方法的时间复杂度

Question

我有一个数组，其中包含某些字符串的一些哈希值， 我不希望我的数组中有重复值，所以我使用 if 逻辑，如下所示:

if(!arrayOfHash.includes(hash_value)){
  arrayOfHash.push(hash_value); 
}

我想知道 JavaScript 中 includes 方法的复杂性。 它是线性搜索函数还是修改后的搜索函数？

Answer 1

规范将此功能描述为线性搜索。 Array.prototype.includes

1. Let O be ? ToObject(this value).

2. Let len be ? ToLength(? Get(O, "length")).

3. If len is 0, return false.
4. Let n be ? ToInteger(fromIndex). (If fromIndex is undefined, this step produces the value 0.)
5. If n ≥ 0, then Let k be n.
6. Else n < 0, Let k be len + n. If k < 0, let k be 0.
7. Repeat, while k < len ... Increase k by 1.

在一般情况下这是一个相当合理的选择(列表未排序，列表不统一，您不维护额外的数据结构以及列表本身)。