本文对比分析了三种判断防火墙访问控制列表（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<>();
for (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 是平衡开发效率、运行性能与长期可维护性的最优解。它摒弃了“以空间换时间”的粗暴思路，转而利用区间数学性质与经典搜索算法，在真实防火墙策略分析场景中兼具鲁棒性与可扩展性。
