Run results for: array vs hashmap1 vs array-polling

Run details:

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/14.1.1 Safari/605.1.15

Browser: Safari 14

Operating system: Mac OS X 10.15.7

Device Platform: Desktop

Date tested: 3 years ago

Test name	Executions per second
find by binary search array	1066133.8 Ops/sec
find by array polling	2206613.0 Ops/sec
find by hashmap	2759216.0 Ops/sec
find by func find	2088421.6 Ops/sec

Script Preparation code:

const array = [];

for (let i = 0; i < 100; i++) {
    array.push({
        key: i,
        prop: Math.floor(Math.random() * 10000)
    })
}

function hashmap () { return array.reduce((mapper, next) => ({
    ...mapper,
    [next.key]: next
}), {});}

let hashmap1;

function findInArray (key) {
    const index = bs(array, key, function(element, needle) {
        return element.key - needle;
    });
    return index > 0 ? array[index] : undefined;
}

function findArrayFind (key) {
  return array.find(elem=>elem.key===key);
}

function findInHashMap (key) {
  if (!hashmap1) {
    hashmap1 = hashmap();
  }
    return hashmap1[key] || undefined;
}

function findInArrayByPolling (key) {
    for (let i = 0, len = array.length ; i < len; i++) {
        if (array[i].key === key) {
            return array[i]
        }
    }
}



function bs(haystack, needle, comparator, low, high) {
    var mid, cmp;
  
    if(low === undefined)
      low = 0;
  
    else {
      low = low|0;
      if(low < 0 || low >= haystack.length)
        throw new RangeError("invalid lower bound");
    }
  
    if(high === undefined)
      high = haystack.length - 1;
  
    else {
      high = high|0;
      if(high < low || high >= haystack.length)
        throw new RangeError("invalid upper bound");
    }
  
    while(low <= high) {
      // The naive `low + high >>> 1` could fail for array lengths > 2**31
      // because `>>>` converts its operands to int32. `low + (high - low >>> 1)`
      // works for array lengths <= 2**32-1 which is also Javascript's max array
      // length.
      mid = low + ((high - low) >>> 1);
      cmp = +comparator(haystack[mid], needle, mid, haystack);
  
      // Too low.
      if(cmp < 0.0)
        low  = mid + 1;
  
      // Too high.
      else if(cmp > 0.0)
        high = mid - 1;
  
      // Key found.
      else
        return mid;
    }
  
    // Key not found.
    return ~low;
}

Tests:

find by binary search array
const target = Math.floor(Math.random() * 100); findInArray(target);
find by array polling
const target = Math.floor(Math.random() * 100); findInArrayByPolling(target);
find by hashmap
const target = Math.floor(Math.random() * 100); findInHashMap(target);
find by func find
const target = Math.floor(Math.random() * 100); findArrayFind(target)

Run results for: array vs hashmap1 vs array-polling

find by binary search array

find by array polling

find by hashmap

find by func find