Run results for: array vs hashmap vs array-polling

Run details:

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_14_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/79.0.3945.117 Safari/537.36

Browser: Chrome 79

Operating system: Mac OS X 10.14.6

Device Platform: Desktop

Date tested: 4 years ago

Test name	Executions per second
find by binary search array	1185816.0 Ops/sec
find by array polling	689623.9 Ops/sec
find by hashmap	2872956.0 Ops/sec

Script Preparation code:

const array = [];

for (let i = 0; i < 2000; i++) {
    array.push({
        key: i,
        prop: Math.floor(Math.random() * 10000)
    })
}

const hashmap = array.reduce((mapper, next) => ({
    ...mapper,
    [next.key]: next
}), {});

function findInArray (key) {
    const index = bs(array, key, function(element, needle) {
        return element.key - needle;
    });
    return index > 0 ? array[index] : undefined;
}

function findInHashMap (key) {
    return hashmap[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() * 2000); findInArray(target);
find by array polling
const target = Math.floor(Math.random() * 2000); findInArrayByPolling(target);
find by hashmap
const target = Math.floor(Math.random() * 2000); findInHashMap(target);

Run results for: array vs hashmap vs array-polling

find by binary search array

find by array polling

find by hashmap