如何高效判断指定端口集合与防火墙ACL端口集合是否存在交集？

问题背景 #

防火墙访问控制列表（ACL）的服务端口存在两种格式：

• 单个端口：如22、443
• 端口范围：如10000-65535
  需求是判断指定的端口/端口范围，是否与ACL中的端口集合存在交集。

示例场景 #

ACL端口数组：String[] servicePorts = {"20-22","443","8080-8088","10000-65535"}
待判断集合：{"5672","15672-15674"}
需验证两者是否存在交集。

现有方案分析 #

方案1：基于Set的全量存储判断 #

把所有ACL端口展开存入Set<Integer>，用Set的contains方法直接判断。

• 优点：实现简单，依赖现有集合API即可完成
• 缺点：遇到大端口范围（比如10000-65535）时，要存储5万+元素，内存占用高，初始化和查询性能极差，完全不适合大场景。

方案2：统一范围格式后逐一比较 #

先把所有端口（单个/范围）转成「起始-结束」格式：

• 转换后的ACL集合：{"20-22","443-443","8080-8088","10000-65535"}
• 待判断集合：{"5672-5672","15672-15674"}
  遍历待判断的每个范围，和ACL里的每个范围做区间交集判断，核心逻辑：两个区间[s1,e1]和[s2,e2]满足s1 <= e2 && s2 <= e1则存在交集。
• 优点：内存占用极低，仅存储每个范围的起止数值，无需展开所有端口
• 缺点：最坏情况需遍历所有ACL和待判断范围，时间复杂度为O(M*N)（M为ACL范围数，N为待判断范围数），范围数量多的时候性能一般。

更高效的优化方案 #

方案3：ACL范围排序+二分查找 #

1. 先将所有ACL端口转换为[起始端口, 结束端口]的数值对，按起始端口升序排序；若起始端口相同，按结束端口升序排序。
2. 对每个待判断范围[myS, myE]，用二分查找快速定位可能存在交集的ACL范围：
   • 先筛选出所有起始端口 <= myE的ACL范围（起始端口大于myE的肯定无交集）
   • 在候选范围内，检查是否存在ACL范围的结束端口 >= myS，满足s <= myE && e >= myS即说明有交集

• 优点：时间复杂度降至O(M log M + N log M)，M为ACL范围数，N为待判断范围数，大场景下性能提升明显
• 额外优化：排序前可合并重叠/连续的ACL范围，比如20-22和21-25可合并为20-25，减少后续遍历的范围数量。

二进制位图方案（你提到的思路落地） #

用一个65536位的位图（比如Java的BitSet），每一位对应一个端口，置1表示该端口在ACL中：

1. 初始化位图，遍历ACL的每个端口/范围：单个端口n就将第n位置1；范围a-b就将a到b的所有位置1
2. 待判断的单个端口直接查询对应位是否为1；待判断范围则检查该区间内是否至少有一个位为1

• 优点：查询速度极快，单个端口查询为O(1)，范围查询也有底层优化
• 缺点：内存固定占用8192字节（65536位），若需处理大量不同的ACL集合，内存会累积；初始化大范围时，比方案2的范围存储速度慢一些。

方案选型建议 #

• 若ACL范围数量少（几十个以内），直接用方案2，实现简单且性能足够
• 若ACL范围数量多或查询频繁，优先选择方案3，兼顾内存和性能
• 若查询频率极高且内存资源充足，可考虑二进制位图方案，查询效率最优

内容的提问来源于stack exchange，提问作者Eric