在处理大数据集时，尤其是涉及到内存问题时，执行基本任务如计数不同元素、成员检查、过滤重复元素、查找最小值、最大值、前n个元素，或进行集合操作如并集、交集、相似性等，可能会面临挑战。概率数据结构在这些情况下非常有用，因为它们显著减少了内存需求，同时仍然提供了可接受的准确性。此外，由于查找（和添加）依赖于多个独立的哈希函数，可以实现并行化，从而提高了时间效率。
广泛使用如布隆过滤器（Bloom filters）、MinHash、Count-min sketch、HyperLogLog等结构来解决各种问题。下面是一个相对简单的示例。
为客户管理移动推送通知，需要防范的一个问题是，对于同一活动，向同一用户发送多次通知。推送通知是基于移动平台生成的推送通知令牌，路由到个别设备/用户。由于它们的大小（从32b到4kb不等），索引推送令牌或将其作为主要用户密钥对来说性能不佳。
在某些移动平台上，当用户卸载然后重新安装同一个应用程序时，会丢失主要用户密钥，并为该设备创建一个新的用户配置文件。通常在这种情况下，移动平台会在重新安装时为该用户生成一个新的推送通知令牌。然而，这并不总是保证的。因此，在少数情况下，系统中可能会有多个用户记录具有相同的推送通知令牌。
因此，为了防止对同一用户针对同一活动发送多次通知，需要从总数达到数亿到数十亿条记录的数据集中过滤出相对较小数量的重复推送令牌。为了给一个比例感，仅过滤1亿个推送令牌所需的内存是100M * 256 = 25GB！
这个想法非常简单。
分配一个大小为m的位数组
选择k个独立的哈希函数，其范围是[0, m-1]
对于每个数据元素，计算哈希值并打开位
对于成员查询，应用哈希并检查所有相应的位是否为'on'
注意，位可能会被哈希冲突打开，导致误报，即不存在的元素可能被错误地报告为存在，目标是最小化这种情况。
Bloom过滤器的哈希函数应该是独立的且均匀分布的。像MD5或SHA-1这样的加密哈希函数由于性能原因不是好的选择。一些合适的快速哈希包括MurmurHash、FNV哈希和Jenkin的哈希。
使用MurmurHash -
确定位数组的大小涉及选择最优数量的哈希函数以最小化误报概率。
对于给定的n、m和k，误报概率，即当元素不存在时，所有相应的位错误地'on'的概率为
P(k, n, m) = (1 - e^(-k * n / m))^k
为了最小化P(k, n, m)，即最小化误报概率，需要找到最优的k，使得P(k, n, m)最小，所以，对于1亿个推送令牌，错误概率为0.001