哪个散列函数更适合表示小型散列表中的128位随机id
在我的课堂上，我做了以下练习：
我有128位的GUID(全局唯一标识符)。
哪个散列函数更适合表示hashID为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并不更好，因为它只会在前几千个I中给我们带来好处，它们应该更好地分布，但之后，我可能不得不进行更多的冲突探测来将这些值存储在其他存储桶中。
我已经尝试完成了上面描述的行为:在下面的代码片段中，我生成了90000个“随机”的唯一数字，这些数字存储在一个映射中，在mod900之后使用哈希函数。我知道出于某些原因，素数更适合用于哈希函数。
随机性仅实现为最大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);
下一个片段具有相同的函数，但使用mod 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种方法，他们告诉我mod a^2的最高冲突计数比887和900都要高，而不给guid加电。所以我认为这不可能是正确的答案。
但是我应该如何比较另外两个呢？他们向我展示了相似的峰值，只是有很小的区别。
回答 1
Stack Overflow用户
发布于 2019-03-29 06:31:22
您可以通过简单地检查哪一个具有较少的因子来比较其他两个，因为素数具有较少的因子，它们用于散列。
两者之间的差异可以忽略不计的原因主要是由于您使用的散列函数。您的散列函数已经给出了分布良好的值。但由于问题是关于直接比较。最好的方法是选择素数为mod 887的那个
cs.stackexchange对此有一个非常好的解释
有关更多信息，请访问此链接https://cs.stackexchange.com/questions/11029/why-is-it-best-to-use-a-prime-number-as-a-mod-in-a-hashing-function
了解更多关于模块化散列https://algs4.cs.princeton.edu/34hash/的详细信息
https://stackoverflow.com/questions/55384412
复制相似问题