假设你有一个很大的数据集,非常非常大,以至于不能全部存入内存。这个数据集中有重复的数据,你想找出有多少重复的数据,但数据并没有排序,由于数据量太大所以排序是不切实际的。你如何来估计数据集中含有多少无重复的数据呢?这在许多应用中是很有用的,比如数据库中的计划查询:最好的查询计划不仅仅取决于总共有多少数据,它也取决于它含有多少无重复的数据。 在你继续读下去之前,我会引导你思考很多,因为今天我们要讨论的算法虽然很简单,但极具创意,它不是这么容易就能想出来的。 一个简单的朴素基数估计器 让我们从一个简单的例子开始吧。假定某人以下列方式来生成数据: 生成 n 个充分分散的随机数