口述演算法 13: 如何從上億條 IP 地址中去除重複的地址？

誤判率怎麼計算

前言

Hello，朋友們好，歡迎來到我的口述算法系列，今天的主題是大規模資料去重。

思路一

首先，這裡的 IP 地址就是類似 192。168。1。1 這種具體的 IP 地址，而並不是 192。168。1。1/16 這種帶掩碼的表示方法。

一個 IP 地址可以用 4 個位元組表示，對應一個 int 型別的整數，這個數的最大值就是 2 的 32 次方，大約是 512 Mbyte。從而，定義一個長度為 512M 的 bitset。 如果出現某個 IP 地址就把 bitset 對應的位置設為 1。

思路二

如果 IP 地址換成 IPv6 呢？每個 IPv6 地址需要用 64 bit 表示，那麼這個 bitset 需要多大呢？2 的 64 次方，約 2 Ebyte，這是個天文數字。所以，如何在有限空間的 bitset 上實現大規模資料的去重呢？答案就是布隆過濾器，在我之前的文章中有詳細介紹過

C++ 實現布隆過濾器 - 從上億條資料中查詢某個記錄是否存在

。

大規模資料集中的每個元素就是 key，透過多個雜湊函式計算出多個索引值，然後將 bitset 對應位置置為 1。 同理，在查詢的時候，如果每個雜湊函式求出來的索引值對應的 bitset 中都為 1，那麼這個 key 就存在。

但是，布隆過濾器有個小小的缺點，它有一定的誤判機率，假設雜湊函式的個數是 k，誤判率大概是 0。5 的 k 次方，所以誤判率隨著 k 的增加會變得非常小。