概率数据结构：用极低内存实现近似计数与集合判断

为什么需要概率数据结构在处理海量数据流或内存受限的场景下，精确数据结构的代价往往高得难以承受。例如，一个存储1亿个64位整数的Python列表需要约3.8 GiB RAM（每个整数作为独立对象开销巨大），而改用array('l')后仅需约760 MiB。即便如此，当数据量达到十亿级别时，内存仍会迅速耗尽。一种更极端的思路是用精度换取内存：在可接受的误差范围内，使用概率数据结构将内存消耗降低几个数量级。这种思想类似于JPEG图像压缩——损失一些信息（且不可逆），但获得巨大的压缩率。《High Performance Python》第12章中提到了两类典型场景：近似计数：统计大规模事件的发生次数，如页面浏览量、网络包计数。近似集合成员判断：快速判断一个元素是否出现过，如反垃圾邮件系统的URL黑名单。下面逐一介绍几种经典的概率数据结构，并展示它们如何在极低内存下完成近似任务。Morris计数器：用指数与概率近似计数传统计数器（如64位整数）最大能计数到2^64-1，但需要8字节内存。Morris计数器（Robert Morris，1978年）的神奇之处在于：它仅用1字节（8位）即可近似计数到10^76。其核心思想是：不是每次增加1，而是以指数递减的概率递增。计数器存储的是log(n)的近似值，读取时需要指数变换还原。具