Set.has() 方法是 O(1) 和 Array.indexOf O(n) 吗？

Question

我在一个答案中看到 Set.has() 方法是 O(1) 而 Array.indexOf() 是 O(n)。

var a = [1, 2, 3, 4, 5];
a.indexOf(5);          


s = new Set(a);
s.has(5);              //Is this O(1)?

Set.has() 真的是 O(1) 吗？

Answer 1

如果读到has()的specification，有一种算法描述它：

Set.prototype.has(value)的算法：

采取以下步骤：

Let S be the this value.

If Type(S) is not Object, throw a TypeError exception.

If S does not have a [[SetData]] internal slot, throw a TypeError exception.

Let entries be the List that is the value of S’s [[SetData]] internal slot.

Repeat for each e that is an element of entries,

If e is not empty and SameValueZero(e, value) is true, return true.

Return false.

显然，根据该算法和 REPEAT 这个词的存在，人们可能会对它成为 O(1) 产生一些混淆（我们可能认为它可能是 O(n)） .但是，在 specification 我们可以看到：

Set objects must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection.

感谢 @CertainPerformance 指出这一点。

所以，我们可以创建一个测试来比较 Array.indexOf() 和 Set.has() 在最坏的情况下，即寻找一个根本不在数组中的项目（感谢 @aquinas 指出此测试):

// Initialize array.
let a = [];

for (let i = 1; i < 500; i++)
{
    a.push(i);
}

// Initialize set.
let s = new Set(a);

// Initialize object.
let o = {};
a.forEach(x => o[x] = true);

// Test Array.indexOf().
console.time("Test_Array.indexOf()");
for (let i = 0; i <= 10000000; i++)
{
    a.indexOf(1000);
}
console.timeEnd("Test_Array.indexOf()");

// Test Set.has().
console.time("Test_Set.has()");
for (let i = 0; i <= 10000000; i++)
{
    s.has(1000);
}
console.timeEnd("Test_Set.has()");

// Test Object.hasOwnProperty().
console.time("Test_Object.hasOwnProperty()");
for (let i = 0; i <= 10000000; i++)
{
    o.hasOwnProperty(1000);
}
console.timeEnd("Test_Object.hasOwnProperty()");

.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}

现在我们可以看到 Set.has() 比 Array.indexOf() 表现更好。还有一个额外的比较Object.hasOwnProperty()作为参考。

结论：

虽然无法保证 O(1) 复杂性，但规范要求方法在 次线性时间 中运行。而 Set.has()，一般来说，会比 Array.indexOf().

表现得更好

另一个测试：

在下一个示例中，我们将生成一组随机样本数据，稍后使用它来比较不同的方法。

// Generate a sample array of random items.

const getRandom = (min, max) =>
{
    return Math.floor(Math.random() * (max - min) + min);
}

let sample = Array.from({length: 10000000}, () => getRandom(0, 1000));

// Initialize array, set and object.

let a = [];

for (let i = 1; i <= 500; i++)
{
    a.push(i);
}

let s = new Set(a);
let o = {};
a.forEach(x => o[x] = true);

// Test Array.indexOf().

console.time("Test_Array.indexOf()");
for (let i = 0; i < sample.length; i++)
{
    a.indexOf(sample[i]);
}
console.timeEnd("Test_Array.indexOf()");

// Test Set.has().
console.time("Test_Set.has()");
for (let i = 0; i < sample.length; i++)
{
    s.has(sample[i]);
}
console.timeEnd("Test_Set.has()");

// Test Object.hasOwnProperty().
console.time("Test_Object.hasOwnProperty()");
for (let i = 0; i < sample.length; i++)
{
    o.hasOwnProperty(sample[i]);
}
console.timeEnd("Test_Object.hasOwnProperty()");

.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}

最后，我想道歉，因为我的第一个版本的回答可能会造成混淆。感谢大家让我更好地理解我的错误。

Answer 2

我认为包含 5 个元素的数组不是检查时间复杂度的好例子。

因此，基于@Shidersz 的代码片段，我制作了一个包含 多个元素并调用一次的新代码片段。

Is Set.has() really O(1) ?

是。根据下面的测试结果，Set.has() 的时间复杂度为 O(1)。

const MAX = 10000000
let a = []
a.length = MAX

for (let i = 0; i < MAX; i++) {
  a[i] = i
}

let s = new Set(a)

let o = a.reduce((acc, e) => {
  acc[e] = e
  return acc
}, {})

console.time("Test_Array.IndexOf(0)\t")
a.indexOf(0);
console.timeEnd("Test_Array.IndexOf(0)\t")
console.time("Test_Array.IndexOf(n/2)\t")
a.indexOf(MAX / 2);
console.timeEnd("Test_Array.IndexOf(n/2)\t")
console.time("Test_Array.IndexOf(n)\t")
a.indexOf(MAX);
console.timeEnd("Test_Array.IndexOf(n)\t")

console.time("Test_Set.Has(0)\t\t")
s.has(0)
console.timeEnd("Test_Set.Has(0)\t\t")
console.time("Test_Set.Has(n/2)\t")
s.has(MAX / 2)
console.timeEnd("Test_Set.Has(n/2)\t")
console.time("Test_Set.Has(n)\t\t")
s.has(MAX)
console.timeEnd("Test_Set.Has(n)\t\t")

console.time("Test_Object[0]\t\t")
o[0]
console.timeEnd("Test_Object[0]\t\t")
console.time("Test_Object[n/2]\t")
o[MAX / 2]
console.timeEnd("Test_Object[n/2]\t")
console.time("Test_Object[n]\t\t")
o[MAX]
console.timeEnd("Test_Object[n]\t\t")

.as-console {
  background-color: black !important;
  color: lime;
}

.as-console-wrapper {
  max-height: 100% !important;
  top: 0;
}

Set.has() 方法是 O(1) 和 Array.indexOf O(n) 吗？

Is the Set.has() method O(1) and Array.indexOf O(n)?

javascript

arrays

lookup

big-o

set

结论：

另一个测试：