阅读： 7
实际业务中，高频率往往会遇到以下业务问题：
- 判断两个IP网段是否重叠 / 多个IP网段数组是否重叠
- 对用户进行相应的提醒 / 启动相应的策略
例如，客户有两台设备，在配置时填入错误的冲突IP网段时提醒客户，或收到一个攻击源IP信息时，需要判断源IP是否命中某个IP网段。
一般的业务流程是这样走的：
- 获取比较的IP网段集合
- 选出一个网段，与其他网段做对比
- 将该IP网段移除集合
- 重复第二步直到有网段重叠或没有网段重叠
这里忽略第二步，因为通常各团队底层公共库都已在第二步加入对应的算法，主要操作一般为：
- 获取IP网段的起始IP地址和结束IP地址，并解析为ip1_start, ip1_end, ip2_start, ip2_end
- 比较这四个数，判断是否重叠
在比较两个IP网段上述算法时，性能一般已到极限。但在实际业务需求中，往往会遇到客户一次性输入成百上千IP网段的情况（由EXCEL导入或外部系统导入等），原有业务流程效率就不再被接受。绿盟科技ADBOS团队对应的优化算法如下：
众所周知，
一个IP地址可以被解析为一个int类型的数字，
一个IP范围可以被解析为两个int类型的数字，
……
则可以想象，若干IP网段最终会被映射到一个无限长的数轴之上，数轴如下图：
重叠IP网段如下图：
如何通过这个数轴表现出来的特征，判断是否出现了重叠IP网段，设计算法如下：
- 所有IP网段，均初始化在值为0的数轴上，起始位置标为1，结束位置标为-1
- 如果是IP地址，则变换为一个小范围进行初始化，如IP地址映射的整数是10000，则变换为9999.9和10000.1
- 初始化过程中如果有相同的起始位置/结束位置，则所在位置再+1/-1
- 从左到右对数轴求和
- 如果当前坐标值大于1或小于-1，说明有重叠情况
- 如果当前坐标值为-1，但此时求和不为0，说明有形如1、1、-1的情况，有重叠
- 如果当前坐标值是1，但此时的值大于1，也说明有形如1、1、-1的情况，有重叠
- 如果发生重叠判断，则记录当前坐标，和当前坐标的前一个坐标
- 如果需要返回重叠IP网段，则此处可以根据坐标获取对应的IP网段，去重放入返回集合即可。
简单来说：
- 从左到右依次求和
- 读到-1，和值为0，说明正常，除此以外的任何情况，都说明出现了重叠
- 读到-1，和值为0，说明结束了一个冲突段
前后两种算法的伪代码如下：
旧代码：
新代码：
前后两种算法的效率对比如下：
重叠IP网段：数组中的最后一个 / 数组中全部都是重叠网段
是否提前中断：无
则均为两种算法的最坏情况下的最长耗时（即遍历所有IP网段的耗时）。
性能测试结果：
| 输入IP网段数 | 旧算法/耗时 | 新算法/耗时 |
| 400 | 30s | 0.0035 s |
| 10000 | \ | 0.0686 s |
| 100000 | \ | 1.0340 s |
| 200000 | \ | 1.5224 s |
1、这里数轴没有用数组的形式构建，因为IP解析出的int值都很大，采用了字典形式来节约内存空间，通过对字典排序变相实现数轴。
2、根据不同的业务逻辑，发现重叠IP网段后，采取不同手段也会影响到算法的性能，例如：
- 发现重叠网段立刻不再判断，不影响性能
- 发现重叠网段后进行数据库请求，则实际耗时取决于重叠网段数 * 每次数据库请求的时间
3、针对2，需要在特定业务场景下进行优化，如对重叠网段子集合不再内存中频繁去重，一次遍历进行输入，一次遍历进行去重，或借助redis集合，实现遍历一遍，一次去重。
版权声明
本站“技术博客”所有内容的版权持有者为绿盟科技集团股份有限公司（“绿盟科技”）。作为分享技术资讯的平台，绿盟科技期待与广大用户互动交流，并欢迎在标明出处（绿盟科技-技术博客）及网址的情形下，全文转发。
上述情形之外的任何使用形式，均需提前向绿盟科技（010-68438880-5462）申请版权授权。如擅自使用，绿盟科技保留追责权利。同时，如因擅自使用博客内容引发法律纠纷，由使用者自行承担全部法律责任，与绿盟科技无关。