Eine ausführliche Analyse des Bloom-Filters in Redis

Wie vermeide ich das Eindringen in den Cache? Im folgenden Artikel erfahren Sie mehr über den Bloom-Filter (Bloom-Filter), ein leistungsstarkes Tool zur Vermeidung von Cache-Penetrationen.

Übersicht

Der Bloom-Filter (Bloom Filter) ist eine Datenstruktur, die 1970 von Burton Howard Bloom vorgeschlagen wurde. Es handelt sich tatsächlich um einen langen binären Vektor und eine Reihe zufälliger Zuordnungsfunktionen. [Verwandte Empfehlungen: Redis-Video-Tutorial] Bloom Filter）是一个数据结构，由布隆（Burton Howard Bloom）于 1970 年提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。【相关推荐：Redis视频教程】

布隆过滤器可以用于高效的检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远优于一般的算法，缺点是有一定的误识别率，而且难以删除（一般不支持，需要额外的实现）。

误识率指的是可以判断元素肯定不在集合中，判断元素可能在集合中，无法判断元素一定在集合中。

布隆过滤器之所以高效，因为它是一个概率数据结构，它能确认元素肯定不在集合中，或者元素可能在集合中。之所以说是可能，是因为它有一定的误识别率，使得无法 100% 确定元素一定在集合中。

问题引出

在日常工作中，有一个比较常见的需求，就是需要判断一个元素是否在集合中。例如以下场景

• 给定一个IP黑名单库，检查指定IP是否在黑名单中？
• 在接收邮件的时候，判断一个邮箱地址是否为垃圾邮件？
• 在文字处理软件中，检查一个英文单词是否拼写正确？

遇到这种问题，通常直觉会告诉我们，应该使用集合这种数据结构来实现。例如，先将 IP 黑名单库的所有 IP 全部存储到一个集合中，然后再拿指定的 IP 到该集合中检查是否存在，如果存在则说明该 IP 命中黑名单。

通过一段代码来模拟 IP 黑名单库的存储和检查。

public class IPBlackList {

	public static void main(String[] args) {
		Set<String> set = new HashSet<>();
		set.add("192.168.1.1");
		set.add("192.168.1.2");
		set.add("192.168.1.4");
		System.out.println(set.contains("192.168.1.1"));
		System.out.println(set.contains("192.168.1.2"));
		System.out.println(set.contains("192.168.1.3"));
		System.out.println(set.contains("192.168.1.4"));
	}
}

集合的内部，通常是使用散列表来实现。其优点是查询非常高效，缺点是比较耗费存储空间。

一般在数据量比较小的时候，我们会使用集合来进行存储。以空间换时间，在占用空间较小的情况下，同时又能提高查询效率。

但是，当存储的数据量比较大的时候，耗费大量空间将会成为问题。因为这些数据通常会存储到进程内存中，以加快查询效率。而机器的内存通常都是有限的，要尽可能高效的使用。

另一方面，散列表在空间和效率上是需要做平衡的。存储相同数量的元素，如果散列表容量越小，出现冲突的概率就越高，用于解决冲突的时间将会花费更多，从而影响性能。

而布隆过滤器（Bloom Filter）的产生，能够很好的解决这个问题。一方面能够以更少的内存来存储数据，另一方面能够实现非常高效的查询性能。

基本原理

• 首先，建立一个二进制向量，并将所有位设置为 0

• 然后，选定 K 个散列函数，用于对元素进行 K 次散列，计算向量的位下标。

添加元素

当添加一个元素到集合中时，通过 K 个散列函数分别作用于元素，生成 K 个值作为下标，并对向量的相应位设置为 1。

检查元素

如果要检查一个元素是否存在集合中，用同样的散列方法，生成 K 个下标，并检查向量的相应位是否全部是 1。

如果全为 1，则该元素很可能在集合中；否则（只要有1个或以上的位为0），该元素肯定不在集合中。

