假设有一堵防火墙，系统管理员已经封锁了许多子网，甚至可能封锁了某个特定国家的所有子网。
例如：
192.168.2.0 / 255.255.255.0
223.201.0.0 / 255.255.0.0
223.202.0.0 / 255.254.0.0
223.208.0.0 / 255.252.0.0
....
为了判断一个IP地址是否被阻止，防火墙可能会使用以下算法。
func blocked(ip)
foreach subnet in blocked_subnets
if in_subnet(subnet, ip)
return true
return false
但是，该算法需要运行太长的时间，时间复杂度为O(n)。如果路由表包含太多条目，则网络几乎将不可用。
有没有更有效的方法将IP地址与大量路由条目匹配？我猜想它基于某种树/图（Trie？）。我已经阅读了一些关于最长前缀匹配和Trie的内容，但并没有理解其中的要点。
你所需要的只是一个四层的 trie。每个非叶子节点包含高达256个子节点的数组。每个节点还包含一个子网掩码。所以，以你的例子为例：
192.168.2.0 / 255.255.255.0
223.201.0.0 / 255.255.0.0
223.202.0.0 / 255.254.0.0
223.208.0.0 / 255.252.0.0
您的树将类似于下面的样子。每个节点的两个数字分别是IP段和子网掩码。
root
/ \
192,255 223,255
| -------------------------
168,255 | | |
| 201,255 202,255 208,255
2,255
获取 IP 地址后，需要将其分段。首先在根级别上搜索第一个段。为了提高速度，你可能会想要在根级别使用数组进行直接查找。
假设 IP 地址的第一个段是 223。你可以从 root[223] 中获取节点，然后你就只处理一个子树了。除非数据非常密集，否则在其他级别上你可能不想要完整的数组，而是需要一些字典之类的东西来处理后续层级。如果下一个段是 201，则在 223 节点的字典中查找 201，这样你的候选列表中可能只有 64K 个项目（即所有以 223、201 开头的 IP 地址）。你可以在其他两个级别上执行相同的操作。结果是你只需进行四次查找就能解析一个 IP 地址：一次在数组中的查找和三次在字典中的查找。
这种结构也很容易维护。插入新地址或范围最多需要进行四次查找和添加。删除也是如此。更新可以就地完成，无需重建整个树。只需确保在更新时不要尝试读取，并且不要尝试进行并发更新。但任意数量的读者可以同时访问该项。
Key = (subnet_no,ip)You can compare them similar to above and would get O(log(S)) where S is total number of ip entries in all subnets.
请注意，IP地址基本上是一个32位数字。
您可以将每个子网规范化为其正常形式，并将所有正常形式存储在哈希表中。
在运行时，将给定的地址规范化（易于执行），并检查哈希表是否包含此条目 - 如果是，则阻止。否则-允许。
例如，假设您想要阻止子网5.*.*.*，这实际上是具有前导位00000101的网络。因此，将地址5.0.0.0或00000101-00000000-00000000-00000000添加到哈希表中。
一旦到达特定地址-例如5.1.2.3，将其规范化回5.0.0.0，并检查它是否在表中。
使用哈希表，平均查询时间为O(1)。
255.254.0.0放入您的表中，一旦出现特定的IP地址（例如255.254.5.6）- 从最不重要的16位中删除它，然后您将获得255.254.0.0 - 您可以在哈希表中进行检查。请注意，使用IP结构，您始终知道需要剥离哪些位。 - amit
223.208.0.0 / 255.252.0.0。 - shawn