Traduzido do English • Ver original Qual estrutura de dados você usaria para determinar se uma entidade está em um determinado conjunto de dados com velocidade? Muitos responderiam "Hashtable" sem hesitar. Hashtable tem bom desempenho ao acessar uma entidade entre um grupo de entidades — a complexidade média de tempo de suas operações de leitura é constante. No entanto, usar Hashtables pode ser bastante caro ao lidar com grandes conjuntos de dados. Hashtables precisam acompanhar cada entidade no conjunto de dados, resultando em uma complexidade linear no espaço.
Existe uma alternativa melhor ao Hashtable? Você pode querer perguntar. A resposta é sim, desde que você esteja disposto a abrir mão da precisão. Neste artigo, vou apresentar o Filtro de Bloom, uma alternativa ao Hashtable para verificar se uma entidade pertence a um conjunto de dados com melhor complexidade espacial, ao custo de menor precisão.
O que é Bloom Filter
O Filtro de Bloom é uma estrutura de dados probabilística eficiente em espaço para testar se um item pertence a um conjunto. Semelhante ao Hashtable, o Filtro de Bloom também utiliza hashing. No entanto, ao contrário do Hashtable, o Filtro de Bloom não armazena os itens adicionados a ele. Em vez disso, calcula um valor de hash para o item adicionado e marca o valor como presente no conjunto. Portanto, não requer tanto espaço quanto o Hashtable, resultando em uma complexidade de espaço superior.
No entanto, estamos fazendo um equilíbrio entre eficiência de espaço e precisão aqui. Ao não armazenar os itens no Filtro de Bloom, também perdemos a capacidade de saber com certeza se um item pertence a um conjunto, algo que damos como certo ao usar o Hashtable. Quando queremos saber se um item existe em um Filtro Bloom, calculamos o valor de hash do item e verificamos se o valor hash está marcado como presente no Filtro de Bloom. Precisamos nos preocupar com falsos positivos, mas não com falsos negativos. Em outras palavras, quando um Filtro de Bloom afirma que um item não pertence a um conjunto, a precisão da afirmação é garantida de ser 100%. No entanto, a afirmação oposta feita por um Filtro de Bloom nem sempre está correta.
Quando usar o Bloom Filter
Como mencionado acima, o filtro Bloom é uma alternativa ideal ao Hashtable quando você valoriza a eficiência de espaço em vez da precisão (especificamente, a ausência de falsos positivos). Um detector de URLs maliciosas é um exemplo. Digamos que você tenha coletado milhões de URLs maliciosas. Se você construísse um detector de URLs maliciosas com uma Hashtable, teria que despejar todas as URLs maliciosas na Hashtable. A busca seria lenta, e as URLs ocupariam muito espaço. Esse detector tem um alto nível de precisão. No entanto, não precisa ser preciso porque o objetivo do detector de URLs maliciosas é proteger os usuários contra URLs maliciosas. Desde que o detector não confunda URLs maliciosas com URLs seguras, que são as URLs que os usuários acabam abrindo, ele terá cumprido suas funções.
Em comparação, construir o detector de URLs maliciosas com o Bloom Filter levará a um desempenho melhor em termos de complexidade espacial. Além disso, o Bloom Filter ainda pode garantir que todas as URLs marcadas como seguras estejam sempre seguras para serem abertas, protegendo os usuários contra URLs maliciosas. A única desvantagem é que o detector de URLs maliciosas agora é infestado de falsos positivos, o que significa que as URLs marcadas como maliciosas podem estar seguras. Essa desvantagem é superada pelo benefício de exigir menos espaço e velocidade de detecção mais rápida.
Ainda podemos usar o Filtro de Bloom mesmo em casos em que eliminar falsos positivos é fundamental. No entanto, precisamos adicionar uma etapa crucial após o Filtro de Bloom retornar um resultado positivo. Para garantir que o positivo não seja um falso positivo (um negativo disfarçado), recorremos à fonte original de dados (banco de dados, etc.) e verificamos se o resultado positivo está correto. Não precisamos fazer o mesmo para resultados negativos, já que todos os resultados negativos são garantidos como corretos.
Neste artigo, expliquei o que é o Bloom Filter, como ele funciona e quando usá-lo. Bloom Filter é uma alternativa ao Hashtable, mas ambos têm suas respectivas vantagens e fraquezas. Por favor, tenha isso em mente da próxima vez que decidir qual usar para construir seu recurso.