javascript - 哪个哈希函数更适合在小哈希表中表示 128 位随机 id
问题描述
在我的课上,我做了以下练习:
我有 128bit 的 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
我有什么:
我认为使用 a^2 并不是更好,因为它只会在前几千个 id 中给我们带来好处,它们应该更好地分布,但之后,我可能不得不进行更多的碰撞探测以将这些值存储在其他桶。
我试图完成上述行为:在下面的代码片段中,我生成了 90000 个“随机”唯一数字,这些数字存储在地图中,哈希函数遵循 mod 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);
具有相同功能但使用 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);
并使用 a^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 种方法,它们会告诉我,在没有为 guid 供电的情况下,使用 mod a^2 的最高碰撞计数高于 887 和 900。所以我认为这不是正确的答案。
但是我应该如何比较另外两个呢?他们向我展示了相似的峰,只有很小的差异。
解决方案
您可以通过简单地检查哪个具有较少数量的因子来比较其他两个,因为素数具有较少的因子用于散列。
之所以两者之间的差异可以忽略不计,主要是由于您使用的哈希函数。您的散列函数已经给出了分布良好的值。但由于问题是关于直接比较。最好的方法是选择具有素数 a 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 -功能
以及有关模块化散列的更多详细信息 https://algs4.cs.princeton.edu/34hash/
推荐阅读
- c# - 我们可以在有和没有 jsonbody 的情况下重载 API
- javascript - 使用js移动对象时过渡不起作用
- python - 如何在 python 正则表达式中使用前瞻查找每个匹配项?
- javascript - 状态改变时报错【渲染方法应该是props和state的纯函数】
- arrays - 我可以将数组对象推送到 mongodb 上的空数组吗?(使用去)
- android - 删除 dispatchkeyevent 调用两次
- python - 给 numpy 数组 A 和是 MxN 和 B 这是 DxN 找到 AB=L2(A[i,:]-B[:,j]) 的欧几里德距离 st ijth 元素
- azure-logic-apps - For Each 中未显示逻辑应用迭代失败
- javascript - 类型上不存在属性:为什么 TypeScript 会抱怨而 JavaScript 没有?
- r - 在 R 中创建一个向量(关联数组)