1. 问题描述

对于海量数据，要求判断一个数据是否已经存在。这个数据很有可能是字符串，例如 URL。

2. HashSet

最直观的方法是使用 HashSet 存储，那么就能以 O(1) 的时间复杂度判断一个数据是否已经存在。

考虑到数据是海量的，那么就需要使用拆分的方式将数据拆分到多台机器上，分别在每台机器上使用 HashSet 存储。我们需要使得相同的数据拆分到相同的机器上，可以使用哈希取模的拆分方式进行实现。

3. BitSet

如果海量数据是整数，并且范围不大时，就可以使用 BitSet 存储。通过构建一定大小的比特数组，并且让每个整数都映射到这个比特数组上，就可以很容易地知道某个整数是否已经存在。因为比特数组比整型数组小的多，所以通常情况下单机就能处理海量数据。

以下是一个 BitSet 的实现，当然在实际开发中可以直接使用语言内置的实现。

使用 BitSet 还可以很容易地解决一个整数出现次数的问题，例如使用两个比特数组就可以存储 0~3 的信息。其实判重问题也可以简单看成一个数据出现的次数是否为 1，因此一个比特数组就够了。

4. 布隆过滤器

布隆过滤器能够以极小的空间开销解决海量数据判重问题，但是会有一定的误判概率。它主要用在网页黑名单系统、垃圾邮件过滤系统、爬虫的网址判重系统。

布隆过滤器也是使用 BitSet 存储数据，但是它进行了一定的改进，从而解除了 BitSet 要求数据的范围不大的限制。在存储时，它要求数据先经过 k 个哈希函得到 k 个位置，并将 BitSet 中对应位置设置为 1。在查找时，也需要先经过 k 个哈希函数得到 k 个位置，如果所有位置上都为 1，那么表示这个数据存在。

由于哈希函数的特点，两个不同的数通过哈希函数得到的值可能相同。如果两个数通过 k 个哈希函数得到的值都相同，那么使用布隆过滤器会将这两个数判为相同。

可以知道，令 k 和 m 都大一些会使得误判率降低，但是这会带来更高的时间和空间开销。

布隆过滤器会误判，也就是将一个不存在的数判断为已经存在，这会造成一定的问题。例如在垃圾邮件过滤系统中，会将一个邮件误判为垃圾邮件，那么就收不到这个邮件。可以使用白名单的方式进行补救。

5. Trie

Trie 树又叫又叫字典树、前缀树、单词查找树，它是一颗多叉查找树。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。

如果海量数据是字符串数据，那么就可以用很小的空间开销构建一颗 Trie 树，空间开销和树高有关。

Leetcode : Implement Trie (Prefix Tree)

参考资料

• Bloom Filters: Is element x in set S?

个人博客

https://github.com/CyC2018/CS-Notes

开源在 Github 上的个人博客，总结了技术面试必备的基础知识，在 Github 上关注数排在二十名左右。