The question Is the Set.has() method O(1) and Array.indexOf O(n)? is listed as a duplicate of this one, which it isn't exactly (I've voted to re-open). I'll add these benchmarks here anyway, as the benchmarks on the replies to that question fail to show the full range of differences in performance between Set#has
and Array#indexOf
.
The following is all true for Chrome 93:
You find that for smaller datasets, Array#indexOf
actually outperforms Set#has
or Map#has
; however, for larger datasets, Set#has
and Map#has
are multiple orders of magnitude faster. Which is pretty consistent with what you'd expect for O(n) vs O(1) operations.
Interestingly, despite both being O(n), Array#includes
is way slower than Array#indexOf
for a small dataset, but performs very similarly for large datasets. Presumably, Array#indexOf
takes advantage of some optimization that Array#includes
doesn't.
Meanwhile, Object#hasOwnProperty
slightly outperforms Set#has
and Map#has
in all cases (at least in Chrome 93).
Benchmarking code
const [small, medium, large] = [1e3, 1e5, 1e7]
const configs = [
{ size: small, iterations: large },
{ size: medium, iterations: medium },
{ size: large, iterations: small },
]
for (const { size, iterations } of configs) {
const arr = Array.from({ length: size }, (_, i) => String(i))
const obj = Object.fromEntries(arr.map(k => [k, true]))
const set = new Set(arr)
const map = new Map(Object.entries(obj))
const valsToTest = Array.from(
{ length: iterations },
(_, i) => String(Math.floor(Math.random() * size)),
)
const title = `dataset size: ${size.toLocaleString()}; iterations: ${iterations.toLocaleString()}`
console.log(`\n-> ${title}`)
for (const [target, method] of [
[arr, 'indexOf'],
[arr, 'includes'],
[set, 'has'],
[map, 'has'],
[obj, 'hasOwnProperty'],
]) {
const subtitle = `${target.constructor.name}#${method}`
console.time(subtitle)
for (const val of valsToTest) {
target[method](val)
}
console.timeEnd(subtitle)
}
}
My results (Chrome 93)
-> dataset size: 1,000; iterations: 10,000,000
Array#indexOf: 185.100ms
Array#includes: 11302.700ms
Set#has: 367.400ms
Map#has: 375.000ms
Object#hasOwnProperty: 252.800ms
-> dataset size: 100,000; iterations: 100,000
Array#indexOf: 10794.100ms
Array#includes: 10476.800ms
Set#has: 6.600ms
Map#has: 6.800ms
Object#hasOwnProperty: 1.900ms
-> dataset size: 10,000,000; iterations: 1,000
Array#indexOf: 12798.900ms
Array#includes: 12435.400ms
Set#has: 0.800ms
Map#has: 0.800ms
Object#hasOwnProperty: 0.300ms