randomlyDistributedHash

randomlyDistributedHash.js

// Deprecated: Dont use this. Just use fnv1a hash
function randomlyDistributedHash(s) {
  // fnv1a hash
  var h = 0x811c9dc5;
  for (var i = 0, l = s.length; i < l; i++) {
      h ^= s.charCodeAt(i);
      h += (h << 1) + (h << 4) + (h << 7) + (h << 8) + (h << 24);
  }
  h = (h >>> 0);
  
  // testing whether a Pseudo random number generator would give more uniform distribution
  // than using fnv1a hash alone.
  
  // Park-Miller-Carta Pseudo-Random Number Generator
  var seed = h; // use fnv1a hash as seed
  seed = seed % 2147483647;
  if (seed <= 0) num += 2147483646;
  return seed * 16807 % 2147483647;
}

// Usage with example: Distributing customers to servers 
// var servers = ['server1', 'server2', 'server3'];
// console.log(
//   'server to use for customer =',
//   servers[ randomlyDistributedHash('sessionIDOfCustomer') % servers.length ]
// );

My initial test was wrong. Seems like fnv1a has better bucket distribution.

Testing method:
I tried mapping the first 1 million number (converted to string) mapped into 10 buckets. Sequential data is useful for test as it would test how a single character change would affect distribution. A perfect hash would map exactly 1m/10 entries to each bucket. So for each bucket I counted hits / 1m (* 100 for percentage). Looks like fnv1a has lower average and max deviation from the ideal number.

Testing fnv1a
distribution (in %) {
  '0': 9.977,
  '1': 9.9886,
  '2': 9.9869,
  '3': 10.0043,
  '4': 10.001,
  '5': 10.0098,
  '6': 10.0155,
  '7': 10.0191,
  '8': 10.019599999999999,
  '9': 9.9782
}
avgDeviation 0.01385999999999985
maxDeviation 0.022999999999999687
-------------

Testing randomlyDistributedHash
distribution (in %) {
  '0': 9.9714,
  '1': 9.9897,
  '2': 9.990400000000001,
  '3': 10.0365,
  '4': 10.0207,
  '5': 10.014199999999999,
  '6': 9.9576,
  '7': 9.9855,
  '8': 9.9965,
  '9': 10.037500000000001
}
avgDeviation 0.021780000000000223
maxDeviation 0.04240000000000066