Playing around with random keys, collisions, and slow lookups

.gitignore

node_modules/

index.js

const assert = require("assert");
const {
  toPairs,
  toArray,
  countBy,
  times,
  random,
  snakeCase
} = require("lodash");

const {
  KEY_LENGTH,
  ITERATIONS,
  MAX_RETRIES,
  DELAY_LOOKUP_MIN,
  DELAY_LOOKUP_MAX,
  CHAR_SET
} = process.argv.slice(2).reduce(
  (acc, k, i, list) => {
    if (i % 2 > 0) return acc;
    const key = snakeCase(k.slice(2)).toUpperCase();
    const value = list[i + 1];
    acc[key] = /^\d+$/.test(value) ? Number(value) : value;
    return acc;
  },
  {
    KEY_LENGTH: 4,
    ITERATIONS: 923521,
    MAX_RETRIES: Infinity,
    DELAY_LOOKUP_MIN: 0,
    DELAY_LOOKUP_MAX: 1,
    // Less ambiguous character set (no o, 0, 1, l, i, etc)
    CHAR_SET: "abcdefghjkmnpqrstuvwxyz23456789"
  }
);

assert.ok(
  ITERATIONS <= Math.pow(CHAR_SET.length, KEY_LENGTH),
  "Iterations is too big for the max of char set and key length"
);

const hrtimeN = hrtime => hrtime[0] * 1e9 + hrtime[1];
const hrtimeM = hrtime => hrtimeN(hrtime) / 1e6;
const hrtimeS = hrtime => hrtimeM(hrtime) / 1e3;

const sleep = time => {
  const stop = process.hrtime();
  while (hrtimeM(process.hrtime(stop)) < time) {}
  return true;
};

const generateKey = (length = KEY_LENGTH) =>
  times(length, () => CHAR_SET.charAt(random(0, CHAR_SET.length - 1))).join("");

class DelayMap extends Map {
  has(key) {
    if (DELAY_LOOKUP_MAX) {
      sleep(random(DELAY_LOOKUP_MIN || 0, DELAY_LOOKUP_MAX));
    }
    return super.has(key);
  }
}

const keys = new DelayMap();

const tryGenerateKey = () => {
  let key = null;
  let tries = 0;
  do {
    tries++;
    key = generateKey();
    if (!keys.has(key)) {
      return { key, tries };
    }
    if (tries >= MAX_RETRIES) {
      assert.fail(`Exceeded max retries ${MAX_RETRIES}`);
    }
  } while (true);
};

const start = process.hrtime();

for (let i = 0; i < ITERATIONS; i++) {
  const startKey = process.hrtime();
  const { key, tries } = tryGenerateKey();
  keys.set(key, tries);
  const endKey = process.hrtime(startKey);
  console.log(key, tries, keys.size, `${hrtimeM(endKey)}ms`);
}

assert.equal(keys.size, ITERATIONS);
const end = process.hrtime(start);

const countByTries = toPairs(countBy(toArray(keys.values())))
  .map(v => v.join(" "))
  .join("\n");

console.log("-".repeat(40));
console.log(countByTries);
console.log(`${hrtimeS(end)}s`);

package-lock.json

{
  "name": "key-collisions",
  "version": "1.0.0",
  "lockfileVersion": 1,
  "requires": true,
  "dependencies": {
    "lodash": {
      "version": "4.17.15",
      "resolved": "https://registry.npmjs.org/lodash/-/lodash-4.17.15.tgz",
      "integrity": "sha512-8xOcRHvCjnocdS5cpwXQXVzmmh5e5+saE2QGoeQmbKmRS6J3VQppPOIt0MnmE+4xlZoumy0GPG0D0MVIQbNA1A=="
    }
  }
}

package.json

{
  "name": "key-collisions",
  "version": "1.0.0",
  "dependencies": {
    "lodash": "^4.17.15"
  },
  "keywords": [],
  "license": "ISC",
  "main": "index.js",
  "private": true
}