algorithm - 如何有效地散列 ip 地址

Question

这是一道面试题。我想过一些解决方案，比如多路哈希，但找不到优雅的东西。请推荐一些好的方法。

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

提示:使用 IP 本身作为 key 是个坏主意，因为会浪费很多空间

Answer 1

有趣的是，这么有趣的问题却没有任何有趣的答案(抱歉重复)。

如果您将其视为理论问题，那么此链接就是您所需要的(甚至还有一个为您编写并准备就绪的 superfast 哈希函数):

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

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

另一个用例 - TCP 连接跟踪，其中客户端使用由内核随机分配的临时端口(这不是散列的理想选择吗？)。问题是范围有限:类似于 32768-61000，它使最低有效字节比最高有效字节更随机。因此，您可以将最高有效字节与 IP 地址中可能为零 (c) 的最易变字节进行 XOR，并将其用作 64K 表中的哈希。