如何高效判断端口号集合是否存在交集

本文介绍在防火墙访问控制列表（acl）分析场景下，快速检测目标端口范围是否与已有服务端口范围存在交集的三种算法方案，并重点推荐基于区间排序与二分查找的最优实践。

在网络安全运维与自动化策略分析中，常需判断一组待检端口（如 {"5672", "15672-15674"}）是否与防火墙 ACL 中已配置的服务端口范围（如 {"20-22", "443", "8080-8088", "10000-65535"}）存在交集。由于端口表示形式混合了单值（443）与区间（20-22），直接暴力展开为完整整数集合（如 {20,21,22}）虽逻辑清晰，但在端口范围广（如 10000-65535 含 55536 个端口）时极易引发内存与性能瓶颈。因此，需设计不展开、低开销、可复用的区间交集判定方案。

✅ 推荐方案：区间归一化 + 有序范围二分查找（Approach 2）

该方案将所有端口统一为 [start, end] 形式（如 "443" → (443, 443)，"20-22" → (20, 22)），对 ACL 区间列表按 start 排序后构建 List，再对每个待查区间，利用二分查找快速定位潜在重叠候选，最后精确判断区间是否相交。

public record PortRange(int start, int end) {
    public boolean intersects(PortRange other) {
        return this.start <= other.end && other.start <= this.end;
    }
}

public class PortRangeChecker {
    private final List sortedAclRanges;

    public PortRangeChecker(String[] aclPortStrings) {
        this.sortedAclRanges = Arrays.stream(aclPortStrings)
                .map(PortRangeChecker::parseRange)
                .sorted(Comparator.comparingInt(PortRange::start))
                .collect(Collectors.toList());
    }

    private static PortRange parseRange(String s) {
        String[] parts = s.trim().split("-");
        int start = Integer.parseInt(parts[0]);
        int 
end = parts.length == 2 ? Integer.parseInt(parts[1]) : start;
        return new PortRange(Math.min(start, end), Math.max(start, end));
    }

    public boolean hasIntersection(String[] targetPortStrings) {
        for (String target : targetPortStrings) {
            PortRange targetRange = parseRange(target);
            // 二分查找首个 start <= targetRange.end 的区间（潜在重叠起点）
            int pos = binarySearchFirstStartLE(sortedAclRanges, targetRange.end);
            if (pos < 0) continue;
            // 向前/向后有限扫描（通常只需检查 1~2 个邻近区间）
            for (int i = Math.max(0, pos - 1); i < Math.min(sortedAclRanges.size(), pos + 2); i++) {
                if (sortedAclRanges.get(i).intersects(targetRange)) {
                    return true;
                }
            }
        }
        return false;
    }

    private static int binarySearchFirstStartLE(List list, int upperBound) {
        int left = 0, right = list.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid).start() <= upperBound) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left - 1; // 最右满足 start <= upperBound 的索引
    }
}

优势总结：

• 时间复杂度优： 预处理 ACL 一次为 O(n log n)；每次查询为 O(m log n)（n = ACL 区间数，m = 待查区间数），远优于暴力展开的 O(a + s) 内存与潜在 O(a × s) 比较；
• 内存友好： 仅存储区间端点，空间复杂度稳定为 O(n + m)；
• 工程友好： 支持 ACL 列表预构建、多轮复用，契合实际防火墙策略批量校验场景。

⚠️ 其他方案对比说明

• 方案 1（全量端口 Set）： 适用于极小 ACL（如 内存占用飙升至数万整数，且无法复用计算结果，不推荐用于生产环境。
• 方案 3（事件点扫描法）： 将所有区间的起止点合并排序并标记类型（+1 起始 / -1 结束），通过扫描计数判断覆盖。虽理论简洁，但实现稍繁，且每次查询均需重建合并序列，时间复杂度 O((n+m) log(n+m)) 略逊于方案 2，实用性较低。

✅ 实践建议

• 始终对 ACL 端口字符串做合法性校验与归一化（如自动交换 65535-10000 为 10000-65535）；
• 若 ACL 极大（n > 10⁴）且查询高频，可进一步升级为 TreeSet 并自定义比较器，或采用线段树（Segment Tree）优化最坏查询性能；
• 在日志或告警中明确输出首次命中交集的具体区间对（如 "15672-15674 overlaps with 10000-65535"），提升排障效率。

综上，区间归一化 + 有序列表 + 二分定位 + 局部扫描是平衡开发成本、运行效率与资源消耗的最佳路径，适用于绝大多数企业级防火墙策略分析系统。