1

我需要实现一个哈希表来维护 IP 数据包。但是，由于数据包的唯一性，我无法使用单个元素（例如 IP 地址）来制作哈希键。以下是数据包中负责使数据包唯一的元素：

  1. 源 IP 地址（16 字节字符串，由于 IPv6 格式）
  2. 源端口（2 字节）
  3. 目的IP地址（又是16字节）
  4. 目的端口（2 字节） 5. id1（1 字节）

我知道，如果有一个元素来计算哈希值，可以使用任何已知的算法，如 MD5 等来完成。我的问题是，在哈希值计算的过程中，如何包含上述多个元素？

4

2 回答 2

3

你提到你知道如何散列单个元素的情况。

然后，您可以将所有列出的元素放入/复制/连接到单个缓冲区（例如大小为 16+2+16+2+1 的无符号字符数组），然后将此缓冲区视为单个元素。

于 2012-10-23T10:35:13.303 回答
1

创建一个有效的哈希；首先确定要用于查找的数据。例如，如果您要搜索从某个 IP 地址发送的所有数据包，那么您只想使用“源 IP 地址”（并且您不想使用源 IP 地址和源端口，因为这意味着您必须进行 65536 次搜索才能找到从某个 IP 地址发送的所有数据包）。

下一步是确定最有效的哈希大小。这往往取决于数据量和 CPU 缓存的大小。如果散列大小太小（例如 8 位），那么您最终会得到每个散列的长条目列表（这会增加查找任何内容的时间）；如果散列大小太大（例如 24 位），那么在尝试查找散列条目列表时，您会经常出现缓存未命中。

请注意，您也可以有多个级别。例如，如果您要搜索来自特定端口和 IP 地址的数据包；然后您可以单独使用 IP 地址创建一个哈希表，用于查找第二个哈希表；然后使用该端口创建与第二个哈希表一起使用的不同哈希。

一旦你决定了你需要为哈希和哈希大小使用什么信息；下一步是确定如何以最小化冲突的方式计算哈希。此计算需要快速 - 您不希望尝试阻止少量开销的大量开销（并且使用像 MD5 这样复杂的东西将是一个坏主意）。通常，像“XOR 和移位”这样的简单方法既快速又有效。例如，对于一个 16 字节的 IP 地址和 16 位哈希，您可能只需要执行hash ^= (hash << 3) | next_pair_of_bytes;8 次。

最后，你想调整它。大多数情况下，您想调整散列大小并尝试一些不同的散列计算，看看它是否能提高性能。以上所有内容都依赖于对数据和缓存大小的假设，而这些假设在实践中可能是错误的。例如，也许大多数数据包都来自一个 IP 地址，而在哈希中使用 IP 地址是浪费时间；也许程序的其他部分正在消耗大量缓存，并且尝试将缓存未命中率降至最低是一个坏主意（并且更大的散列可能会提高性能）；也许没有你想象的那么多数据，你也没有遇到很多哈希冲突，减少哈希大小可以提高性能；等等

于 2012-10-23T11:14:02.417 回答