这是一个老问题了，公司的产品中经常会需要检测新添加的 IP 是否已经存在，就需要有判断重复 IP 的算法，这里只是一个算法思想的搬运。
问题：给定一个 IP 或者一个网段，如何判断该 IP 或者该网段已经存在于数据库？
- 最简单暴力的算法，可以将所有网段都列出来，转换为单 IP，然后再逐一比对。这个方案就是最普通的方法，不做赘述。优点是简单易懂，缺点是比较耗费资源。
- 稍微优化一下，每个 IP 都可以当作一个数值（二进制转为十进制即可），线段处只用记录起始和结束的两个数值，然后对需要判断重复的 IP 的进行数值的比对，每个线段是一组，逐一比较即可。优点：相对于方案 1 优化存储资源 O (n)，缺点：存在多次遍历与比较 T (n)。
- 再优化一下，如果我们对于一个段，只记录开头和起始两个点，将所有的网段放在同一条线段上，开头的点记为 1，结束的点记为 - 1，从这条线段从头往后开始相加，每次取前两个值，
- 对于所有没有重叠的网段，和为 0。
- 对于出现重叠的网段，和不为 0
稍微列一下关键步骤的代码
def get_first_last_ip(ip_cidr:str) -> list:
try:
ip, cidr = ip_cidr.split('/')
octets = ip.split('.')
subnet_bits = int(cidr)
# 将IP地址转换为32位二进制字符串
ip_binary = ''.join([bin(int(octet))[2:].zfill(8) for octet in octets])
# 根据掩码位数计算网络地址和广播地址的二进制字符串
network_binary = ip_binary[:subnet_bits] + '0' * (32 - subnet_bits)
broadcast_binary = ip_binary[:subnet_bits] + '1' * (32 - subnet_bits)
# 将二进制字符串转换回IP地址形式
start_ip = '.'.join([str(int(network_binary[i:i+8], 2)) for i in range(0, 32, 8)])
end_ip = '.'.join([str(int(broadcast_binary[i:i+8], 2)) for i in range(0, 32, 8)])
return [start_ip, end_ip]
except ValueError:
# logging.error("Invalid IP format")
return [None, None]
def check_ip_cover(ip:str) -> bool:
dic = build_ip_dic()
try:
if check_ip(ip) and valid_ip_netmask(ip):
[first_ip, last_ip] = get_first_last_ip(ip)
first_ip_num = ip_2_int(first_ip)
last_ip_num = ip_2_int(last_ip)
if first_ip_num not in dic:
dic[first_ip_num] = 1
else:
logging.info("IP {} is repeated.".format(first_ip))
return False
if last_ip_num not in dic:
dic[last_ip_num] = -1
else:
logging.info("IP {} is repeated.".format(last_ip))
return False
res = 0
## 排序字典
sorted_dic = sorted(dic.keys())
## 每次从字典中取两个值进行运算
## 如果出现和不为0的情况就退出
ip_key_iter = iter(sorted_dic.keys())
while True:
try:
ip_1 = next(ip_key_iter)
ip_2 = next(ip_key_iter)
value_1 = sorted_dic[ip_1]
value_2 = sorted_dic[ip_2]
if value_1 + value_2 != 0:
return False
except StopIteration:
if ip_1:
return False
return True
except Exception as e:
logging.error("Some wrong in here: {}".format(e))
这个算法挺精妙的，只用看开始和结束的 IP，就能对大量的 IP 进行判重校验。
7/13 修改：
之前写的内容逻辑上有些问题，稍微修改了一下。