如何有效地散列ip-address

Question

这是一个面试问题.我想过像multiway-hashing这样的解决方案,却找不到优雅的东西.请提出一些好的方法.

问题:您有1000万个IP地址.(IPv4 4字节地址).为这些IP地址创建哈希函数.

提示:使用IP本身作为关键是一个坏主意,因为会浪费很多空间

Answer 1

有趣的是，这样一个有趣的问题没有任何有趣的答案（对不起重言式）。

如果您将其视为理论问题，那么此链接就是您所需要的（甚至还有superfast为您编写并可以使用的哈希函数）：

http://www.kfki.hu/~kadlec/sw/netfilter/ct3/

实际问题可能有所不同。如果哈希表的大小合理，则无论如何都必须处理冲突（使用链表）。因此，问问自己最终将发生什么用例？如果您的代码将在某个僻静的生态系统中运行，并且IP地址是a-b-c-d，c并且d是最易变的数字，并且d不会为空（假设您不处理网络），那么请使用64K存储桶的哈希表，并将其cd作为哈希会令人满意吗？

另一个用例-TCP连接跟踪，其中客户端使用由内核随机分配的临时端口（这不是哈希的理想选择吗？）。问题在于范围有限：类似32768-61000的东西，它使最低有效字节比最高有效字节更具随机性。因此，您可以将IP地址中的最高有效字节与易失性字节进行异或运算，c并将其用作zerro（），并将其用作64K表中的哈希。

Answer 2

因为您的输入是随机的并且表的大小较小，所以您设计的任何哈希函数的地址空间都将具有其自己的病态数据集，这将使您的哈希函数看起来很糟糕。我认为面试官想了解你对用作标准的现有哈希函数的了解。

以下是一些这样的哈希函数：

1. MD5

2. SHA-1,SHA-2

为什么这些函数比其他哈希函数工作得更好，因为如果不使用强力算法很难找到它们的病态数据集。因此，如果您拥有像这些一样好的东西，请不要告诉您的面试官（您可以获得该专利并在谷歌找到工作）。

对于散列 ip 地址，请对其使用 MD5 或 SHA 并截断为表的大小，然后就完成了。

注意： - 表的大小必须是素数以防止错误的散列。