Comment déterminer rapidement si un élément se trouve dans une collection en Java

1. Qu'est-ce qu'un filtre Bloom ?

Le filtre Bloom a été proposé par un homme nommé Bloom en 1970.

Vous pouvez en fait le considérer comme une structure de données composée d'un vecteur binaire (ou d'un tableau de bits) et d'une série de fonctions de mappage aléatoires (fonctions de hachage).

Son avantage est que l'efficacité spatiale et le temps de requête sont bien meilleurs que les algorithmes ordinaires. Son inconvénient est qu'il a un certain taux de mauvaise reconnaissance et des difficultés de suppression.

2. Principe de mise en œuvre

Prenons d'abord une photo

L'idée principale de l'algorithme de filtre Bloom est d'utiliser n fonctions de hachage pour hacher et obtenir différentes valeurs de hachage, qui sont mappées sur Différentes. positions d'index du tableau (la longueur de ce tableau peut être très longue), puis définissez la valeur du bit d'index correspondant sur 1.

Pour déterminer si l'élément apparaît dans l'ensemble, il faut utiliser k fonctions de hachage différentes pour calculer la valeur de hachage et voir si la valeur à la position d'index correspondante de la valeur de hachage est 1. Si l'une n'est pas 1, cela signifie que le élément N'existe pas dans la collection.

Mais il est également possible de juger que l'élément est dans l'ensemble, mais que l'élément ne l'est pas. Les 1 au-dessus de toutes les positions d'index de cet élément sont fixés par d'autres éléments, ce qui conduit à une certaine probabilité d'erreur de jugement (c'est pourquoi). ce qui précède peut être dans un ensemble) La cause première est qu'il y aura un certain conflit de hachage).

Remarque : Plus le taux de faux positifs est faible, plus la performance correspondante sera faible.

3. Fonction

Le filtre Bloom peut être utilisé pour déterminer si un élément est (éventuellement) dans un ensemble. Par rapport à d'autres structures de données, le filtre Bloom présente d'énormes contraintes d'espace et de temps.

Faites attention au mot ci-dessus : peut-être. Il y a ici un suspense réservé, qui sera analysé en détail ci-dessous.

Déterminer si les données fournies existent

Empêcher la pénétration du cache (déterminer si les données demandées sont valides pour éviter de contourner directement le cache pour demander la base de données), etc., filtrage anti-spam des boîtes aux lettres, fonctions de liste noire, etc.

4. Implémentation spécifique

Après avoir lu l'idée de l'algorithme du filtre Bloom, commençons par expliquer l'implémentation spécifique.

Permettez-moi d'abord de donner un exemple. Supposons qu'il y ait deux chaînes, Wangcai et Xiaoqiang, elles ont été hachées trois fois respectivement, puis la valeur de la position d'index du tableau correspondant (en supposant que la longueur du tableau est de 16) est définie en fonction. sur le résultat du hachage. est 1, regardons d'abord l'expression richesse prospère :

richesse prospère. Après avoir haché trois fois, les valeurs sont 2, 4 et 6. Ensuite, nous pouvons obtenir les valeurs de l'indice. ​​​comme 2, 4 et 6, nous allons donc La valeur de l'index (2, 4, 6) du tableau est définie sur 1 et le reste est traité comme 0. Supposons maintenant que vous deviez trouver Wangcai . Après les trois mêmes hachages, vous retrouverez les valeurs des positions correspondant aux index 2, 4 et 6. Si les deux valent 1, alors on peut juger que la richesse peut exister.

Ensuite, insérez Xiaoqiang dans le filtre Bloom. Le processus réel est le même que ci-dessus. Supposons que les indices obtenus soient 1, 3, 5

Mettez de côté l'existence de la richesse, Xiaoqiang est comme ça en ce moment. le filtre Bloom, le tableau réel combiné avec Wangcai et Xiaoqiang ressemble à ceci :

Il y a maintenant une donnée : 9527. L'exigence actuelle est de déterminer si 9527 existe. Supposons que 9527 soit obtenu après trois hachages. sont : 5, 6, 7. Il s'avère que la valeur de la position avec l'indice 7 est 0, on peut donc définitivement juger que 9527 ne doit pas exister.

Puis un autre 007 domestique est arrivé. Après trois hachages, les indices obtenus étaient : 2, 3, 5. Il a été constaté que les valeurs correspondant aux indices 2, 3 et 5 étaient toutes 1, nous pouvons donc juger grossièrement. que le numéro 007 domestique peut exister. Mais en fait, après notre démonstration de tout à l'heure, le 007 domestique n'existe pas du tout. La raison pour laquelle les valeurs des positions d'index 2, 3 et 5 sont 1 est due à d'autres paramètres de données.

En parlant de ça, je me demande si tout le monde comprend le rôle du filtre Bloom.

5. Implémentation du code

En tant que programmeurs Java, nous sommes vraiment heureux. Nous utilisons de nombreux frameworks et outils, et ils sont essentiellement encapsulés, nous utilisons Google pour les encapsuler. Bien entendu, il existe d’autres méthodes que vous pouvez explorer.

Ajoutez d'abord les dépendances

<!--布隆过滤依赖-->
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>25.1-jre</version>
</dependency>

Implémentation du code

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.nio.charset.Charset;
public class BloomFilterDemo {
        public static void main(String[] args) {
        /**
         * 创建一个插入对象为一亿，误报率为0.01%的布隆过滤器
         * 不存在一定不存在
         * 存在不一定存在
         * ----------------
         *  Funnel 对象：预估的元素个数，误判率
         *  mightContain ：方法判断元素是否存在
         */
        BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")), 100000000, 0.0001);
        bloomFilter.put("死");
        bloomFilter.put("磕");
        bloomFilter.put("Redis");
        System.out.println(bloomFilter.mightContain("Redis"));
        System.out.println(bloomFilter.mightContain("Java"));
    }
}

L'explication spécifique a été écrite dans les commentaires. À présent, je pense que tout le monde doit comprendre le filtre Bloom et comment l'utiliser.

6. Combat pratique

Simulons ce scénario : résoudre la pénétration du cache via le filtre Bloom.

Tout d’abord, savez-vous ce qu’est la pénétration du cache ?

La pénétration du cache signifie que l'utilisateur accède à des données qui ne sont pas dans le cache ou dans la base de données. Parce qu'elles n'existent pas dans le cache, il accédera à la base de données si la concurrence est élevée. Il est facile de vaincre la base de données

Alors, comment le filtre Bloom résout-il ce problème ? lui

的原理是这样子的：将数据库中所有的查询条件，放入布隆过滤器中，当一个查询请求过来时，先经过布隆过滤器进行查，如果判断请求查询值存在，则继续查；如果判断请求查询不存在，直接丢弃。

其代码如下：

String get(String key) {
    String value = redis.get(key);     
    if (value  == null) {
        if(!bloomfilter.mightContain(key)){
            return null; 
        }else{
            value = db.get(key); 
            redis.set(key, value); 
        }    
    }
    return value；
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!