面试题：Hbase中布隆过滤器误判率与哪些因素相关

Question

在Hbase的布隆过滤器场景下，请阐述误判率与哪些因素存在关联，例如布隆过滤器的大小、插入元素的数量等因素是如何影响误判率的。

Answer 1

• 布隆过滤器大小：布隆过滤器大小指的是其内部数组的容量。一般来说，布隆过滤器越大，即数组容量越大，误判率越低。因为更大的数组可以容纳更多的哈希值，使得不同元素的哈希值冲突概率降低。例如，对于同样数量的插入元素，一个容量为1000的布隆过滤器比容量为100的布隆过滤器误判率更低。
• 插入元素的数量：插入元素数量越多，误判率越高。随着元素不断插入，布隆过滤器内部数组被置为1的位置增多，新元素插入时，其哈希值对应的位置可能已经被其他元素置为1，从而导致误判。比如，在一个固定大小的布隆过滤器中，先插入10个元素和插入100个元素相比，插入100个元素时误判率会更高。
• 哈希函数的个数：哈希函数个数对误判率有影响。哈希函数个数过少，可能无法充分分散元素的哈希值，导致冲突增加，误判率升高；而哈希函数个数过多，虽然可以更均匀地分散哈希值，但也会使布隆过滤器中被置为1的位置增加，同样可能提高误判率。存在一个理论上的最优哈希函数个数，与布隆过滤器大小和插入元素数量有关，能使误判率达到最低。