应用复杂的哈希函数然后取 mod n 而不是简单地对输入做 mod n 有什么好处？
What is the advantage of applying a complex hash function and then taking mod n instead of simply doing mod n for the input?
在散列中，我们获取输入并应用一些复杂的散列算法。然后，我们执行 mod n 以找到需要将此输入发送到的存储桶或服务器。
哈希输入 x -> Hash(x) -> 除以 n - >Hash(x) mod n 给出桶的位置。
如果我们直接取输入，不经过哈希处理，就相当于有了一个恒等哈希函数。 Hash(x) =x .. mod n..维基百科将此函数称为 'trivial' 哈希函数。
一般来说，hash(x)是一种复杂的哈希算法，如MD5、SHA等...
Q1）无论我们如何对其进行哈希处理，它都归结为介于 0 和 n-1 之间的值（除以 n 时的提示）。那么，哈希函数的选择有什么关系呢？
Q2) 我知道理想的哈希函数将输入值均匀分布在桶中。在这方面，那些复杂的哈希函数是否优于哈希恒等函数？
假设输入总是一个整数。
What is the advantage of applying a complex hash function and then taking mod n instead of simply doing mod n for the input?
让我们看一个简单的例子。假设我们的键是 100 个指向内存中 8 字节对齐对象的指针：这意味着 3 least-significant 位始终为 0。我们的 table 大小目前是 128 个桶。我们 mod 在散列之前将指针值乘以 128，我们有效地采用：
32-bit pointer bits xxxxxxxx xxxxxxxx xxxxxxxx xxxxx000
mod 128 00000000 00000000 00000000 0xxxx000
请注意，指针中只有 4 个可能有意义的位通过我们的哈希函数，这意味着 最多 16 个不同的值到达哈希函数：我们的 100 个指针将发生冲突只有 16 个桶，这意味着即使对于最强的哈希函数，碰撞链通常也有 7 或 8 个深度。考虑到我们有 100 个键的 128 个桶，这很糟糕：我们应该将大部分 0、1 或 2 个键映射到任何给定的桶。
现在，如果我们有 100 个指向内存映射区域的指针，每个 4096 字节页面对齐，会发生什么情况？他们都会映射到同一个桶。
直到最后才执行 mod 操作确保密钥中的高阶位可以帮助随机化哈希值中的低阶位位置，而那些 lower-significance 位可以影响桶键映射到。 （另一件可以有点帮助的事情是确保 table 大小是质数，但最好在散列后与 mod 结合使用。作为随机抽样，GNU 的 C++ 编译器使用素数桶计算标准库散列 tables，而 Visual C++ 使用 2 的幂（对于长字符串更快但散列函数较弱））
Q1) Regardless of how we hash it, it just boils down to a value between 0 and n-1(reminder when divided by n). So, how does the choice of hashing function matter?
显然，如果我们的哈希函数是 h(key) { return 0 }，则每个键都会在桶 0 处发生冲突。在另一个极端，加密哈希函数应该有效地 randomly-but-repeatedly 将任何给定的键映射到给定的桶，例如密钥中任何位置的任何位更改都会创建一个完全不相关的映射。这有助于保护您免受与在许多位位置上不变的密钥的过度冲突。但是，强大的哈希函数往往需要更长的时间来计算，并且冲突的减少可能会也可能不会导致净性能获胜。有时值得根据键之间可能存在的差异来选择散列函数的强度。
Q2) I know that an ideal hash function distributes the input values uniformly across the buckets. In this aspect, are those complex hashing functions superior to the hash identity function?
在极端情况下，身份哈希函数希望输入数字映射到不同的桶上的概率比密码强度哈希函数高：例如，如果我们将 5、6、7、8、10 哈希到一个table 使用身份函数，它们是密集的（彼此靠近）并且仅跨越 6 个值（5 到 10），所以只要 table 大小 >= 6（例如质数7) 保证它们不会发生碰撞。但是，给定容易发生冲突的输入（例如，指向数字的指针）的身份哈希函数是一场灾难，因为它们在 mod 开始之前没有采取任何措施将 more-significant 位与 less-significant 位混合- 上面的指针解释了同样的问题。
总而言之，身份哈希函数对于普通整数键可以有更好的 average-case 性能，但对于 non-dense、non-random / [=40 的 worst-case 性能要差得多=]键。
在散列中，我们获取输入并应用一些复杂的散列算法。然后，我们执行 mod n 以找到需要将此输入发送到的存储桶或服务器。 哈希输入 x -> Hash(x) -> 除以 n - >Hash(x) mod n 给出桶的位置。
如果我们直接取输入，不经过哈希处理，就相当于有了一个恒等哈希函数。 Hash(x) =x .. mod n..维基百科将此函数称为 'trivial' 哈希函数。
一般来说，hash(x)是一种复杂的哈希算法，如MD5、SHA等... Q1）无论我们如何对其进行哈希处理，它都归结为介于 0 和 n-1 之间的值（除以 n 时的提示）。那么，哈希函数的选择有什么关系呢？ Q2) 我知道理想的哈希函数将输入值均匀分布在桶中。在这方面，那些复杂的哈希函数是否优于哈希恒等函数？
假设输入总是一个整数。
What is the advantage of applying a complex hash function and then taking mod n instead of simply doing mod n for the input?
让我们看一个简单的例子。假设我们的键是 100 个指向内存中 8 字节对齐对象的指针：这意味着 3 least-significant 位始终为 0。我们的 table 大小目前是 128 个桶。我们 mod 在散列之前将指针值乘以 128，我们有效地采用：
32-bit pointer bits xxxxxxxx xxxxxxxx xxxxxxxx xxxxx000
mod 128 00000000 00000000 00000000 0xxxx000
请注意，指针中只有 4 个可能有意义的位通过我们的哈希函数，这意味着 最多 16 个不同的值到达哈希函数：我们的 100 个指针将发生冲突只有 16 个桶，这意味着即使对于最强的哈希函数，碰撞链通常也有 7 或 8 个深度。考虑到我们有 100 个键的 128 个桶，这很糟糕：我们应该将大部分 0、1 或 2 个键映射到任何给定的桶。
现在，如果我们有 100 个指向内存映射区域的指针，每个 4096 字节页面对齐，会发生什么情况？他们都会映射到同一个桶。
直到最后才执行 mod 操作确保密钥中的高阶位可以帮助随机化哈希值中的低阶位位置，而那些 lower-significance 位可以影响桶键映射到。 （另一件可以有点帮助的事情是确保 table 大小是质数，但最好在散列后与 mod 结合使用。作为随机抽样，GNU 的 C++ 编译器使用素数桶计算标准库散列 tables，而 Visual C++ 使用 2 的幂（对于长字符串更快但散列函数较弱））
Q1) Regardless of how we hash it, it just boils down to a value between 0 and n-1(reminder when divided by n). So, how does the choice of hashing function matter?
显然，如果我们的哈希函数是 h(key) { return 0 }，则每个键都会在桶 0 处发生冲突。在另一个极端，加密哈希函数应该有效地 randomly-but-repeatedly 将任何给定的键映射到给定的桶，例如密钥中任何位置的任何位更改都会创建一个完全不相关的映射。这有助于保护您免受与在许多位位置上不变的密钥的过度冲突。但是，强大的哈希函数往往需要更长的时间来计算，并且冲突的减少可能会也可能不会导致净性能获胜。有时值得根据键之间可能存在的差异来选择散列函数的强度。
Q2) I know that an ideal hash function distributes the input values uniformly across the buckets. In this aspect, are those complex hashing functions superior to the hash identity function?
在极端情况下，身份哈希函数希望输入数字映射到不同的桶上的概率比密码强度哈希函数高：例如，如果我们将 5、6、7、8、10 哈希到一个table 使用身份函数，它们是密集的（彼此靠近）并且仅跨越 6 个值（5 到 10），所以只要 table 大小 >= 6（例如质数7) 保证它们不会发生碰撞。但是，给定容易发生冲突的输入（例如，指向数字的指针）的身份哈希函数是一场灾难，因为它们在 mod 开始之前没有采取任何措施将 more-significant 位与 less-significant 位混合- 上面的指针解释了同样的问题。
总而言之，身份哈希函数对于普通整数键可以有更好的 average-case 性能，但对于 non-dense、non-random / [=40 的 worst-case 性能要差得多=]键。