JavaScript 中包含方法的时间复杂度 [英] Time complexity of the includes method in JavaScript

问题描述

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

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

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

解决方案

Spec 将此功能描述为线性搜索.Array.prototype.includes

<块引用>

1. 让O成为?ToObject(这个值).

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

3. 如果 len 为 0，则返回 false.
4. 让 n 是?ToInteger(fromIndex).(如果未定义 fromIndex，则此步骤生成值 0.)
5. 如果 n ≥ 0，则令 k 为 n.
6. 否则 n <0，令k为len + n.如果 k＜0，令k为0.
7. 重复，而 k ... 将 k 增加 1.

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

I have an array that contains some hash values of certain strings, I don't want duplicate values in my array so I use if logic like this:

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

I want to know the complexity of the includes method in JavaScript. Is it a linear search function or is it a modified search function?

解决方案

Spec describes this function as linear search. 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.

Which is quite a reasonable choice in general case (list is not sorted, list is not uniform, you do not maintain additional datastructures along with the list itself).

这篇关于JavaScript 中包含方法的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！