前言
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 的增加會變得非常小。
