javascript - 哪个哈希函数更适合在小型哈希表中表示 128 位随机 id

标签 javascript hash hash-function

在我的类里面,我有以下练习:

我有 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

我得到的:

我认为使用 a^2 并不好,因为它只会在前几千个 id 中给我们带来好处,它们应该更好地分布,但之后,我可能不得不进行更多的碰撞探测来存储这些其他桶中的值。

我已尝试完成上述行为: 在下面的代码片段中,我生成了 90000 个“随机”唯一数字,这些数字存储在 map 中,散列函数遵循 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);

还有一个^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 供电。 所以我认为这不是正确的答案。

但是我应该如何比较其他两个呢?他们向我展示了相似的峰,只有很小的差异。

最佳答案

您可以通过简单地检查哪个具有较少的因子来比较其他两个,因为质数具有较少的因子,它们用于哈希。

之所以两者之间的差异可以忽略不计,主要是因为你使用的散列函数。您的哈希函数已经给出了分布良好的值。但是由于问题是关于直接比较的。最好的方法是选择质数为 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/

关于javascript - 哪个哈希函数更适合在小型哈希表中表示 128 位随机 id,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55384412/

相关文章:

javascript - Windows 8 JS 应用程序中的 jQuery

javascript - 将按 ASCII 顺序排序的一维数组转换为 Javascript 中的嵌套数组

javascript - 我可以将消息从接收者发送回发送者吗?

开放简历 |筛选冲浪 |散列 |图片搜索

python - (1) 哈希函数、(2) 签名长度和 (3) jaccard 相似度之间的关系?

javascript - 如何从第一个下拉列表的 onchange 填充 2 个文本框和 1 个下拉列表

ruby - 如何从两个大小相等的数组构建 Ruby 哈希?

c# - 在 C# 中从哈希集中检索对象

java - Java中HashMap的内部实现

c++ - C++ 标准是否为 unordered_set 定义了桶的结构?