我试图理解这个草图，但无法理解。如果我错了，请纠正我，但基本上，假设我有一个文本数据..单词..我有一个散列函数..它需要一个单词并创建一个整数散列，然后我将该散列转换为二进制位向量？对.. 然后我跟踪我从左边看到的第一个 1.. 那个 1 的位置（比如说，k）......这个集合的基数是 2^k？
http://ravi-bhide.blogspot.com/2011/04/flajolet-martin-algorithm.html
但是……说我只有一个字。并且它的散列函数使得它生成的散列是2 ^ 5，那么我猜有5个（？？）尾随0？所以它会预测 2^5 (??) 基数？这听起来不对？我错过了什么
对于单个单词，R 的分布是 p = 1/2 的几何分布，其标准差为 sqrt(2) ≈ 1.41。
因此，对于哈希以 100000 b结尾的单词，该算法确实会产生 2 5 /0.77351 = 41.37。但这种概率只有 1/64，这与 R 的标准差接近 1 的说法是一致的。
真正重要的是要记住，Flajolet Martin 算法旨在从一组 N 个元素中计算不同的元素（比如说 M 个不同的元素），而 M 预计会非常大。
如果 N 或 M 小到足以让我们将所有不同的元素存储在内存中，那么使用该算法是没有意义的。
在 N 和 M 真的很大的情况下，估计接近 2^k 的概率其实是非常合理的。
对此有解释：http: //infolab.stanford.edu/~ullman/mmds/ch4.pdf（第143页）
http://ravi-bhide.blogspot.com/2011/04/flajolet-martin-algorithm.html
我们有一个很好的随机散列函数，它作用于字符串并生成整数，我们能对生成的整数说些什么呢？由于它们本身是随机的，我们期望：
1/2 of them to have their binary representation end in 0(i.e. divisible by 2),
1/4 of them to have their binary representation end in 00 (i.e. divisible by 4)
1/8 of them to have their binary representation end in 000 (i.e. divisible by 8)
解决问题，如果哈希函数生成一个以 0^m 位结尾的整数..直观地说，唯一字符串的数量约为 2^m。