计数器大小和计数器溢出
柜台尺寸
我们必须选择足够大的计数器以避免溢出。
泊松近似建议大小为4位/计数器。
实现k=(ln2)m/n个计数器的平均负载为ln2。
概率的计数器具有最小负载16:≈e-ln2(LN2)16/16!≈6.78E-17
我们考虑4位/计数器进行比较。
计数器溢出
当计数器确实溢出时,它可能达到最大值。
仅当计数器原本应保持为非零时最终降至0时,这种情况以后才可能导致假阴性。
这种情况的预期时间非常长,但是对于任何不允许误报的应用程序,我们都需要牢记这一点。
为了避免计数器溢出,其大小必须足够大。发现每个计数器4位就足够了。