这是一个老问题了,公司的产品中经常会需要检测新添加的IP是否已经存在,就需要有判断重复IP的算法,这里只是一个算法思想的搬运。
问题:给定一个IP或者一个网段,如何判断该IP或者该网段已经存在于数据库?
稍微列一下关键步骤的代码
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修改:
之前写的内容逻辑上有些问题,稍微修改了一下。