這是一個老問題了，公司的產品中經常會需要檢測新添加的 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 修改：
之前寫的內容邏輯上有些問題，稍微修改了一下。