## 原理

A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not – in other words, a query returns either "possibly in set" or "definitely not in set". Elements can be added to the set, but not removed (though this can be addressed with a "counting" filter); the more elements that are added to the set, the larger the probability of false positives.

## 算法描述

<!-- 通常，k需要远小于m且需要尽可能满足：对于每一个元素x，经过k个函数会映射到k个不同的位置上 -->

• 元素数量n越少，生成的k个哈希值碰撞的可能就越小，判断也就越准确；
• 数组长度m越大，生成的k个哈希值碰撞的可能也就越小，判断也就越准确；
• k个函数选取越准确，生成的k个哈希值碰撞的可能越小，判断越准确；