Skip to content

Instantly share code, notes, and snippets.

@yhahn
Created July 31, 2015 17:16
Show Gist options
  • Save yhahn/ab79aa73591a997a64e3 to your computer and use it in GitHub Desktop.
Save yhahn/ab79aa73591a997a64e3 to your computer and use it in GitHub Desktop.
murmur collision tests
var fnvplus = require('fnv-plus');
var murmur = require('murmur');
function collisionRate(bits) {
var hashes = {};
var texts = 0;
var collisions = [];
var sample = 1e6;
console.time(bits + ' bits');
while (texts < sample) {
var name = Math.random().toString(36);
var num = parseInt(murmur.hash128(name).hex().substr(-1*(bits/4)), 16);
if (hashes[num] === name) {
continue;
} else if (hashes[num]) {
collisions.push([hashes[num], name]);
} else {
hashes[num] = name;
}
texts++;
}
console.timeEnd(bits + ' bits');
console.log('%d bits, collisions: %s% (%s/%s)', bits, (collisions.length/sample * 100).toFixed(3), collisions.length, sample);
}
collisionRate(32);
collisionRate(52);
// 32 bits: 10440ms
// 32 bits, collisions: 0.011% (110/1000000)
// 52 bits: 12697ms
// 52 bits, collisions: 0.000% (0/1000000)
{
"name": "murmur-collisions",
"dependencies": {
"murmur": "0.0.2"
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment