高效判断端口范围集合是否相交：三种算法对比与推荐实现

本文对比分析了三种判断防火墙访问控制列表（acl）端口范围与目标端口范围是否存在交集的算法，重点评估其时间/空间复杂度与工程适用性，最终推荐基于有序区间二分查找的方案，并提供可直接使用的 java 实现。

在网络安全运维与自动化策略分析中，常需快速判定一组目标端口（如 {"5672", "15672-15674"}）是否与防火墙 ACL 中定义的服务端口范围（如 {"20-22", "443", "8080-8088", "10000-65535"}）存在交集。由于端口范围可能覆盖 1–65535 的整数空间，暴力展开为单点集合（Approach 1）虽编码简单，但内存与时间开销不可接受（最坏 O(65535) 级别）。因此，必须采用基于区间表示与高效区间重叠检测的算法。

✅ 推荐方案：有序区间 + 二分查找（Approach 2）

该方案将 ACL 端口统一归一化为 [start, end] 区间（如 "443" → [443, 443]，"20-22" → [20, 22]），构建按 start 排序的不可变区间列表；对每个待查目标区间 [tStart, tEnd]，通过二分查找定位所有可能重叠的候选 ACL 区间（即满足 acl[i].end >= tStart && acl[i].start

其核心优势在于：

• 时间复杂度优：预处理 ACL 区间排序仅需 O(n log n)；每次查询 m 个目标区间仅需 O(m log n)；
• 空间极省：仅存储 n 个区间（通常 n ≪ 65535），内存占用恒定；
• 工程友好：逻辑清晰、易于测试、支持复用（ACL 列表构建一次，多次查询）。

以下是完整 Java 实现（含解析、标准化与交集检测）：

import java.util.*;

public class PortRangeIntersector {
    // 内部区间类（不可变）
    public static final class Range implements Comparable {
        final int start, end;
        Range(int s, int e) {
            this.start = Math.min(s, e);
            this.end = Math.max(s, e);
        }
        @Override
        public int compareTo(Range o) { return Integer.compare(this.start, o.start); }
        // 检查 [this.start, this.end] 与 [otherStart, otherEnd] 是否有交集
        boolean intersects(int otherStart, int otherEnd) {
            return this.start <= otherEnd && otherStart <= this.end;
        }
    }

    // 解析字符串端口（支持 "80" 或 "1000-2000"）
    public static Range parsePort(String portStr) {
        if (portStr == null || portStr.trim().isEmpty())
            throw new IllegalArgumentException("Invalid port string: " + portStr);
        String[] parts = portStr.trim().split("-", 2);
        int start = Integer.parseInt(parts[0]);
        int end = parts.length == 2 ? Integer.parseInt(parts[1]) : start;
        return new Range(start, end);
    }

    // 构建已排序的 ACL 区间列表（建议缓存复用）
    public static List buildSortedAclRanges(String[] aclPorts) {
        List ranges = new ArrayList<>();
        fo
r (String p : aclPorts) {
            ranges.add(parsePort(p));
        }
        ranges.sort(Comparator.naturalOrder());
        return Collections.unmodifiableList(ranges);
    }

    // 判断目标端口集合（字符串数组）是否与 ACL 存在任意交集
    public static boolean hasIntersection(List sortedAcl, String[] targetPorts) {
        for (String t : targetPorts) {
            Range target = parsePort(t);
            // 二分查找：首个 start <= target.end 的区间（右边界约束）
            int lo = 0, hi = sortedAcl.size();
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (sortedAcl.get(mid).start <= target.end) lo = mid + 1;
                else hi = mid;
            }
            // 检查 [0, lo) 范围内所有可能重叠的区间（因 start ≤ target.end 是必要条件）
            for (int i = 0; i < lo && i < sortedAcl.size(); i++) {
                if (sortedAcl.get(i).intersects(target.start, target.end)) {
                    return true;
                }
            }
        }
        return false;
    }

    // 使用示例
    public static void main(String[] args) {
        String[] acl = {"20-22", "443", "8080-8088", "10000-65535"};
        String[] targets1 = {"5672", "15672-15674"}; // 无交集 → false
        String[] targets2 = {"21", "443-444"};       // 有交集 → true

        List aclRanges = buildSortedAclRanges(acl);
        System.out.println(hasIntersection(aclRanges, targets1)); // false
        System.out.println(hasIntersection(aclRanges, targets2)); // true
    }
}

⚠️ 注意事项与优化建议

• 输入校验：生产环境需增强 parsePort 对非法格式（如负数、非数字、end
• 性能再优化：若 ACL 规则极多（n > 10⁴）且查询高频，可改用 TreeSet 替代 ArrayList，利用 headSet() / tailSet() 快速截取候选区间；
• 扩展性：本方案天然支持 IPv4/IPv6 地址段、时间窗口等任意一维连续区间交集检测，只需替换 Range 的类型与比较逻辑；
• 避免误区：不要试图用位运算（如 bitmap）压缩端口——65536 位虽仅 8KB，但动态范围合并、区间查询仍需遍历，且丧失语义清晰性。

综上，Approach 2 是平衡开发效率、运行性能与长期可维护性的最优解。它摒弃了“以空间换时间”的粗暴思路，转而利用区间数学性质与经典搜索算法，在真实防火墙策略分析场景中兼具鲁棒性与可扩展性。