面试题：Cassandra中布隆过滤器误判率的基本影响因素

Question

在Cassandra中，布隆过滤器的误判率主要受哪些因素影响？请简要阐述这些因素是如何作用于误判率的。

Answer 1

1. 过滤器大小（位数组大小）：
   • 作用：布隆过滤器是基于位数组实现的。位数组越大，能容纳的信息越多，不同元素映射到相同位置的概率就越低，误判率也就越低。例如，假设一个非常小的位数组，可能很多不同的元素都映射到相同的几个位置，这样在判断一个元素是否存在时，误判的可能性就很大；而较大的位数组，元素能更均匀地分布在其中，误判的概率降低。
2. 哈希函数个数：
   • 作用：哈希函数个数增加，每个元素在位数组中的映射位置增多。适量增加哈希函数个数可以使元素在位数组中分布更均匀，降低误判率。但如果哈希函数个数过多，会导致每个元素映射的位置过多，使得位数组被大量占用，其他元素映射时更容易冲突，反而可能增加误判率。例如，当哈希函数个数过少，元素映射位置少，分布不均匀，误判率较高；而当哈希函数个数从合适的值继续增加时，误判率会先降低后升高。
3. 插入元素数量：
   • 作用：随着插入元素数量的增加，位数组被占用的比例上升，不同元素映射位置冲突的可能性增大，误判率随之升高。比如一个位数组刚开始只有少量元素插入时，冲突少，误判率低；但当大量元素不断插入，位数组几乎被填满，此时再判断元素是否存在，误判的可能性就大大增加了。