如何从上亿条 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 的增加会变得非常小。