Demo

• 假设有一个布隆过滤器，容量是15位，使用2个哈希函数，如下所示。

|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |0|||||||||||||||||||

• 添加一个字符串 a，2次哈希得到下标为 4 和 10，将 4 和 10 对应的位由 0 标记为 1。

|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |||||1||||||1|||||||||

• 再添加一个字符串 b

  Bloom-Filter Kann sein Wird verwendet, um effizient abzurufen, ob sich ein Element in einer Sammlung befindet. Sein Vorteil besteht darin, dass die Speicherplatzeffizienz und die Abfragezeit weitaus besser sind als bei herkömmlichen Algorithmen. Der Nachteil besteht darin, dass er eine gewisse Fehlerkennungsrate aufweist und schwer zu löschen ist (im Allgemeinen nicht unterstützt und erfordert eine zusätzliche Implementierung).

Die Fehlerrate bedeutet, dass beurteilt werden kann, dass das Element definitiv nicht in der Menge enthalten ist. Es kann beurteilt werden, dass das Element möglicherweise in der Menge enthalten ist, aber es kann nicht beurteilt werden, dass das Element vorhanden sein muss im Set sein.

Der Bloom-Filter ist effizient, weil es sich um eine probabilistische Datenstruktur handelt, die bestätigt, dass ein Element definitiv nicht in der Menge ist oder dass das Element wahrscheinlich in der Menge ist. Der Grund, warum dies möglich ist, liegt darin, dass es eine gewisse Fehlerkennungsrate gibt, sodass es unmöglich ist, 100 % sicher zu sein, dass das Element in der Menge vorhanden sein muss. 🎜

Frage 🎜🎜Bei der täglichen Arbeit besteht häufig die Notwendigkeit, festzustellen, ob sich ein Element in einer Menge befindet. Zum Beispiel das folgende Szenario🎜

