Performance of array includes vs mapping to an Object and accessing it in JavaScript

Question

According to the fundamentals of CS the search functionality of an unsorted list has to occur in O(n) time where as direct access into an array will occur in O(1) time for HashMaps.

So is it more performant to map an array into a dictionary and then access the element directly or should I just use includes? This question is specifically for JavaScript because I believe this would come down to core implementation details of how includes() and {} is implemented.

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

or...

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

Answer 1

It's true that object lookup occurs in constant time - O(1) - so using object properties instead of an array is one option, but if you're just trying to check whether a value is included in a collection, it would be more appropriate to use a Set, which is a (generally unordered) collection of values, which can also be looked up in linear time. (Using a plain object instead would require you to have values in addition to your keys, which you don't care about - so, use a Set instead.)

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

This will be useful when you have to look up multiple values for the same Set. But, adding items to the Set (just like adding properties to an object) is O(N), so if you're just going to look up a single value, once, there's no benefit to this nor the object technique, and you may as well just use an array includes test.