O princípio do filtro Bloom é muito simples: é hash uma string em uma chave inteira e selecionar uma sequência de bits muito longa, que começa com 0, e alterar 0 nesta posição para 1 na chave; Da próxima vez que uma string entrar, a chave do valor após o hash e, se o valor nesse bit também for 1, isso significa que a string existe.
Se você seguir o método acima, ele não será diferente do algoritmo de hash e ainda há duplicações do algoritmo de hash.
O filtro Bloom Hash uma corda em várias teclas, então é melhor eu seguir o livro.
Primeiro, crie uma constante binária de 1,6 bilhão e depois defina todos os 1,6 bilhões de bits binários como zero. Para cada sequência, 8 geradores aleatórios diferentes (F1, F2, ..., F8) são usados para gerar 8 informações digitais (F1, F2, ..., F8). Em seguida, um gerador de números aleatório G é usado para mapear essas oito informações digitais para 8 números naturais G1, G2, ..., G8 em 1 a 1,6 bilhão. Agora altere todos os bits binários nessas 8 posições para 1. Dessa forma, um filtro de floração é construído.
Então, como detectar se já existe uma string?
Agora use 8 geradores de números aleatórios (F1, F2, ..., F8) para gerar 8 informações digitais S1, S2, ..., S8 para essa corda e, em seguida, correspondem a essas 8 impressão digital dos 8 bits binários do filtro de flor, ou seja, T1, T2, ..., T8. Se a string existir, obviamente os bits binários correspondentes a T1, T2, ..., T8 deve ser 1. É assim que determina se já existe uma string.
De fato, o filtro Bloom é uma extensão do algoritmo de hash. Como é essencialmente um hash, definitivamente haverá deficiências. Em outras palavras, definitivamente haverá julgamentos. Uma string não apareceu, mas o julgamento do filtro Bloom apareceu. Embora a possibilidade seja muito pequena, ela existe.
Então, como reduzir essa probabilidade? Antes de tudo, pode -se imaginar que, se 8 impressões digitais forem estendidas a 16 erros, a probabilidade será definitivamente reduzida, mas também deve ser considerada que, dessa maneira, o número de cordas que um filtro de flores pode armazenar também é reduzido em 1 vezes; Além disso, selecione uma boa função de hash e existem muitos tipos de métodos de hash para strings, incluindo funções de hash muito boas.
O filtro de bronze é usado principalmente para filtrar URLs maliciosos. Todos os URLs maliciosos são construídos em um filtro de bronze e, em seguida, o usuário é acessado pelo URL. Se estiver em um URL malicioso, o usuário será notificado. Dessa forma, também podemos definir uma lista de permissões para alguns URLs que geralmente têm erros de julgamento e, em seguida, combinar os URLs que são considerados existentes e os URLs na lista de permissões. Se estiverem na lista de permissões, serão libertados. Obviamente, essa lista de permissões não pode ser muito grande, nem é muito grande, e a probabilidade de um erro de filtro de flores é muito pequena. Os leitores interessados podem verificar a taxa de erro do filtro Bloom.
A seguir, o código -fonte da versão Java do filtro Bloom:
importar java.util.bitset; /** * * @author xkey */public class Bloomfilter {private estático final int default_size = 2 << 24; // comprimento do bit do filtro de flores private estático final int [] sementes = {3,5,7, 11, 31, 37, 61}; // o número principal aqui pode ser seleto para reduzir a taxa de erro, a taxa de incorporação muito privada; private static simpleshash [] func = new simpleshash [sementes.length]; public static void addValue (valor da string) {for (simpleshash f: func) // hash o valor da string em 8 ou mais inteiros e depois mude para 1 nos bits desses números inteiros. } public static void add (value string) {if (value! = null) addValue (value); } public static boolean boolean ret = true; para (simpleshash f: func) // Na verdade, não há necessidade de executar todos eles aqui. Basta ret == FALSE uma vez, a sequência não será incluída. ret = ret && bits.get (f.hash (valor)); retornar ret; } public static void main (string [] args) {string value = "www.vevb.com"; for (int i = 0; i <sementes.length; i ++) {func [i] = new simpleshash (default_size, sementes [i]); } adicionar (valor); System.out.println (contém (valor)); }} classe simpleshash {// essa coisa é equivalente à estrutura no C ++ private int cap; private int semente; public simpleshash (int cap, int semente) {this.cap = cap; this.seed = semente; } public int hash (String Value) {// Hash Stand, é muito importante selecionar uma boa função hash int resultado = 0; int len = value.length (); for (int i = 0; i <len; i ++) {resultado = semente * resultado+value.charat (i); } retornar (cap - 1) e resultado; }} Resumo: O filtro Bloom é uma inovação em algoritmos de hash e requer muito pouco espaço e tem uma baixa taxa de erro. Em suma, essa idéia inovadora vale a pena aprender e é um uso do tipo de dados como o bit.
O método de implementação Java do filtro Bloom é todo o conteúdo que compartilhei com você. Espero que você possa lhe dar uma referência e espero que você possa apoiar mais o wulin.com.