• Überprüfen Sie anhand einer IP-Blacklist-Datenbank, ob die angegebene IP in der Blacklist enthalten ist. 🎜
• Wie kann man beim Empfang von E-Mails feststellen, ob es sich bei einer E-Mail-Adresse um Spam handelt? 🎜
• Überprüfen Sie in einer Textverarbeitungssoftware, ob ein englisches Wort richtig geschrieben ist? 🎜🎜🎜Wenn wir auf ein solches Problem stoßen, sagt uns unsere Intuition normalerweise, dass wir eine Datenstruktur wie eine Menge verwenden sollten, um es zu implementieren. Speichern Sie beispielsweise zunächst alle IPs in der IP-Blacklist-Datenbank in einem Satz und prüfen Sie dann, ob die angegebene IP im Satz vorhanden ist. Wenn sie vorhanden ist, bedeutet dies, dass die IP auf die Blacklist gelangt. 🎜🎜Simulieren Sie die Speicherung und Überprüfung der IP-Blacklist-Bibliothek durch einen Code. 🎜

  <dependency>
      <groupId>com.google.guava</groupId>
      <artifactId>guava</artifactId>
      <version>23.0</version>
  </dependency>

  🎜Die Interna einer Sammlung werden normalerweise mithilfe von Hash-Tabellen implementiert. Der Vorteil besteht darin, dass die Abfrage sehr effizient ist, der Nachteil besteht jedoch darin, dass sie mehr Speicherplatz verbraucht. 🎜🎜Wenn die Datenmenge relativ gering ist, verwenden wir im Allgemeinen Sammlungen zur Speicherung. Der Tausch von Platz gegen Zeit kann die Abfrageeffizienz verbessern und gleichzeitig weniger Platz beanspruchen. 🎜🎜Wenn jedoch die gespeicherte Datenmenge relativ groß ist, wird der hohe Speicherplatzverbrauch zum Problem. Weil diese Daten normalerweise im Prozessspeicher gespeichert werden, um die Abfrageeffizienz zu beschleunigen. Der Speicher der Maschine ist meist begrenzt und muss möglichst effizient genutzt werden. 🎜🎜Andererseits müssen Hash-Tabellen hinsichtlich Platz und Effizienz ausgewogen sein. Bei gleicher Anzahl von Elementen ist die Wahrscheinlichkeit eines Konflikts höher, wenn die Kapazität der Hash-Tabelle geringer ist und mehr Zeit für die Lösung von Konflikten aufgewendet wird, was sich negativ auf die Leistung auswirkt. 🎜🎜Die Einführung des Bloom-Filters (Bloom-Filter) kann dieses Problem sehr gut lösen. Einerseits können Daten mit weniger Speicher gespeichert werden, andererseits kann eine sehr effiziente Abfrageleistung erzielt werden. 🎜

  Grundprinzip🎜

  • 🎜Erstellen Sie zunächst einen binären Vektor und setzen Sie alle Bits auf 0🎜 🎜🎜Dann werden K Hash-Funktionen ausgewählt, um die Elemente K-mal zu hashen und den Bit-Index des Vektors zu berechnen. 🎜🎜🎜

    Element hinzufügen

    🎜Beim Hinzufügen eines Elements zum Satz werden K-Hash-Funktionen jeweils auf die Elemente angewendet, um K-Werte zu generieren ​​werden als Indizes verwendet und die entsprechenden Bits des Vektors werden auf 1 gesetzt. 🎜

    Element prüfen

    🎜Wenn Sie überprüfen möchten, ob ein Element in der Menge vorhanden ist, verwenden Sie dieselbe Hashing-Methode, um K-Indizes zu generieren. Und prüfen Sie, ob die entsprechenden Bits des Vektors alle Einsen sind. 🎜🎜Wenn alle 1 sind, ist das Element wahrscheinlich in der Menge; andernfalls (solange 1 oder mehr Bits 0 sind) ist das Element definitiv nicht in der Menge. 🎜

    Demo🎜

    • 🎜Angenommen, es gibt einen Bloom-Filter mit einer Kapazität von 15 Bit und 2 verwendeten Hashes Funktion wie unten gezeigt. 🎜🎜🎜🎜|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |0||||||||||||||||🎜
      • 🎜Fügen Sie eine Zeichenfolge a hinzu , zwei Hashing-Zeiten führten zu den Indizes 4 und 10, und die Bits, die 4 und 10 entsprechen, wurden von 0 bis 1 markiert. 🎜🎜🎜🎜|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |||||1|||||1||||||||🎜<ul style="list-style-type: disc;"><li>🎜Fügen Sie eine weitere Zeichenfolge <code> bhinzu >, zweimal gehasht, um den Index 11 zu erhalten, und markiert das Bit, das 11 entspricht, von 0 auf 1. 🎜🎜🎜🎜|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |||||1||||||1|1|||||||🎜

        • Fügen Sie eine weitere Zeichenfolge c hinzu, hashen Sie zweimal, um die Indizes 11 und 12 zu erhalten, und markieren Sie die entsprechenden Bits von 0 bis 1. c，2 次哈希得到下标为 11 和 12，将对应的位由 0 标记为 1。

        |0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |||||1||||||1|1|1|||||||

        • 最后添加一个字符串 sam，2 次哈希得到下标为 0 和 7，将对应的位由 0 标记为 1。

        |0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |1||||1|||1|||1|1|1|||||||

        上面，我们添加了 4 个字符串，每个字符串分别进行 2 次哈希，对应的2个位标记为1，最终被标记为1的共有6位而不是8位。

        这说明，不同的元素，哈希后得到的位置是可能出现重叠的。如果元素越多，出现重叠的概率会更高。如果有2个元素出现重叠的位置，我们是无法判断任一元素一定在集合中的。

        如果要检查一下元素是否存在集合中，只需要以相同的方法，进行 2 次哈希，将得到的 2 个下标在布隆过滤器中的相应位进行查找。如果对应的 2 位不是全部为1，则该元素肯定不在集合中。如果对应的 2 位全部为1，则说明该元素可能在集合中，也可能不存在。

        例如，检查字符串 b 是否存在集合中，哈希得到的 2 个下标都为11。检查发现，11对应的位为1。但是，这并不能说明 b 一定在集合中。这是因为，字符串 c 哈希后的下标也包含11，有可能只是字符串c在集合中，而 b 却不存在，这就是造成了误识别，也称为假阳性。

        再检查字符串 foo，哈希得到的下标分别为 8 和 13，对应的位都为0。因此，字符串 foo 肯定不在集合中。

        数学原理

        布隆过滤器背后的数学原理是

        两个完全随机的数字相冲突的概率很小，因此可以在很小的误识别率条件下，用很少的空间存储大量信息。

        误识别率

        误识别率（FPP，false positive probabilistic）的计算如下。

        假设布隆过滤器大小为 m 比特，存储了 n 个元素，使用 k 次散列函数来计算元素的存储位置。

        • 添加 1 个元素，则任一比特为 1 的概率为 1/m，任一比特为 0 的概率为 1-1/m；
        • 添加 1 个元素，执行 k 次散列之后，则任一比特为 0 的概率为 (1-1/m)^k，任一比特为 1 的概率为 1-(1-1/m)^k；
        • 如果添加 n 个元素，那么任一比特为 0 的概率为 (1-1/m)^kn，任一比特为 1 的概率为 1-(1-1/m)^kn；
        • 如果将 1 个新的元素，添加到已存在 n 个元素的布隆过滤器中，则任一比特已经为 1 的概率与上面相同，概率为 1-(1-1/m)^kn。因此，k 个比特都为1的概率为：(1-(1-1/m)^kn)^k，此即为新插入元素的误识别率。

        当 n 值比较大时，$(1-(1-1/m)^{kn})^k$ 约等于 $(1-e^{-kn/m})^k$

        假定布隆过滤器大小 m 为 16 比特，k为 8，存储元素 n 为1，那么误识别（假阳性）的概率是万分之五（5/10000）。

        此时，m/n=16，事实上这表示 1个元素使用 16 个比特的空间来存储。

        因此，当 k 相同时，m/n 为 16/1、32/2、64/4 等值时具有相同的误识别率。

        网站 Bloom Filters - the math 给出了布隆过滤器的误识别率表，可以很方便的查处不同 m，n，k

        |0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |||||1|||||1|1|1||||||
        • Fügen Sie schließlich eine Zeichenfolge sam hinzu und hashen Sie sie zweimal, um den Index zu erhalten: 0 und 7. Markieren Sie das entsprechende Bit von 0 bis 1.

        • |0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |1||||1|||1|||1|1|1||||||
          Oben haben wir 4 Zeichenfolgen hinzugefügt, wobei jede Zeichenfolge 2-mal gehasht wurde, was 2 Bits entspricht, die als 1 markiert sind, und Insgesamt werden schließlich 6 Bits statt 8 Bits als 1 markiert.
        Dies zeigt, dass sich die durch Hashing verschiedener Elemente erhaltenen Positionen überschneiden können. Je mehr Elemente vorhanden sind, desto höher ist die Wahrscheinlichkeit einer Überlappung. Wenn sich zwei Elemente an überlappenden Positionen befinden, können wir nicht beurteilen, ob sich eines der Elemente in der Menge befinden muss.

        Wenn Sie überprüfen möchten, ob ein Element in der Menge vorhanden ist, müssen Sie es nur zweimal auf die gleiche Weise hashen und die entsprechenden Bits im Bloom-Filter nach den beiden erhaltenen Indizes durchsuchen. Wenn die entsprechenden 2 Bits nicht alle 1 sind, ist das Element definitiv nicht in der Menge. Wenn die entsprechenden 2 Bits alle 1 sind, bedeutet dies, dass das Element möglicherweise in der Menge vorhanden ist oder nicht.

        Wenn beispielsweise überprüft wird, ob die Zeichenfolge b in der Menge vorhanden ist, sind die beiden durch Hashing erhaltenen Indizes beide 11. Überprüfen Sie, ob das Bit, das 11 entspricht, 1 ist. Dies bedeutet jedoch nicht, dass b in der Sammlung enthalten sein muss. Dies liegt daran, dass der gehashte Index der Zeichenfolge c ebenfalls 11 enthält. Es ist möglich, dass die Zeichenfolge c in der Menge enthalten ist, b jedoch nicht vorhanden ist. Dies ist der Grund Fehlidentifizierung, auch falsch positiv genannt.
        Überprüfen Sie die Zeichenfolge foo noch einmal. Die durch Hashing erhaltenen Indizes sind 8 bzw. 13 und die entsprechenden Bits sind alle 0. Daher ist die Zeichenfolge foo definitiv nicht in der Menge enthalten.

        Mathematisches Prinzip

        Das mathematische Prinzip hinter dem Bloom-Filter ist

        Die Wahrscheinlichkeit, dass zwei völlig zufällige Zahlen kollidieren, ist sehr gering, sodass sie in sehr kurzer Zeit erkannt werden kann klein Unter der Bedingung einer geringen Falscherkennungsrate wird eine große Informationsmenge auf kleinem Raum gespeichert.

        Fehlerkennungsrate 🎜🎜Die Fehlerkennungsrate (FPP, falsch positive Wahrscheinlichkeit) wird wie folgt berechnet. 🎜🎜Gehen Sie davon aus, dass die Größe des Bloom-Filters m beträgt und n Elemente speichert. Verwenden Sie k Hash-Funktionen, um den Speicherort der Elemente zu berechnen. 🎜

        🎜Füge 1 Element hinzu, dann beträgt die Wahrscheinlichkeit, dass ein beliebiges Bit 1 ist, 1/m, und die Wahrscheinlichkeit, dass ein beliebiges Bit 0 ist, beträgt 1-1/m ;🎜🎜Füge 1 Element hinzu und führe k Hashes durch, dann ist die Wahrscheinlichkeit, dass irgendein Bit 0 ist, (1-1/m)^k, und die Wahrscheinlichkeit, dass irgendein Bit 1 ist, ist 1 -(1-1/m)^k; 🎜🎜Wenn n Elemente hinzugefügt werden, ist die Wahrscheinlichkeit, dass ein beliebiges Bit 0 ist, (1-1/m)^kn, die Wahrscheinlichkeit dass jedes Bit 1 ist, ist 1-(1-1/m)^kn 🎜🎜Wenn ein neues Element zum vorhandenen n in einem Bloom-Filter mit Elementen hinzugefügt wird , die Wahrscheinlichkeit, dass ein beliebiges Bit bereits 1 ist, ist die gleiche wie oben und die Wahrscheinlichkeit beträgt 1-(1-1/m)^kn. Daher beträgt die Wahrscheinlichkeit, dass alle k Bits 1 sind: (1-(1-1/m)^kn)^k, was der Fehlerkennungsrate neu eingefügter Elemente entspricht. 🎜🎜🎜🎜Wenn der n-Wert relativ groß ist, ist $(1-(1-1/m)^{kn})^k$ ungefähr gleich $(1-e ^{- kn/m})^k$🎜🎜🎜Angenommen, die Bloom-Filtergröße m beträgt 16 Bit, k ist 8 und das Speicherelement n Code> ist 1, dann beträgt die Wahrscheinlichkeit einer Fehlidentifizierung (falsch positiv) fünf von zehntausend (5/10000). 🎜🎜Zu diesem Zeitpunkt <code>m/n=16 bedeutet dies tatsächlich, dass 1 Element 16 Bit Speicherplatz zum Speichern benötigt. 🎜🎜Wenn also k gleich ist, hat m/n die gleiche Fehlerkennungsrate, wenn sie 16/1, 32/2, 64/4 usw. beträgt. 🎜🎜WebsiteBloom Filters - Die Mathematik ergibt die Falscherkennungsratentabelle des Bloom-Filters, der leicht verschiedene m, n, k überprüfen und verarbeiten kann. Code> Falscherkennungsrate bei einem bestimmten Wert. 🎜🎜Um die Falscherkennungsrate zu lösen🎜🎜Zu den gängigen Methoden zur Lösung der Falscherkennungsrate gehören 🎜🎜🎜🎜Whitelist🎜🎜🎜🎜Backtracking-Bestätigung🎜🎜🎜🎜🎜Whitelist🎜🎜🎜Eine gängige Methode zur Lösung der Falscherkennungsrate ist: Erstellen Sie eine kleinere Whitelist, in der Daten gespeichert werden, die möglicherweise falsch identifiziert werden. 🎜🎜Nehmen Sie als Beispiel die Spam-Filterung. Angenommen, wir verfügen über eine Spam-Bibliothek, die Spam beim Empfang von E-Mails herausfiltert. 🎜🎜Zu diesem Zeitpunkt können Sie diese Spam-Bibliothek zunächst im Bloom-Filter speichern. Beim Empfang von E-Mails können Sie die meisten normalen E-Mails zunächst effizient durch den Bloom-Filter herausfiltern. 🎜🎜Bei einer geringen Anzahl von Treffern handelt es sich (möglicherweise) um Spam-E-Mails, bei einigen handelt es sich möglicherweise um normale E-Mails. 🎜<p>再创建一个白名单库，当在布隆过滤器中判断可能为垃圾邮件时，通过查询白名单来确认是否为正常邮件。</p> <p>对于没在白名单中的邮件，默认会被移动到垃圾箱。通过人工识别的方式，当发现垃圾箱中存在正常邮件的时候，将其移入白名单。</p> <h3 data-id="heading-11"><strong>回源确认</strong></h3> <p>很多时候，使用布隆过滤器是为了低成本，高效率的拦截掉大量数据不在集合中的场景。例如</p> <ul> <li>Google Bigtable，Apache HBase以及Apache Cassandra和PostgreSQL 使用 Bloom 过滤器来减少对不存在的行或列的磁盘查找。避免进行昂贵的磁盘查找，可大大提高数据库查询操作的性能。</li> <li>在谷歌浏览器用于使用布隆过滤器来识别恶意URL的网页浏览器。首先会针对本地 Bloom 过滤器检查所有 URL，只有在 Bloom 过滤器返回肯定结果的情况下，才对执行的 URL 进行全面检查（如果该结果也返回肯定结果，则用户会发出警告）。</li> <li>拦截掉大量非IP黑名单请求，对于少量可能在黑名单中的IP，再查询一次黑名单库。</li> </ul> <p><strong>这是布隆过滤器非常典型的应用场景，先过滤掉大部分请求，然后只处理少量不明确的请求。</strong></p> <p><strong>这个方法，和白名单库的区别是，不需要再另外建立一套库来处理，而是使用本来就已经存在的数据和逻辑。</strong></p> <p>例如 Google Bigtable 查询数据行本来就是需要查的，只不过使用布隆过滤器拦截掉了大部分不必要的请求。而 IP 是否为黑名单也是需要查询的，同样是先使用布隆过滤器来拦截掉大部分IP。</p> <p>而上面垃圾邮件的处理，对于可能为垃圾邮件的情况，不是通过完整的垃圾邮件库再查询一次进行确认，而是用增加白名单来进行判断的方式。因为通常来说，白名单库会更小，便于缓存。</p> <p>这里所说的回源，实际上是对可能被误识别的请求，最后要回到数据源头或逻辑确认一次。</p> <h2 data-id="heading-12">Guava中的布隆容器的实现</h2> <p>Guava 中就提供了一种 Bloom Filter 的实现。</p> <h3 data-id="heading-13"><strong>guava包引入</strong></h3> <p>要使用 Bloom Filter，需要引入 guava 包</p><pre class="brush:js;toolbar:false;">&lt;dependency&gt; &lt;groupId&gt;com.google.guava&lt;/groupId&gt; &lt;artifactId&gt;guava&lt;/artifactId&gt; &lt;version&gt;23.0&lt;/version&gt; &lt;/dependency&gt;</pre><h3 data-id="heading-14"><strong>误判率测试</strong></h3> <p>下面对布隆容器的误判率进行测试，分2步</p> <ul style="list-style-type: disc;"> <li><p>往过滤器中放一百万个数，然后去验证这一百万个数是否能通过过滤器</p></li> <li><p>另外找一万个数，去检验漏网之鱼的数量</p></li> </ul><pre class="brush:js;toolbar:false;">/** * 测试布隆过滤器(可用于redis缓存穿透) * * @author 敖丙 */ public class TestBloomFilter { private static int total = 1000000; private static BloomFilter&lt;Integer&gt; bf = BloomFilter.create(Funnels.integerFunnel(), total); // private static BloomFilter&lt;Integer&gt; bf = BloomFilter.create(Funnels.integerFunnel(), total, 0.001); public static void main(String[] args) { // 初始化1000000条数据到过滤器中 for (int i = 0; i &lt; total; i++) { bf.put(i); } // 匹配已在过滤器中的值，是否有匹配不上的 for (int i = 0; i &lt; total; i++) { if (!bf.mightContain(i)) { System.out.println(&quot;有坏人逃脱了~~~&quot;); } } // 匹配不在过滤器中的10000个值，有多少匹配出来 int count = 0; for (int i = total; i &lt; total + 10000; i++) { if (bf.mightContain(i)) { count++; } } System.out.println(&quot;误伤的数量：&quot; + count); } }</pre><p>运行结果</p><pre class="brush:js;toolbar:false;">误伤的数量：320</pre><p>运行结果表示，遍历这一百万个在过滤器中的数时，都被识别出来了。一万个不在过滤器中的数，误伤了320个，错误率是0.03左右。</p> <h3 data-id="heading-15"><strong>Bloom Filter 源码分析</strong></h3><pre class="brush:js;toolbar:false;">public static &lt;T&gt; BloomFilter&lt;T&gt; create(Funnel&lt;? super T&gt; funnel, int expectedInsertions) { return create(funnel, (long) expectedInsertions); } public static &lt;T&gt; BloomFilter&lt;T&gt; create(Funnel&lt;? super T&gt; funnel, long expectedInsertions) { return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions } public static &lt;T&gt; BloomFilter&lt;T&gt; create( Funnel&lt;? super T&gt; funnel, long expectedInsertions, double fpp) { return create(funnel, expectedInsertions, fpp, BloomFilterStrategies.MURMUR128_MITZ_64); } static &lt;T&gt; BloomFilter&lt;T&gt; create( Funnel&lt;? super T&gt; funnel, long expectedInsertions, double fpp, Strategy strategy) { ...... }</pre><p>Bloom Filter 一共四个 <code>create 方法，不过最终都是走向第4个。看一下每个参数的含义

        • funnel：数据类型(一般是调用Funnels工具类中的)

        • expectedInsertions：期望插入的值的个数

        • fpp： 错误率(默认值为0.03)

        • strategy： 哈希算法 Bloom Filter的应用

        更多编程相关知识，请访问：编程视频！！

Das obige ist der detaillierte Inhalt vonEine ausführliche Analyse des Bloom-Filters in Redis. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!