概率数据结构

布隆过滤器深度实战:从位图、误判率推导到 Counting/Scalable/Cuckoo 变体与防缓存穿透的工程全解

在精确集合成员判定(HashSet / 红黑树 / 哈希表)的成本随数据规模线性膨胀之后,工程界早已接受一个现实:**大多数"是否存在"的查询,并不需要 100% 精确**。当你可以容忍一个极小且可量化的假阳性(false positive)概率,却坚决不允许假阴性(false negative)时,有一类被称为"概率数据结构"的工具能把内存占用从 O(n·w) 压到 O(n·c)(c 为常数比特…