android - 快速比较 IP 地址的最佳方法

Question

我正在解析两个包含 IP 地址的 CSV 文件。第一个是源 CSV，第二个是“黑名单”。

由于源文件的大小，我正在尝试优化查找与黑名单匹配的 IP 地址的速度。

编辑: 黑名单由 IP 地址“ block ”组成。这意味着黑名单中的每条记录都有两个 IP 地址:一个 Start block (例如 216.254.128.0)和一个 End block 。 (例如 216.254.223.255)

这意味着直接查找等将不起作用。

我想知道解决这个问题的最佳方法是什么。蛮力方法是:

String[] parts = sourceIP.split("\\."); // String array, each element is text between dots

int hi = 255;
int lo = 0;

int mid = (hi - lo) / 2 ;

if (Integer.valueOf(parts[0]) > mid) {
    mid = lo;
}

然后我可以对每个 部分 重复此操作以确定 IP 地址是否在黑名单中。

这看起来非常激进，并且有 4k+ 记录，这可能需要非常非常长的时间。

决定每个部分可能需要 10 次以上的迭代，然后必须重复此过程以检查黑名单中 IP block 的“高”部分。这是每条记录 80 多次迭代。

我希望在这里得到一些输入，以了解比较 IP 地址的最佳方法。

你有什么想法？

是否可以通过序列化 INetAddress 使用快速按位掩码来快速比较值？

文件结构说明:

源IP文件:

包含来自数据库的记录列表。 (约 4k)。每条记录都包含姓名、地址、电子邮件和 IP 地址。

黑名单:

包含 4.2k 条记录。每条记录都是一个 IP 地址“ block ”。这由两个 IP 地址组成。 1. 开始和 2. 结束。

如果源列表中的记录有在黑名单中找到的 IP 地址，我需要保存该记录并将其添加到新文件中。

Answer 1

我假设您说的是 xxx.xxx.xxx.xxx 形式的 IPV4 地址。

您可以轻松地将 IP 地址转换为整数。每个段(即 xxx)为 8 位(即一个字节)。所以它们中的四个加起来就是一个 32 位整数。因此，给定一个像“192.168.100.12”这样的 IP 地址，您可以将它分成四个部分，将每个部分解析为一个字节并创建一个整数。比方说，您创建了一个字节数组的段:

ipBytes[0] = 192;
ipBytes[1] = 168;
ipBytes[2] = 100;
ipBytes[3] = 12;

你可以把它变成一个整数:

int ipAddress = ipBytes[0];
ipAddress = (ipAddress << 8) | ipBytes[1];
ipAddress = (ipAddress << 8) | ipBytes[2];
ipAddress = (ipAddress << 8) | ipBytes[3];

有更有效的方法可以做到这一点，但您明白了。您的语言的运行时库可能已经有一些东西可以解析 IP 地址并为您提供字节以使其成为整数。

您有一组 IP 地址范围，您希望根据这些范围检查您的源地址。将每个范围加载到这样的结构中:

class IPRange
{
    public int startIp;
    public int stopIp;
}

并将它们存储在数组或列表中。然后按起始 IP 地址对列表进行排序。

对于每个源 IP 地址，将其转换为整数并对列表进行二进制搜索，搜索起始 IP 地址。可能找不到(可能不会)找到源地址本身，但是当二分查找终止时，mid 值将保存起始 IP 地址小于或等于源地址。然后，您只需根据该项目的结束 IP 地址检查源地址，看看它是否在范围内。

二分查找复杂度为 O(log n)。如果您正在搜索包含 4,300 个范围的列表，则最多需要 13 个探测才能在数组中找到一个地址。这应该足够快了，即使进行 4,000 次不同的搜索也是如此。您只是在谈论范围阵列的总共 50,000 个探针的数量级。

一些注意事项:

首先，正如我上面所说，我假设您在谈论 IPV4 地址。如果您谈论的是 IPV6 地址，相同的概念仍然适用，但您需要一个 64 位整数。我对 IPv6 了解不够，无法说明如何将地址转换为 64 位整数。可能您应该依靠运行时库来获取地址字节。

第二:我假设范围不重叠。也就是说，您不会有类似的东西:

start range    end range
192.168.1.1    192.168.2.255
192.168.2.1    192.168.3.255

如果您有，那么 IP 地址可能属于这些范围中的任何一个。您可能会构建重叠范围，从而使地址从裂缝中掉下来。如果范围重叠，问题就会变得有点复杂。