我正在尝试理解哈希表，从我所见，模运算符用于选择密钥将被放置在哪个桶中。我知道哈希算法应该最小化不同输入的相同结果，但是我不明白模运算后不同输入的相同结果如何最小化。假设我们有一个近乎完美的散列函数，它给出 0 到 100,000 之间的不同散列值，然后我们将结果取模 20（在我们的示例中，我们有 20 个桶），得到的数字不是非常接近0到19之间的随机数？大致意思是最终结果是 0 到 19 之间的任何一个数字的概率大约是 20 分之一？如果是这种情况，那么原始哈希函数不会 t 似乎确保了最小的冲突，因为在模运算之后我们最终得到了一个随机数之类的东西？我一定是错的，但我认为最能确保最小冲突的不是原始哈希函数，而是我们有多少桶。
我确定我误解了这一点。有人可以解释吗？
在对散列数进行取模后，您不会得到一个随机数吗？
这取决于哈希函数。
假设你有一个数字的标识哈希 - h(n) = n - 那么如果被哈希的键通常是递增的数字（可能偶尔会有遗漏），那么在哈希之后它们通常仍然会命中连续的桶（在某个点包装从最后一个桶回到第一个桶），整体碰撞率很低。不是很随机，但效果很好。如果密钥是随机的，它仍然可以很好地工作 - 请参阅下面的随机但可重复散列的讨论。问题是当密钥既不是粗略递增也不是接近随机时 - 那么身份哈希可以提供可怕的冲突率。（您可能会认为“这是一个非常糟糕的示例哈希函数，没有人会这样做；实际上，大多数 C++ 标准库实现的整数哈希函数都是身份哈希）。
另一方面，如果你有一个散列函数，它表示要散列对象的地址，并且它们都是 8 字节对齐的，那么如果你使用 mod 并且桶数也是 8 的倍数，你只会散列到每 8 个桶，碰撞次数是您预期的 8 倍。不是很随机，而且效果不好。但是，如果桶的数量是素数，那么地址将倾向于更随机地分散在桶上，事情会变得更好。这就是 GNU C++ 标准库倾向于使用质数桶的原因（Visual C++ 使用大小为 2 的桶，因此它可以利用按位与将哈希值映射到桶，因为 AND 需要一个 CPU 周期，而 MOD 可以取例如 30-40 个周期 - 取决于您的确切 CPU - 请参见此处）。
当所有输入在编译时都是已知的，并且没有太多的输入，那么通常可以创建一个完美的哈希函数（GNU gperf 软件专门为此设计），这意味着它会计算出你的一些桶'将需要一个避免任何冲突的散列函数，但散列函数的运行时间可能比通用函数长。
人们经常有一个奇特的概念——也可以在问题中看到——“完美的散列函数”——或者至少有很少冲突的函数——在一些大的数字散列范围内将在散列表的实际使用中提供最小的冲突，因为这个stackoverflow问题确实是要了解这个概念的虚假性。如果键映射到那个大的散列范围的方式仍然存在模式和概率，那就不是真的了。
用于运行时输入的通用高质量哈希函数的黄金标准是具有您可能称之为“随机但可重复”的质量，甚至在模运算之前，因为该质量也适用于桶选择（即使使用桶选择的笨拙和不那么宽容的和位掩码方法）。
正如您所注意到的，这确实意味着您会在表格中看到冲突。如果您可以利用密钥中的模式来减少这种随机但可重复的质量会给您带来的冲突，那么一定要充分利用它。如果不是，散列的美妙之处在于，通过随机但可重复的散列，您的冲突在统计上与您的负载因子（存储元素的数量除以存储桶的数量）相关。
例如，对于单独的链接- 当您的负载因子为 1.0 时，1/e (~36.8%) 的桶往往是空的，另一个 1/e (~36.8%) 有一个元素，1/(2e) 或~18.4% 两个元素，1/(3!e) 约 6.1% 三个元素，1/(4!e) 或 ~1.5% 四个元素，1/(5!e) ~.3% 有五个等等。-无论表中有多少元素（即是否有 100 个元素和 100 个桶，或 1 亿个元素和 1 亿个桶），非空桶的平均链长度约为 1.58，这就是我们说查找/插入的原因/erase 是 O(1) 的常数时间操作。
我知道哈希算法应该最小化不同输入的相同结果，但是我不明白在模运算后不同输入的相同结果如何最小化。
这仍然是模数后的真实情况。最小化相同的结果意味着每个后模值具有（大约）相同数量的映射到它的键。我们特别关注存储在表中的正在使用的键，如果键的使用存在不均匀的统计分布。对于表现出随机但可重复质量的哈希函数，后模映射会有随机变化，但总体而言，它们对于大多数实际目的来说足够接近以达到均匀平衡。
回顾一下，让我直接解决这个问题：
假设我们有一个近乎完美的散列函数，它给出 0 到 100,000 之间的不同散列值，然后我们将结果取模 20（在我们的示例中，我们有 20 个桶），得到的数字不是非常接近0到19之间的随机数？大致意思是最终结果是 0 到 19 之间的任何一个数字的概率大约是 20 分之一？如果是这种情况，那么原始哈希函数似乎并不能确保最小的冲突，因为在模运算之后我们最终会得到一个随机数之类的东西？我一定是错的，但我认为最能确保最小冲突的不是原始哈希函数，而是我们有多少桶。
所以：
随机是好的：如果你得到类似随机但可重复的哈希质量，那么你的平均哈希冲突将在统计上被限制在低水平，实际上你不太可能看到特别可怕的冲突链，只要你保持合理的负载系数（例如 <= 1.0）
也就是说，您的“近乎完美的哈希函数......在 0 到 100,000 之间”可能是高质量的，也可能不是高质量的，这取决于值的分布是否具有会产生冲突的模式。如果对此类模式有疑问，请使用具有随机但可重复质量的散列函数。
如果你取一个随机数而不是使用散列函数会发生什么？然后对其进行取模？如果您调用 rand() 两次，您可以获得相同的数字 - 我猜一个正确的哈希函数不会这样做，或者是吗？甚至哈希函数也可以为不同的输入输出相同的值。
这条评论表明您正在努力解决随机性的可取性 - 希望我的答案的早期部分您现在对此很清楚，但无论如何，关键是随机性是好的，但它必须是可重复的：相同的密钥必须产生相同的预模哈希，因此模后值告诉您它应该在哪个桶中。
作为随机但可重复的示例，假设您曾经rand()填充一个数组，然后您可以通过对随机数进行异或来uint32_t a[256][8]散列任何 8 字节密钥（例如包括例如 a ）：double
auto h(double d) {
uint8_t i[8];
memcpy(i, &d, 8);
return a[i[0]] ^ a[i[1]] ^ a[i[2]] ^ ... ^ a[i[7]];
}
这将产生一个近乎理想的（rand()不是一个高质量的伪随机数生成器）随机但可重复的哈希，但是有一个需要查询较大内存块的哈希函数很容易被缓存未命中而减慢。
继 [Mureinik] 所说的之后，假设您有一个完美的散列函数，假设您的数组/存储桶已满 75%，那么对散列函数进行取模可能会导致 75% 的冲突概率。如果这是真的，我认为他们要好得多。虽然我现在只是在了解它们是如何工作的。
75%/75% 的事情对于高质量的哈希函数是正确的，假设：
关于“我认为他们好多了”。- 这实际上很好，正如我在前面的回答中提到的碰撞链长度的百分比所证明的那样。
我认为你对情况的理解是正确的。
散列函数和桶的数量都会影响碰撞的机会。例如，考虑最坏的哈希函数——返回一个常数值的哈希函数。无论您有多少个桶，所有条目都将集中到同一个桶中，并且您有 100% 的碰撞机会。
另一方面，如果你有一个（接近）完美的散列函数，那么桶的数量将是碰撞机会的主要因素。如果您的哈希表只有 20 个桶，那么最小的冲突机会确实是 20 分之一（随着时间的推移）。如果散列值没有均匀分布，那么至少在其中一个存储桶中发生冲突的可能性会大得多。你拥有的桶越多，碰撞的可能性就越小。另一方面，有太多的桶会占用更多的内存（即使它们是空的），并最终会降低性能，即使有更少的冲突。