4.2.1 原理：哈希函数与位图

文档摘要

4.2.1 原理：哈希函数与位图 4.2.1 原理：哈希函数与位图想象一下这个场景：你的系统拥有亿级用户，每天处理海量的查询请求——“这个用户名是否已被注册？”、“这条动态用户是否已经看过？”、“这个可疑的IP地址是否在黑名单中？”。如果每一次查询你都去庞大的数据库或缓存中进行一次精确查找，就像在图书馆的每一排书架上逐一寻找一本特定的书，其带来的磁盘I/O或网络开销将是灾难性的。我们迫切需要一种方法，能够以极小的内存代价，在常数时间内告诉我们：“这个东西很可能不存在”或者“这个东西可能存在，需要进一步确认”。这就是布隆过滤器（Bloom Filter）诞生的动机，而它的全部魔法，就蕴藏在哈希函数与位图这两个看似简单的核心构件之中。让我们暂时抛开那些复杂的定义，直接切入本质。