布隆过滤器是如何用多个哈希函数和位数组来判断一个元素“可能存在”或“一定不存在”的？它的误判率与位数组大小和哈希函数个数有何数学关系？如何根据预期数据量计算合适的参数？

Question

布隆过滤器是如何用多个哈希函数和位数组来判断一个元素“可能存在”或“一定不存在”的？它的误判率与位数组大小和哈希函数个数有何数学关系？如何根据预期数据量计算合适的参数？

Answer 1

布隆过滤器无法保证 100% 正确性，存在误判率（False Positive Rate），即某些不存在于集合中的元素会被错误地判定为存在。