JavaScript fast lookup data structure?

Question

I have an array of 109582 strings ordered alphabetically. My web application will be making a lot of rapid checks for whether a given string is contained in the array. Obviously I could make a wrapper class that is a hash table or binary tree, but is there any native JavaScript data structure that I can use instead?

Answer 1

Sure. Make an dictionary object

dict = {
  string1: 1,
  string2: 1,
etc

It's guaranteed to provide O(1) lookup time.

Answer 2

There are various suitable structures and approaches, see below how they perform.

Array

• for loop
• for loop (reversed)
• array.includes(target)

Set

• set.has(target)

Object

• obj.hasOwnProperty(target)
• target in obj <- 1.29% slower
• obj[target] <- fastest

Map

• map.has(target) <- 2.94% slower

Results from January 2021, Chrome 87

JSBench tests https://jsbench.me/3pkjlwzhbr/1

// https://jsbench.me/3pkjlwzhbr/1
// https://docs.google.com/spreadsheets/d/1WucECh5uHlKGCCGYvEKn6ORrQ_9RS6BubO208nXkozk/edit?usp=sharing
// JSBench forked from https://jsbench.me/irkhdxnoqa/2

var theArr = Array.from({ length: 10000 }, (_, el) => el)
var theSet = new Set(theArr)
var theObject = Object.assign({}, ...theArr.map(num => ({ [num]: true })))
var theMap = new Map(theArr.map(num => [num, true]))

var theTarget = 9000


// Array

function isTargetThereFor(arr, target) {
  const len = arr.length
  for (let i = 0; i < len; i++) {
    if (arr[i] === target) {
      return true
    }
  }
  return false
}
function isTargetThereForReverse(arr, target) {
  const len = arr.length
  for (let i = len; i > 0; i--) {
    if (arr[i] === target) {
      return true
    }
  }
  return false
}

function isTargetThereIncludes(arr, target) {
  return arr.includes(target)
}

// Set

function isTargetThereSet(numberSet, target) {
  return numberSet.has(target)
}

// Object 

function isTargetThereHasOwnProperty(obj, target) {
  return obj.hasOwnProperty(target)
}
function isTargetThereIn(obj, target) {
  return target in obj
}
function isTargetThereSelectKey(obj, target) {
  return obj[target]
}

// Map

function isTargetThereMap(numberMap, target) {
  return numberMap.has(target)
}

---

This answer is migrated from https://stackoverflow.com/a/65604244/985454