В моих классах у меня есть следующее упражнение:
У меня есть GUID (глобальный уникальный идентификатор) с 128 битами.
Какая хеш-функция лучше представлять значения в сегментахс хэш-идентификатором от 000 до 899 у каждого сегмента есть 100 свободных мест для хранения хэш-коллизий?
Я хочу сравнить следующие хеш-функции:
a) h(a) = a mod 900
b) h(a) = a mod 887
c) h(a) = a^2 mod 887
d) there are not enough information to answer this question
Что у меня есть:
Я думаю, что не лучше использовать ^ 2, потому что это дало бы нам преимущество только в первых нескольких тысячах идентификаторов, они должны быть лучше распределены, но после этого мне, вероятно, пришлось бы проводить больше проверок столкновений, чтобысохранить эти значения в других сегментах.
Я попытался выполнить поведение, описанное выше: в приведенном ниже фрагменте я генерирую 90000 «случайных» уникальных чисел, которые хранятся внутри карты, с хэш-функцией, следующей за модом 900Я знаю, что по некоторым причинам простые числа предпочтительнее использовать для хеш-функций.
Случайность реализована только до 32-битного макс.Но я думаю, что это не должно быть слишком важно, чтобы я не использовал 128-битный макс.
m = null;
uniqueMap = new Map();
hash = (z, p) => z % p ;
function getRandomInt(max) {
guid = Math.floor(Math.random() * Math.floor(max));
if (uniqueMap.has(guid)) return getRandomInt(max);
return guid;
}
map = new Map();
for (var i = 1; i <= 90000; i++) {
h = hash(getRandomInt(2147483647), 900);
map.has(h) ? map.set(h, map.get(h) + 1) : map.set(h, 1);
}
map.forEach((a) => m = Math.max(a, m))
console.log(m);
Следующий фрагмент с теми же функциями, но с модом 887:
m = null;
uniqueMap = new Map();
hash = (z, p) => z % p ;
function getRandomInt(max) {
guid = Math.floor(Math.random() * Math.floor(max));
if (uniqueMap.has(guid)) return getRandomInt(max);
return guid;
}
map = new Map();
for (var i = 1; i <= 90000; i++) {
h = hash(getRandomInt(2147483647), 887);
map.has(h) ? map.set(h, map.get(h) + 1) : map.set(h, 1);
}
map.forEach((a) => m = Math.max(a, m))
console.log(m);
и с ^ 2:
m = null;
uniqueMap = new Map();
hash = (z, p) => z % p ;
function getRandomInt(max) {
guid = Math.floor(Math.random() * Math.floor(max));
if (uniqueMap.has(guid)) return getRandomInt(max);
return guid;
}
map = new Map();
for (var i = 1; i <= 90000; i++) {
h = hash(Math.pow(getRandomInt(2147483647),2), 887);
map.has(h) ? map.set(h, map.get(h) + 1) : map.set(h, 1);
}
map.forEach((a) => m = Math.max(a, m))
console.log(m);
все внутри одного:
m = null;
uniqueMap = new Map();
hash = (z, p) => z % p ;
function getRandomInt(max) {
guid = Math.floor(Math.random() * Math.floor(max));
if (uniqueMap.has(guid)) return getRandomInt(max);
return guid;
}
map = new Map();
for (var i = 1; i <= 90000; i++) {
h = hash(getRandomInt(2147483647), 900);
map.has(h) ? map.set(h, map.get(h) + 1) : map.set(h, 1);
}
map.forEach((a) => m = Math.max(a, m))
console.log(m);
m = null;
uniqueMap = new Map();
map = new Map();
for (var i = 1; i <= 90000; i++) {
h = hash(getRandomInt(2147483647), 887);
map.has(h) ? map.set(h, map.get(h) + 1) : map.set(h, 1);
}
map.forEach((a) => m = Math.max(a, m))
console.log(m);
m = null;
uniqueMap = new Map();
map = new Map();
for (var i = 1; i <= 90000; i++) {
h = hash(Math.pow(getRandomInt(2147483647),2), 887);
map.has(h) ? map.set(h, map.get(h) + 1) : map.set(h, 1);
}
map.forEach((a) => m = Math.max(a, m))
console.log(m);
Если я сравниваю эти 3 метода, они показывают мне, что наибольшее число столкновений с модом ^ 2 выше, чем у 887 и 900 без включения гидов.Поэтому я предполагаю, что это не может быть правильным ответом.
Но как мне сравнить два других?они показывают мне похожие пики с небольшой разницей.