algorithm - 高斯分布+哈希表

Question

我对哈希函数有一个奇怪的想法。问题陈述是

You are storing id-numbers of 162 students in a class obtaining n marks out of 300 in a course (for each n=0, 1, 2, ... 300) in a hash table. Devise the simplest and least collision prone hash function for this such that the wasted memory cells also are minimum. Here, a collision is when two students scoring n₁ and n₂ get the same slot in the hash table.

一种解决方案是使用 h(n) = (n*5 + 7) % 163 和链接。最多可以有 162 个不同的标记。

编辑 有几种标准方法可以做到这一点。但我想尝试我的想法并检查它(也许在数学上)。它可能会与较少的内存发生较少的冲突。

---

现在，这是我的想法。我可以假设标记的分布是 gaussian .因此，接近平均分的人更多，而接近平均分的人更少。

所以，我可以有一个像这样的哈希函数:

h(n) = 0 (if n<100 || n>200)
h(n) = 1 (if 100<=n<125 || 175<=n<200)
h(n) = 2 (if 125<=n<140 || 160<=n<175)
h(n) = 3 (if 140<=n<160)

对于某些这样的条件(比如，k)，哈希表将具有最少的冲突次数和最少的空间占用。

现在，这只是一个猜测。这样的事情有意义吗？有没有办法证明这一点？还是我哪里错了？

Answer 1

您在此处手动执行的操作在图像处理中称为histogram equalization .我认为这绝对有道理，因为您可以确保统计上所有插槽的使用概率相同，因此您可以最大限度地减少冲突。