在正确的用例中，布隆过滤器看起来就像魔法。这是一个大胆的说法，但在本教程中，我们将探讨这种奇怪的数据结构、如何最好地使用它，以及一些使用Redis和Node.js的实际示例。
布隆过滤器是一种概率性、单向数据结构。在这种情况下，“过滤器”一词可能会令人困惑；过滤器意味着它是一个活跃的事物，一个动词，但将它视为存储，一个名词可能更容易。使用简单的布隆过滤器，您可以做两件事：
- 添加一个项目。
- 检查之前是否未添加过某个项目。
这些是需要理解的重要限制-您无法删除项目，也无法在布隆过滤器中列出项目。此外，您无法确定过去是否已将某个项目添加到过滤器中。这就是布隆过滤器的概率性质发挥作用的地方——误报是可能的，但误报则不然。如果过滤器设置正确，误报的可能性会非常小。
存在布隆过滤器的变体，它们添加了其他功能，例如删除或缩放，但它们也增加了复杂性和限制。在继续了解变体之前，首先了解简单的布隆过滤器非常重要。本文仅介绍简单的布隆过滤器。
有了这些限制，您可以获得许多好处：固定大小、基于哈希的加密和快速查找。
当您设置布隆过滤器时，您需要为其指定一个大小。此大小是固定的，因此如果过滤器中有一项或十亿项，它永远不会增长超过指定的大小。当您向过滤器添加更多项目时，误报的可能性就会增加。如果您指定了较小的过滤器，则与使用较大的过滤器相比，误报率会增加得更快。
布隆过滤器建立在单向散列的概念之上。与正确存储密码非常相似，布隆过滤器使用哈希算法来确定传入其中的项目的唯一标识符。哈希本质上是无法逆转的，并且由看似随机的字符串表示。因此，如果有人获得了布隆过滤器的访问权限，它不会直接泄露任何内容。
最后，布隆过滤器速度很快。与其他方法相比，该操作涉及的比较次数要少得多，并且可以轻松存储在内存中，从而防止影响性能的数据库命中。
现在您已经了解了布隆过滤器的限制和优点，让我们来看看可以使用它们的一些情况。
设置
我们将使用Redis和Node.js来说明Bloom过滤器。Redis是Bloom过滤器的存储介质；它速度快，位于内存中，并且有一些特定的命令（GETBIT、SETBIT），可以提高实施效率。我假设您的系统上安装了Node.js、npm和Redis。您的Redis服务器应该在localhost上的默认端口上运行，以便我们的示例正常工作。
在本教程中，我们不会从头开始实现过滤器；而是从头开始实现过滤器。相反，我们将重点关注npm中预构建模块的实际用途：bloom-redis。bloom-redis有一组非常简洁的方法：add、contains和clear。
如前所述，布隆过滤器需要哈希算法来生成项目的唯一标识符。bloom-redis使用众所周知的MD5算法，尽管它可能不适合Bloom过滤器（有点慢，有点过大），但可以正常工作。
独特的用户名
用户名，尤其是在URL中标识用户的用户名，需要是唯一的。如果您构建一个允许用户更改用户名的应用程序，那么您可能需要一个从未使用过的用户名，以避免用户名混淆和被攻击。
如果没有布隆过滤器，您需要引用一个包含曾经使用过的每个用户名的表，而大规模时这可能会非常昂贵。布隆过滤器允许您在用户每次采用新名称时添加一个项目。当用户检查用户名是否被占用时，您所需要做的就是检查布隆过滤器。它将能够绝对确定地告诉您所请求的用户名是否先前已添加。过滤器可能会错误地返回用户名已被使用，而实际上用户名尚未被使用，但这只是为了谨慎起见，不会造成任何真正的伤害（除了用户可能无法声明“k3w1d00d47”）.
为了说明这一点，让我们使用Express构建一个快速的REST服务器。首先，创建package.json文件，然后运行以下终端命令。
npm安装bloom-redis--save
npminstallexpress--save
npminstallredis--save
bloom-redis的默认选项大小设置为2MB。出于谨慎考虑，这是错误的，但它相当大。设置布隆过滤器的大小至关重要：太大会浪费内存，太小则误报率会太高。确定大小所涉及的数学非常复杂，超出了本教程的范围，但幸运的是，有一个布隆过滤器大小计算器可以完成这项工作，而无需破解教科书。
现在，创建app.js如下：
