jumphash.js

"use strict";

// 2862933555777941757 == 0x27bb2ee687b0b0fd
const PRNG_LO = 0x87b0b0fd;
const PRNG_HI = 0x27bb2ee6;

/*
 * jump consistent hash, as described here:
 *   http://arxiv.org/abs/1406.2294
 *
 * compute the bucket index for a hash value. normally the key is a hash
 * from a simple algorithm like FNV1a.
 *
 * - key: a Number
 * - bucketCount: # of buckets to distribute across
 */
function jumpConsistentHash(key, bucketCount) {
  let b = null, j = 0;
  const prng = [ key >>> 0, 0 ];

  while (j < bucketCount) {
    b = j;
    // key = key * 2862933555777941757ULL + 1;
    multiplyU64(PRNG_LO, PRNG_HI, prng[0], prng[1], prng);
    incrU64(prng);
    // j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
    //   j = floor((b + 1) / r)  where r is a (0, 1) randomish number.
    //   r is built by taking the highest 31 bits of the current PRNG output,
    //   and dividing by 0x8000000, as if it were a fixed-point number with
    //   the highest bit as integer and the low 31 bits as fraction.
    j = Math.floor((b + 1) * (0x80000000 / ((prng[1] >>> 1) + 1)));
  }
  return b;
}

// unsigned multiply of U64 * U64 -> U64 (dropping the high 64 bits of the product).
// product is an out-array of [ lo, hi ].
function multiplyU64(alo, ahi, blo, bhi, product) {
  // N * 0 = 0
  if ((alo == 0 && ahi == 0) || (blo == 0 && bhi == 0)) {
    product[0] = 0;
    product[1] = 0;
    return;
  }

  // ugh. 4-way 16-bit multiplication. here we go.
  // (treat each 16-bit section as a "digit" and multiply two four-digit numbers.)
  const a0 = alo & 0xffff, a1 = alo >>> 16, a2 = ahi & 0xffff, a3 = ahi >>> 16;
  const b0 = blo & 0xffff, b1 = blo >>> 16, b2 = bhi & 0xffff, b3 = bhi >>> 16;

  // this would ordinarily be 16 individual products, but we skip any that affect only the top 64 bits.
  // also: take advantage of the fact that we get a few more than 32 bits in each result.
  // Math.floor(x / 65536) to avoid bit loss with >>>. (js truncates to 32 bits before shifting.)
  const c0 = a0 * b0;
  const c1 = a1 * b0 + a0 * b1 + Math.floor(c0 / 65536);
  const c2 = a2 * b0 + a1 * b1 + a0 * b2 + Math.floor(c1 / 65536);
  const c3 = a3 * b0 + a2 * b1 + a1 * b2 + a0 * b3 + Math.floor(c2 / 65536);

  product[0] = ((c1 & 0xffff) << 16) | (c0 & 0xffff);
  product[1] = ((c3 & 0xffff) << 16) | (c2 & 0xffff);
}

function incrU64(product) {
  product[0] = (product[0] + 1) >>> 0;
  if (product[0] == 0) {
    product[1] = (product[1] + 1) >>> 0;
  }
}

const FNV32_INIT = 0x811c9dc5;
//const FNV32_PRIME = 0x01000193;

/*
 * return the 32-bit FNV1a hash of a string.
 */
function fnv1a(text) {
  const buffer = (text instanceof Buffer) ? text : new Buffer(text, "utf-8");
  let rv = FNV32_INIT;
  for (let i = 0; i < buffer.length; i++) {
    rv ^= buffer[i];
    // js can't really do int multiplication.
    rv += (rv << 1) + (rv << 4) + (rv << 7) + (rv << 8) + (rv << 24);
  }
  return rv >>> 0;
}