c - src dest ip + port 的哈希函数

Question

因此，我正在研究不同的哈希函数，用于对 4 元组 ip 和端口进行哈希处理以识别流。

我遇到的一个是

((size_t)(key.src.s_addr) * 59) ^
((size_t)(key.dst.s_addr)) ^
((size_t)(key.sport) << 16) ^
((size_t)(key.dport)) ^
((size_t)(key.proto));

现在对于我的生活，我无法解释所使用的质数 (59)。为什么不是 31，然后为什么要把这项运动乘以 2 的幂来搞砸它。是否有更好的哈希函数可用于 ip 地址？

Answer 1

之所以使用质数，是因为当一个值乘以质数时，当其他类似操作在其之上累积时，它往往有更高的可能性保持唯一性。特定值 59 可能是任意选择的，也可能是有意选择的。这很难说。 59 可能会根据最有可能的输入生成更好的值分布。

移位 16 可能是因为端口被限制在 2^16 的范围内。该函数似乎将源端口移动到位域的较高部分，同时将目标端口留在较低部分。我认为这可以在我的下一段中进一步解释。

乘法发生的另一个原因(移位操作也是如此)是因为它打破了哈希函数的关联性质。请记住，XOR 是关联的，因此如果不存在乘法运算，IP src=192.168.1.1 和 dst=192.168.1.254 将散列为与 src=192.168.1.254 和 dst=192.168.1.1(交换)相同的值。