Skip to content

Instantly share code, notes, and snippets.

@ooflorent
Created May 14, 2020 21:46
Show Gist options
  • Save ooflorent/aba892de6e7c548471c25ca13b12f7a0 to your computer and use it in GitHub Desktop.
Save ooflorent/aba892de6e7c548471c25ca13b12f7a0 to your computer and use it in GitHub Desktop.
function hashSet(arr) {
let h = 0;
for (let x of arr) {
h = Math.imul((h << 5) ^ x, 0x9e3779b9);
}
return h;
}
function rand(n) {
return (Math.random() * n) | 0;
}
function generateRandomSet(size) {
let set = [];
while (set.length < size) {
let x = 1 + rand(MAX_VALUE);
if (!set.includes(x)) {
set.push(x);
}
}
set.sort((a, b) => a - b);
return set;
}
function isEqualSet(a, b) {
if (a.length !== b.length) {
return false;
}
for (let i = 0; i < a.length && i < b.length; i++) {
if (a[i] !== b[i]) {
return false;
}
}
return true;
}
let collisions = [];
let hashMap = new Map();
const ATTEMPTS = 1000;
const MAX_VALUE = 400;
const MAX_SIZE = 4;
for (let i = 0; i < ATTEMPTS; i++) {
let set = generateRandomSet(1 + rand(MAX_SIZE));
let h = hashSet(set);
if (hashMap.has(h)) {
let collide = false;
let sets = hashMap.get(h);
for (let other of sets) {
if (!isEqualSet(other, set)) {
collide = true;
break;
}
}
if (collide) {
collisions.push(h);
sets.push(set);
}
} else {
hashMap.set(h, [set]);
}
}
for (let h of collisions) {
console.log(
"Collision:",
hashMap
.get(h)
.map((set) => `{${set.join(",")}}`)
.join(" ")
);
}
console.log(hashSet([1, 2, 3]));
console.log(hashSet([3, 2, 1]));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment