为什么在哈希表中模数不足够作为哈希函数？

Question

我经常看到或听到模数被用作哈希的最后一步，或在哈希之后使用。例如，h(input)%N，其中h是哈希函数，%是模运算符。如果我正在设计一个哈希表，并希望将大量的键映射到较小的索引空间以供哈希表使用，那么模运算符不就可以实现这个目的吗？此外，如果我想在哈希表中的这些位置上随机分布，那么模数生成的余数是否足够了？那么哈希函数h提供了什么额外的功能呢？

- imagineerThat

Answer 1

我经常看到或听说模数被用作哈希的最后一步或在哈希之后。例如，h(input) % N，其中h是哈希函数，%是模运算符。

确实如此。

如果我正在设计哈希表，并希望将大量键映射到哈希表的较小索引空间中，那么模运算符不就可以实现吗？

这正是模运算符的目的：限制数组索引的范围，所以是的。

但是你不能简单地仅使用模运算符：模运算符需要一个整数值：你无法获得“字符串在N上的模”或“对象图在N上的模”[1]。

此外，如果我想要随机分配散布在哈希表中的位置，模运算符生成的余数是否不足够？

不，它不够-因为模运算符不会给出伪随机输出-也没有任何类型的avalanche效应-这意味着类似的输入值将具有相似的输出哈希，这将导致哈希表中的聚类，从而导致子优性能，因为哈希冲突的可能性大大增加（因此需要更慢的技术，如线性探测，这使哈希表失去了O（1）查找时间的目的。

哈希函数h提供了什么？ h的域可以是任何东西，特别是非整数值。

[1] 严格来说，如果使用对象的内存地址值（即对象指针），则可能会实现这一点，但如果哈希表键不使用对象标识符（例如堆栈分配的对象或自定义struct），则无法使用。

- Dai

---

不，它并不会——因为取模运算符不会给出伪随机的输出。如果我们将整数作为输入（并对其执行取模运算），只要输入不偶然地与number % N中的多个N倍数重叠，输出就不会均匀分布。然而，我确实理解你提到的伪随机有助于防止可能导致碰撞的具有可能模式的不可预测输入流的观点。 - imagineerThat

就在输入键类型为整数的情况下，哈希函数可能是多余的，但您需要确保您的键值域拥有最佳数量的存储桶，否则会产生未使用的存储桶（例如，如果您只限制于 ASCII char 值 [A-Z]，那么您不需要超过 26 个存储桶 - 实际上，您可以跳过使用哈希表，而直接使用可直接索引的固定大小数组。 - Dai

Answer 2

首先，哈希函数的主要目的是将非数字转换为数字。即使在此之后只使用模数来获取您范围内的数字，获取数字仍然是第一步，也是哈希函数的责任。如果您要对整数进行哈希，并且只使用整数作为它们自己的哈希值，那么并不是没有哈希函数，而是选择了恒等函数作为哈希函数。如果您不编写函数，则表示您已将其内联。

其次，哈希函数可以提供更不可预测的分布，以减少意外碰撞的可能性。人们处理的数据通常包含模式，如果您只使用简单的恒等函数和模数，则输入中的模式可能导致模数更容易引起冲突。哈希函数提供了一个机会来打破这种情况，使得模数不太可能暴露原始数据序列中的模式。

- Patrick87