用Bloom Filter的方式统计网络流量
作者从网站面临爬虫攻击和恶意访问的现实问题出发，想要高效统计每个IP的日访问量以识别机器人。传统的Map计数法可能消耗数百兆内存，而文章介绍了一种基于Bloom Filter思想的变体算法，可以在极低的内存占用（O(1)空间复杂度）下完成计数。 这个方案的核心是使用一个二维数组和多个独立的哈希函数。每次访问到来时，不是增加所有对应位置的计数器，而是只增加这m个计数器中值最小的那一个。这种方法巧妙地将Bloom Filter的“是否存在”判断，扩展为了“计数”的近似统计。当然，它继承了Bloom Filter可能存在的假阳性特点——可能误判某些低频IP为机器人，但可以通过调整数组大小和哈希函数数量来控制误差率。 文章还由此类比了《编程之美》中一个经典的微软面试题，并进一步提出了扩展问题：如果要统计的不是访问次数，而是IP的入/出流量，该如何设计算法？这为读者提供了更广阔的思考空间。