java - 检查 IP 地址是否在多个可能的子网中

Question

我正在解析 Apache 日志并想检查 IP 地址是否属于约 300 个可能的子网列表 ( https://github.com/client9/ipcat)。

• Internet 流量有很多不同的 IP(我不知道它们属于哪个子网)。
• 我正在使用 Apache Commons SubnetUtils 包来存储子网。
• 将 300 个子网中所有可能的 IP 存储在 HashMap 中会占用太多内存。
• 遍历每个 IP 的每个 SubnetUtil(即使使用之前查找的 HashMap 缓存)非常慢。

还有什么我可以在这里做的吗？

Answer 1

您可以构建一个带有子网的树结构 - 它可以一点一点地构建。这会将检查次数从 300 次减少到最多 32 次(假设 IPv4)，但在大多数情况下要少得多。 (因为它要么在几位之后不匹配，要么在子网掩码的平均长度上匹配)

这是执行此操作的简单二叉树实现。您可能想用一些函数来装饰它，以更常见的 "a.b.c.d/e" 格式解析子网。

public class SubnetTree {
    private SubnetTree one, zero;
    private boolean terminating;

    public void addSubnet(int net, int bits) {
        if (terminating) {
            // If this node is already terminating, then no need to add
            // subnets that are more specific
            return;
        }
        if (bits > 0) {
            boolean bit = ((net >>> 31) & 1) == 1;
            if (bit) {
                if (one == null) {
                    one = new SubnetTree();
                }
                one.addSubnet(net << 1, bits - 1);
            } else {
                if (zero == null) {
                    zero = new SubnetTree();
                }
                zero.addSubnet(net << 1, bits - 1);
            }
        } else {
            terminating = true;
        }
    }

    public boolean isInRange(int address) {
        if (terminating) {
            return true;
        }
        boolean bit = ((address >>> 31) & 1) == 1;
        if (bit) {
            if (one == null) {
                return false;
            } else {
                return one.isInRange(address << 1);
            }
        } else {
            if (zero == null) {
                return false;
            } else {
                return zero.isInRange(address << 1);
            }
        }
    }
}

此代码的一个非常简单的测试:

public static void main(String[] args) {
    SubnetTree tree = new SubnetTree();
    tree.add(Integer.parseUnsignedInt("01100110000000000000000000000000", 2), 8);
    System.out.println("true: " + tree.isInRange(Integer.parseUnsignedInt("01100110000000000000100010000101", 2)));
    System.out.println("false: " + tree.isInRange(Integer.parseUnsignedInt("01101110000000000000100010000101", 2)));

    tree.add(Integer.parseUnsignedInt("01001110000000000000000000000000", 2), 6);
    System.out.println("true: " + tree.isInRange(Integer.parseUnsignedInt("01100110000000000000100010000101", 2)));
    System.out.println("false: " + tree.isInRange(Integer.parseUnsignedInt("01101110000000000000100010000101", 2)));
    System.out.println("true: " + tree.isInRange(Integer.parseUnsignedInt("01001110100000000000000000000000", 2)));
    System.out.println("true: " + tree.isInRange(Integer.parseUnsignedInt("01001100100000000000000000111111", 2)));
}