javascript - 数组的性能包括与映射到对象并在 JavaScript 中访问它

Question

根据CS的基本原理search未排序列表的功能必须在 O(n) 时间内发生，而对于 HashMap，直接访问数组将在 O(1) 时间内发生。

那么将数组映射到字典然后直接访问元素是否更高效，或者我应该只使用包含？这个问题专门针对 JavaScript，因为我相信这将归结为 includes() 的核心实现细节。和 {}被实现。

let y = [1,2,3,4,5]
y.includes(3)

或者...

let y = {
          1: true,
          2: true
          3: true
          4: true
          5: true
        }
5 in y

Answer 1

确实，对象查找发生在恒定时间 - O(1) - 所以使用对象属性而不是数组是一种选择，但如果你只是想检查一个值是否包含在集合中，那会更合适使用 Set ，它是一个(通常是无序的)值的集合，也可以在线性时间内查找。 (如果使用普通对象，除了键之外，您还需要有值，而您并不关心 - 因此，请改用 Set。)

const set = new Set(['foo', 'bar']);
console.log(set.has('foo'));
console.log(set.has('baz'));

当您必须为同一个 Set 查找多个值时，这将很有用。 .但是，将项目添加到 Set (就像向对象添加属性一样)是O(N) ，所以如果你只是要查找一个值，一次，这和对象技术都没有好处，你也可以只使用数组 includes测试。