src dest ip + port的哈希函数
所以，我正在研究用于散列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地址？
使用素数是因为当一个值乘以素数时，当其他类似操作累积在其上时，它往往具有更高的保持唯一概率。 特定值59可以是任意选择的，也可以是有意的。 这很难说。 有可能59倾向于根据最可能的输入生成更好的值分布。
移位16可能是因为端口被限制在2 ^ 16的范围内。 该function似乎是将源端口移动到位域的较高部分，同时将目标端口保留在下部。 我认为这可以在我的下一段进一步解释。
乘法发生的另一个原因（并且这也适用于移位操作）是因为它打破了散列函数的关联性质。 请记住，XOR是关联的，因此如果乘法不存在，则IP src = 192.168.1.1和dst = 192.168.1.254将散列为与src = 192.168.1.254和dst = 192.168.1.1（交换）相同的值。
检查函数的输出以进行均匀分布。 如果你不喜欢它，请插入一些不同的素数，直到你得到你喜欢的发行版。 哈希可以是一个非常黑暗的艺术，没有“正确”的答案。
就个人而言，我认为你最好将四个IP字节作为无符号长读取，这样可以得到一个大致在0 – 2 ^ 32-1范围内的数字。 然后，您可以计算出您希望在任何时间激活多少个流，这将是您的索引表大小。
以2000为例。 这意味着你想要将2 ^ 32个数字映射到大约2 ^ 11个indeces（流信息）。 这是行不通的，因为如果填充到100％，哈希几乎不会工作，甚至90％都很难。 使用只填充50％（4000个余额）甚至25％（8000个）的索引表对今天的记忆没什么大不了的。
索引表的确切大小应该是不均匀的位置数，并且最好是素数。 这是因为你很可能需要一些溢出处理来处理冲突（两个或多个ip编号，它们在散列之后指向索引表中的相同位置） – 你将得到它。 溢出处理应该是小于索引表大小的另一个素数。 所有这些素数！ 他们还有什么关系？
我将举例说明（在C中）：
idxsiz = prime(2000 * 2); // 50% loading ovfjmp = prime(idxsiz/3);
…
最初使用UNUSED标记（-1）填充idxjmp位置表。 准备好DELETED标记（-2）。
您的IP号码进入系统并查找其流记录（可能存在也可能不存在）：
stoppos = ip % idxsiz; /* modulo (division) just this once */ i = stoppos; do { if (index[i] == UNUSED) return NULL; if (index[i] != DELETED) { flowrecptr = &flow_record[index[i]]; if (!flowrecptr->in_use) {/* hash table is broken */} if (flowrecptr->ip == ip) return flowrecptr; } i += ovfjmp; if (i >= idxsiz) i -= idxsiz; } while (i != stoppos); return NULL;
UNUSED作为这个指数从未使用过的标记，搜索应该停止。 DELETED用作此索引已被使用但不再使用的标记。 这意味着搜索必须继续。
这是你试图获得的时候。 你从get获得了一个NULL，所以你需要做一个put，你首先找到包含UNUSED或DELETED的第一个索引位置。 将此值替换为flow_record表上第一个/下一个空行的索引。 将该行标记为in_use。 将原始ip号放入flow_record行的ip成员中。
这是构建散列机制的一种非常简单但非常有效的方法。 实际上，在此function失效后使用的特殊functionforms的每个优化都将提高散列的有效性。
素数的使用将确保 – 在最坏的情况下所有索引位置都被占用 – 该机制将测试每个位置。 为了说明这一点：假设idxsiz可以被ovfjmp整除：你不会有太多的溢出处理。 35和7将导致在索引跳转到0之前测试位置0,7,14,21和28，其中while测试将导致搜索停止。
———————- OOPS！
我错过了你想要的端口号。 假设ip V4意味着6个字节的地址。 将其读取为无符号的64位整数，并清除前16位/ 2字节。 然后你做模数计算。
Brian Gideon几乎总结了一下; 乘法和移位旨在作为对称破坏者。 因此，这可以捕捉机器A远程登机到机器B的假设情况，反之亦然，他们碰巧选择了相同的短暂的portnum。 不是很常见，但并非不可能。 5元组的大部分都是相当不变的：协议来自一个非常小的域，{address，portnum}的一半也是如此。
假设一个主要大小的哈希表，魔术常数59可以被任何素数IMO替换。 （端口<< 16）也可以被另一个移位替换，只要没有位丢失或甚至是（port * some_other_prime）项。
对于二次幂大小的哈希表，5元组的所有（减1）成员应乘以（不同的）素数。 （在过去，当划分很昂贵时，本来可以选择）