在我的课堂上,我进行了以下练习：

我有128bit的GUID(全局唯一标识符).

哪种哈希函数更好地表示哈希ID为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,887);
  map.has(h) ? map.set(h,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),m))

console.log(m);

全部内在：

m = null;
uniqueMap = new Map();
hash = (z,m))

console.log(m);

m = null;
uniqueMap = new Map();
map = new Map();
for (var i = 1; i <= 90000; i++) {
  h = hash(getRandomInt(2147483647),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),m))

console.log(m);

如果我正在比较这3种方法,他们会告诉我,在不使用GUID的情况下,使用mod a ^ 2的最高碰撞计数高于887和900.
因此,我认为这不是正确的答案.

但是我应该如何比较其他两个呢？它们显示出相似的峰,但差异很小.