{"id":4474,"date":"2023-05-05T08:49:07","date_gmt":"2023-05-05T11:49:07","guid":{"rendered":"https:\/\/elemarjr.com\/clube-de-estudos\/?p=4474"},"modified":"2023-10-21T21:39:24","modified_gmt":"2023-10-22T00:39:24","slug":"como-melhorar-o-desempenho-de-aplicacoes-com-bloomfilter","status":"publish","type":"artigos","link":"https:\/\/elemarjr.com\/clube-de-estudos\/artigos\/como-melhorar-o-desempenho-de-aplicacoes-com-bloomfilter\/","title":{"rendered":"Como melhorar o desempenho de aplica\u00e7\u00f5es com BloomFilter?"},"content":{"rendered":"\n

O que \u00e9 BloomFilter?<\/h3>\n\n\n\n

O BloomFilter<\/em> \u00e9 uma estrutura de dados probabil\u00edstica que permite verificar se um elemento est\u00e1 presente em um conjunto. Ele foi criado por Burton Howard Bloom<\/em> em 1970 e se tornou uma ferramenta amplamente utilizada na ind\u00fastria de tecnologia da informa\u00e7\u00e3o.<\/p>\n\n\n\n

\"\"
Um exemplo de BloomFilter<\/strong>, representando o conjunto {x, y, z} . As setas coloridas mostram as posi\u00e7\u00f5es na matriz de bits para as quais cada elemento definido \u00e9 mapeado. O elemento w n\u00e3o est\u00e1 no conjunto {x, y, z} , porque faz hash para uma posi\u00e7\u00e3o de matriz de bits contendo 0. Para esta figura, m = 18 e k = 3. Fonte: Wikipedia<\/a><\/figcaption><\/figure>\n\n\n\n

Por que \u00e9 importante?<\/h3>\n\n\n\n

O BloomFilter<\/em> \u00e9 uma estrutura de dados eficiente tanto em termos de espa\u00e7o quanto em termos de tempo, e pode ser usado para melhorar o desempenho de v\u00e1rias aplica\u00e7\u00f5es. As melhores consultas e requisi\u00e7\u00f5es s\u00e3o aquelas que n\u00e3o precisam ser executadas, por isso \u00e9 importante conhecer o BloomFilter<\/em>.<\/p>\n\n\n\n

Funcionamento do BloomFilter<\/h2>\n\n\n\n

Estrutura de dados<\/h3>\n\n\n\n

A estrutura de dados do BloomFilter consiste em um vetor de bits, inicialmente zerados, e um conjunto de fun\u00e7\u00f5es de hash independentes. O tamanho do vetor e o n\u00famero de fun\u00e7\u00f5es de hash s\u00e3o escolhidos com base no tamanho do conjunto e na taxa de falsos positivos desejada.<\/p>\n\n\n\n

Opera\u00e7\u00f5es b\u00e1sicas<\/h3>\n\n\n\n

As opera\u00e7\u00f5es b\u00e1sicas realizadas pelo BloomFilter <\/em>s\u00e3o a inser\u00e7\u00e3o de elementos e a consulta de exist\u00eancia. Para inserir um elemento, \u00e9 necess\u00e1rio aplicar todas as fun\u00e7\u00f5es de hash<\/em> e marcar os bits<\/em> correspondentes no vetor. Para consultar a exist\u00eancia de um elemento, basta verificar se todos os bits correspondentes \u00e0s fun\u00e7\u00f5es de hash<\/em> est\u00e3o marcados.<\/p>\n\n\n\n

Vantagens do BloomFilter<\/h2>\n\n\n\n

Efici\u00eancia de espa\u00e7o<\/h3>\n\n\n\n

Uma das principais vantagens do BloomFilter<\/em> \u00e9 sua efici\u00eancia em termos de espa\u00e7o. Ele usa uma quantidade m\u00ednima de mem\u00f3ria para armazenar informa\u00e7\u00f5es sobre os elementos do conjunto, o que o torna ideal para aplica\u00e7\u00f5es com restri\u00e7\u00f5es de mem\u00f3ria.<\/p>\n\n\n\n

Efici\u00eancia de tempo<\/h3>\n\n\n\n

Outra vantagem do BloomFilter<\/em> \u00e9 sua efici\u00eancia de tempo. As opera\u00e7\u00f5es de inser\u00e7\u00e3o e consulta s\u00e3o r\u00e1pidas e t\u00eam complexidade de tempo constante, independentemente do tamanho do conjunto.<\/p>\n\n\n\n

Aplica\u00e7\u00f5es pr\u00e1ticas<\/h2>\n\n\n\n

Verifica\u00e7\u00e3o de exist\u00eancia<\/h3>\n\n\n\n

O BloomFilter<\/em> \u00e9 comumente usado para verificar a exist\u00eancia de elementos em um conjunto sem precisar acessar a estrutura de dados subjacente. Isso pode ser \u00fatil para evitar consultas desnecess\u00e1rias a bancos de dados ou outras estruturas de dados mais lentas.<\/p>\n\n\n\n

Filtragem de spam<\/h3>\n\n\n\n

Um exemplo de aplica\u00e7\u00e3o do BloomFilter<\/em> \u00e9 na filtragem de spam em servi\u00e7os de email<\/em>. O filtro pode verificar rapidamente se uma mensagem cont\u00e9m palavras ou frases comuns em mensagens de spam<\/em>, sem precisar armazenar todas as palavras em uma lista.<\/p>\n\n\n\n

Cache eficiente<\/h3>\n\n\n\n

Outra aplica\u00e7\u00e3o pr\u00e1tica do BloomFilter<\/em> \u00e9 na otimiza\u00e7\u00e3o de sistemas de cache<\/em>. Ele pode ser utilizado para verificar se um item est\u00e1 presente no cache<\/em> antes de realizar uma consulta mais demorada a uma fonte de dados externa.<\/p>\n\n\n\n

Implementa\u00e7\u00e3o do BloomFilter<\/h2>\n\n\n\n

Linguagens de programa\u00e7\u00e3o<\/h3>\n\n\n\n

O BloomFilter<\/em> pode ser implementado em v\u00e1rias linguagens de programa\u00e7\u00e3o, incluindo Python, Java e C#. A escolha da linguagem depender\u00e1 das necessidades e requisitos espec\u00edficos do projeto.<\/p>\n\n\n\n

Exemplo de c\u00f3digo em C#<\/h3>\n\n\n\n
C#<\/span><\/path><\/path><\/svg><\/span>
using<\/span> System<\/span>;<\/span><\/span>\nusing<\/span> System.Collections<\/span>;<\/span><\/span>\n<\/span>\nclass<\/span> <\/span>BloomFilter<\/span> <\/span>{<\/span><\/span>\n    <\/span>private<\/span> BitArray bitArray<\/span>;<\/span><\/span>\n    <\/span>private<\/span> <\/span>int<\/span> numHashFunctions<\/span>;<\/span><\/span>\n    <\/span>private<\/span> <\/span>int<\/span> numElements<\/span>;<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>BloomFilter<\/span>(<\/span>int<\/span> numElements<\/span>,<\/span> <\/span>int<\/span> numHashFunctions<\/span>)<\/span> <\/span>{<\/span><\/span>\n        <\/span>this<\/span>.<\/span>numElements<\/span> <\/span>=<\/span> <\/span>numElements<\/span>;<\/span><\/span>\n        <\/span>this<\/span>.<\/span>numHashFunctions<\/span> <\/span>=<\/span> <\/span>numHashFunctions<\/span>;<\/span><\/span>\n        <\/span>this<\/span>.<\/span>bitArray<\/span> <\/span>=<\/span> <\/span>new<\/span> BitArray<\/span>(<\/span>numElements<\/span>)<\/span>;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>private<\/span> <\/span>int<\/span>[]<\/span> <\/span>GetHashValues<\/span>(<\/span>string<\/span> input<\/span>)<\/span> <\/span>{<\/span><\/span>\n        <\/span>var<\/span> hashValues <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[<\/span>numHashFunctions<\/span>]<\/span>;<\/span><\/span>\n        <\/span>var<\/span> hash1 <\/span>=<\/span> <\/span>input<\/span>.<\/span>GetHashCode<\/span>()<\/span>;<\/span><\/span>\n        <\/span>var<\/span> hash2 <\/span>=<\/span> <\/span>hash1<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>for<\/span> <\/span>(<\/span>int<\/span> i <\/span>=<\/span> <\/span>0<\/span>;<\/span> <\/span>i<\/span> <\/span><<\/span> <\/span>numHashFunctions<\/span>;<\/span> <\/span>i<\/span>++<\/span>)<\/span> <\/span>{<\/span><\/span>\n            <\/span>hashValues<\/span>[<\/span>i<\/span>]<\/span> <\/span>=<\/span> <\/span>Math<\/span>.<\/span>Abs<\/span>((<\/span>hash1<\/span> <\/span>+<\/span> <\/span>i<\/span> <\/span>*<\/span> <\/span>hash2<\/span>)<\/span> <\/span>%<\/span> <\/span>numElements<\/span>)<\/span>;<\/span><\/span>\n        <\/span>}<\/span><\/span>\n<\/span>\n        <\/span>return<\/span> <\/span>hashValues<\/span>;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>Add<\/span>(<\/span>string<\/span> input<\/span>)<\/span> <\/span>{<\/span><\/span>\n        <\/span>var<\/span> hashValues <\/span>=<\/span> <\/span>GetHashValues<\/span>(<\/span>input<\/span>)<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>foreach<\/span> <\/span>(<\/span>var<\/span> hash <\/span>in<\/span> <\/span>hashValues<\/span>)<\/span> <\/span>{<\/span><\/span>\n            <\/span>bitArray<\/span>[<\/span>hash<\/span>]<\/span> <\/span>=<\/span> <\/span>true;<\/span><\/span>\n        <\/span>}<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>bool<\/span> <\/span>Contains<\/span>(<\/span>string<\/span> input<\/span>)<\/span> <\/span>{<\/span><\/span>\n        <\/span>var<\/span> hashValues <\/span>=<\/span> <\/span>GetHashValues<\/span>(<\/span>input<\/span>)<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>foreach<\/span> <\/span>(<\/span>var<\/span> hash <\/span>in<\/span> <\/span>hashValues<\/span>)<\/span> <\/span>{<\/span><\/span>\n            <\/span>if<\/span> <\/span>(<\/span>!<\/span>bitArray<\/span>[<\/span>hash<\/span>])<\/span> <\/span>{<\/span><\/span>\n                <\/span>return<\/span> <\/span>false;<\/span><\/span>\n            <\/span>}<\/span><\/span>\n        <\/span>}<\/span><\/span>\n<\/span>\n        <\/span>return<\/span> <\/span>true;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nclass<\/span> <\/span>Program<\/span> <\/span>{<\/span><\/span>\n    <\/span>static<\/span> <\/span>void<\/span> <\/span>Main<\/span>(<\/span>string<\/span>[]<\/span> args<\/span>)<\/span> <\/span>{<\/span><\/span>\n        <\/span>var<\/span> bloomFilter <\/span>=<\/span> <\/span>new<\/span> BloomFilter<\/span>(<\/span>1000000<\/span>,<\/span> <\/span>10<\/span>)<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>bloomFilter<\/span>.<\/span>Add<\/span>(<\/span>"<\/span>Hello<\/span>"<\/span>)<\/span>;<\/span><\/span>\n        <\/span>bloomFilter<\/span>.<\/span>Add<\/span>(<\/span>"<\/span>World<\/span>"<\/span>)<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>Console<\/span>.<\/span>WriteLine<\/span>(<\/span>bloomFilter<\/span>.<\/span>Contains<\/span>(<\/span>"<\/span>Hello<\/span>"<\/span>))<\/span>;<\/span> <\/span>\/\/ true<\/span><\/span>\n        <\/span>Console<\/span>.<\/span>WriteLine<\/span>(<\/span>bloomFilter<\/span>.<\/span>Contains<\/span>(<\/span>"<\/span>World<\/span>"<\/span>))<\/span>;<\/span> <\/span>\/\/ true<\/span><\/span>\n        <\/span>Console<\/span>.<\/span>WriteLine<\/span>(<\/span>bloomFilter<\/span>.<\/span>Contains<\/span>(<\/span>"<\/span>Foo<\/span>"<\/span>))<\/span>;<\/span> <\/span>\/\/ false<\/span><\/span>\n    <\/span>}<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/\/ Fonte: ChatGPT<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
Este c\u00f3digo implementa um BloomFilter<\/em> usando uma “BitArray”<\/em> <\/strong>para armazenar os valores booleanos. A fun\u00e7\u00e3o de hash utilizada \u00e9 uma fun\u00e7\u00e3o simples baseada no “GetHashCode”<\/em><\/strong> do objeto de entrada, que \u00e9 iterada v\u00e1rias vezes para obter v\u00e1rias fun\u00e7\u00f5es de hash<\/em>. A fun\u00e7\u00e3o “Add”<\/strong><\/em> \u00e9 usada para adicionar um elemento ao filtro, enquanto a fun\u00e7\u00e3o “Contains”<\/em><\/strong> \u00e9 usada para verificar se um elemento est\u00e1 presente no filtro. O tamanho do filtro e o n\u00famero de fun\u00e7\u00f5es de hash <\/em>podem ser ajustados ao criar uma nova inst\u00e2ncia da classe “BloomFilter<\/em>“<\/strong>.<\/p>\n\n\n\n
Exemplo de c\u00f3digo em Python<\/h3>\n\n\n\n
Python<\/span><\/path><\/path><\/svg><\/span>
import<\/span> hashlib<\/span><\/span>\nimport<\/span> math<\/span><\/span>\n<\/span>\nclass<\/span> <\/span>BloomFilter<\/span>:<\/span><\/span>\n    <\/span>def<\/span> <\/span>__init__<\/span>(<\/span>self<\/span>,<\/span> <\/span>num_elements<\/span>,<\/span> <\/span>false_positive_probability<\/span>):<\/span><\/span>\n        <\/span>self<\/span>.<\/span>num_elements <\/span>=<\/span> num_elements<\/span><\/span>\n        <\/span>self<\/span>.<\/span>false_positive_probability <\/span>=<\/span> false_positive_probability<\/span><\/span>\n<\/span>\n        <\/span># Calcula o tamanho do bit array necess\u00e1rio<\/span><\/span>\n        <\/span>self<\/span>.<\/span>bit_array_size <\/span>=<\/span> <\/span>int<\/span>(<\/span>math<\/span>.<\/span>ceil<\/span>((<\/span>num_elements <\/span>*<\/span> math<\/span>.<\/span>log<\/span>(<\/span>false_positive_probability<\/span>))<\/span> <\/span>\/<\/span> math<\/span>.<\/span>log<\/span>(<\/span>1.0<\/span> <\/span>\/<\/span> <\/span>(<\/span>math<\/span>.<\/span>pow<\/span>(<\/span>2.0<\/span>,<\/span> math<\/span>.<\/span>log<\/span>(<\/span>2.0<\/span>))))))<\/span><\/span>\n<\/span>\n        <\/span># Inicializa o bit array com todos os bits definidos para 0<\/span><\/span>\n        <\/span>self<\/span>.<\/span>bit_array <\/span>=<\/span> <\/span>[<\/span>False<\/span>]<\/span> <\/span>*<\/span> <\/span>self<\/span>.<\/span>bit_array_size<\/span><\/span>\n<\/span>\n        <\/span># Calcula o n\u00famero de fun\u00e7\u00f5es hash necess\u00e1rio<\/span><\/span>\n        <\/span>self<\/span>.<\/span>num_hash_functions <\/span>=<\/span> <\/span>int<\/span>(<\/span>math<\/span>.<\/span>ceil<\/span>((<\/span>self<\/span>.<\/span>bit_array_size <\/span>\/<\/span> num_elements<\/span>)<\/span> <\/span>*<\/span> math<\/span>.<\/span>log<\/span>(<\/span>2.0<\/span>)))<\/span><\/span>\n<\/span>\n    <\/span>def<\/span> <\/span>_hash<\/span>(<\/span>self<\/span>,<\/span> <\/span>value<\/span>,<\/span> <\/span>salt<\/span>):<\/span><\/span>\n        <\/span># Combina o valor com o sal e retorna um hash sha256 em formato de bytes<\/span><\/span>\n        <\/span>return<\/span> hashlib<\/span>.<\/span>sha256<\/span>(<\/span>str<\/span>(<\/span>value<\/span>).<\/span>encode<\/span>()<\/span> <\/span>+<\/span> salt<\/span>.<\/span>encode<\/span>()).<\/span>digest<\/span>()<\/span><\/span>\n<\/span>\n    <\/span>def<\/span> <\/span>add<\/span>(<\/span>self<\/span>,<\/span> <\/span>value<\/span>):<\/span><\/span>\n        <\/span># Calcula os hashes necess\u00e1rios para adicionar o valor<\/span><\/span>\n        <\/span>for<\/span> i <\/span>in<\/span> <\/span>range<\/span>(<\/span>self<\/span>.<\/span>num_hash_functions<\/span>):<\/span><\/span>\n            hash_value <\/span>=<\/span> <\/span>int<\/span>.<\/span>from_bytes<\/span>(<\/span>self<\/span>.<\/span>_hash<\/span>(<\/span>value<\/span>,<\/span> <\/span>str<\/span>(<\/span>i<\/span>)),<\/span> <\/span>byteorder<\/span>=<\/span>'<\/span>big<\/span>'<\/span>)<\/span> <\/span>%<\/span> <\/span>self<\/span>.<\/span>bit_array_size<\/span><\/span>\n            <\/span>self<\/span>.<\/span>bit_array<\/span>[<\/span>hash_value<\/span>]<\/span> <\/span>=<\/span> <\/span>True<\/span><\/span>\n<\/span>\n    <\/span>def<\/span> <\/span>contains<\/span>(<\/span>self<\/span>,<\/span> <\/span>value<\/span>):<\/span><\/span>\n        <\/span># Verifica se o valor est\u00e1 presente no BloomFilter<\/span><\/span>\n        <\/span>for<\/span> i <\/span>in<\/span> <\/span>range<\/span>(<\/span>self<\/span>.<\/span>num_hash_functions<\/span>):<\/span><\/span>\n            hash_value <\/span>=<\/span> <\/span>int<\/span>.<\/span>from_bytes<\/span>(<\/span>self<\/span>.<\/span>_hash<\/span>(<\/span>value<\/span>,<\/span> <\/span>str<\/span>(<\/span>i<\/span>)),<\/span> <\/span>byteorder<\/span>=<\/span>'<\/span>big<\/span>'<\/span>)<\/span> <\/span>%<\/span> <\/span>self<\/span>.<\/span>bit_array_size<\/span><\/span>\n            <\/span>if<\/span> <\/span>not<\/span> <\/span>self<\/span>.<\/span>bit_array<\/span>[<\/span>hash_value<\/span>]:<\/span><\/span>\n                <\/span>return<\/span> <\/span>False<\/span><\/span>\n        <\/span>return<\/span> <\/span>True<\/span><\/span>\n<\/span>\n# Fonte: ChatGPT<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
Este c\u00f3digo implementa um BloomFilter<\/em> usando uma lista de booleanos para armazenar os valores. A fun\u00e7\u00e3o de hash<\/em> utilizada \u00e9 uma fun\u00e7\u00e3o SHA256<\/span> que combina o valor a ser adicionado com um sal baseado no n\u00famero da fun\u00e7\u00e3o hash<\/em>. A fun\u00e7\u00e3o “add”<\/em><\/strong> \u00e9 usada para adicionar um elemento ao filtro, enquanto a fun\u00e7\u00e3o “contains”<\/strong><\/em> \u00e9 usada para verificar se um elemento est\u00e1 presente no filtro. O n\u00famero de elementos e a probabilidade de falso positivo podem ser ajustados ao criar uma nova inst\u00e2ncia da classe “BloomFilter<\/em><\/strong>“.<\/p>\n\n\n\n
Exemplo de c\u00f3digo em Java<\/h3>\n\n\n\n
Java<\/span><\/path><\/path><\/svg><\/span>
import<\/span> <\/span>java<\/span>.<\/span>util<\/span>.<\/span>BitSet<\/span>;<\/span><\/span>\nimport<\/span> <\/span>java<\/span>.<\/span>util<\/span>.<\/span>Random<\/span>;<\/span><\/span>\n<\/span>\npublic<\/span> <\/span>class<\/span> <\/span>BloomFilter<\/span> <\/span>{<\/span><\/span>\n    <\/span>private<\/span> <\/span>BitSet<\/span> <\/span>bitSet<\/span>;<\/span><\/span>\n    <\/span>private<\/span> <\/span>int<\/span> <\/span>numHashFunctions<\/span>;<\/span><\/span>\n    <\/span>private<\/span> <\/span>Random<\/span> <\/span>random<\/span>;<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>BloomFilter<\/span>(<\/span>int<\/span> <\/span>numElements<\/span>,<\/span> <\/span>double<\/span> <\/span>falsePositiveProbability<\/span>)<\/span> <\/span>{<\/span><\/span>\n        <\/span>int<\/span> <\/span>bitSetSize<\/span> <\/span>=<\/span> <\/span>(<\/span>int<\/span>)<\/span> <\/span>Math<\/span>.<\/span>ceil<\/span>(<\/span>-<\/span>numElements <\/span>*<\/span> <\/span>Math<\/span>.<\/span>log<\/span>(<\/span>falsePositiveProbability<\/span>)<\/span> <\/span>\/<\/span> <\/span>Math<\/span>.<\/span>pow<\/span>(<\/span>Math<\/span>.<\/span>log<\/span>(<\/span>2<\/span>),<\/span> <\/span>2<\/span>))<\/span>;<\/span><\/span>\n        <\/span>int<\/span> <\/span>numHashFunctions<\/span> <\/span>=<\/span> <\/span>(<\/span>int<\/span>)<\/span> <\/span>Math<\/span>.<\/span>ceil<\/span>((<\/span>bitSetSize <\/span>\/<\/span> numElements<\/span>)<\/span> <\/span>*<\/span> <\/span>Math<\/span>.<\/span>log<\/span>(<\/span>2<\/span>))<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>this<\/span>.<\/span>bitSet<\/span> <\/span>=<\/span> <\/span>new<\/span> <\/span>BitSet<\/span>(<\/span>bitSetSize<\/span>)<\/span>;<\/span><\/span>\n        <\/span>this<\/span>.<\/span>numHashFunctions<\/span> <\/span>=<\/span> numHashFunctions<\/span>;<\/span><\/span>\n        <\/span>this<\/span>.<\/span>random<\/span> <\/span>=<\/span> <\/span>new<\/span> <\/span>Random<\/span>()<\/span>;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>private<\/span> <\/span>int<\/span>[]<\/span> <\/span>getHashValues<\/span>(<\/span>String<\/span> <\/span>input<\/span>)<\/span> <\/span>{<\/span><\/span>\n        <\/span>int<\/span>[]<\/span> <\/span>hashValues<\/span> <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[<\/span>numHashFunctions<\/span>]<\/span>;<\/span><\/span>\n        <\/span>int<\/span> <\/span>hash1<\/span> <\/span>=<\/span> <\/span>input<\/span>.<\/span>hashCode<\/span>()<\/span>;<\/span><\/span>\n        <\/span>int<\/span> <\/span>hash2<\/span> <\/span>=<\/span> <\/span>random<\/span>.<\/span>nextInt<\/span>()<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>for<\/span> <\/span>(<\/span>int<\/span> <\/span>i<\/span> <\/span>=<\/span> <\/span>0<\/span>;<\/span> i <\/span><<\/span> numHashFunctions<\/span>;<\/span> i<\/span>++<\/span>)<\/span> <\/span>{<\/span><\/span>\n            hashValues<\/span>[<\/span>i<\/span>]<\/span> <\/span>=<\/span> <\/span>Math<\/span>.<\/span>abs<\/span>((<\/span>hash1 <\/span>+<\/span> i <\/span>*<\/span> hash2<\/span>)<\/span> <\/span>%<\/span> <\/span>bitSet<\/span>.<\/span>size<\/span>())<\/span>;<\/span><\/span>\n        <\/span>}<\/span><\/span>\n<\/span>\n        <\/span>return<\/span> hashValues<\/span>;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>add<\/span>(<\/span>String<\/span> <\/span>input<\/span>)<\/span> <\/span>{<\/span><\/span>\n        <\/span>int<\/span>[]<\/span> <\/span>hashValues<\/span> <\/span>=<\/span> <\/span>getHashValues<\/span>(<\/span>input<\/span>)<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>for<\/span> <\/span>(<\/span>int<\/span> <\/span>hash<\/span> <\/span>:<\/span> hashValues<\/span>)<\/span> <\/span>{<\/span><\/span>\n            <\/span>bitSet<\/span>.<\/span>set<\/span>(<\/span>hash<\/span>)<\/span>;<\/span><\/span>\n        <\/span>}<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>boolean<\/span> <\/span>contains<\/span>(<\/span>String<\/span> <\/span>input<\/span>)<\/span> <\/span>{<\/span><\/span>\n        <\/span>int<\/span>[]<\/span> <\/span>hashValues<\/span> <\/span>=<\/span> <\/span>getHashValues<\/span>(<\/span>input<\/span>)<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>for<\/span> <\/span>(<\/span>int<\/span> <\/span>hash<\/span> <\/span>:<\/span> hashValues<\/span>)<\/span> <\/span>{<\/span><\/span>\n            <\/span>if<\/span> <\/span>(<\/span>!<\/span>bitSet<\/span>.<\/span>get<\/span>(<\/span>hash<\/span>))<\/span> <\/span>{<\/span><\/span>\n                <\/span>return<\/span> <\/span>false;<\/span><\/span>\n            <\/span>}<\/span><\/span>\n        <\/span>}<\/span><\/span>\n<\/span>\n        <\/span>return<\/span> <\/span>true;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/\/ Fonte: ChatGPT<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
Este c\u00f3digo implementa um BloomFilter<\/em> usando um “BitSet”<\/em><\/strong> para armazenar os valores booleanos. A fun\u00e7\u00e3o de hash utilizada \u00e9 uma fun\u00e7\u00e3o simples baseada no “hashCode<\/strong>“<\/em> do objeto de entrada, que \u00e9 iterada v\u00e1rias vezes para obter v\u00e1rias fun\u00e7\u00f5es de hash<\/em>. A fun\u00e7\u00e3o “add”<\/em><\/strong>\u00e9 usada para adicionar um elemento ao filtro, enquanto a fun\u00e7\u00e3o “contains<\/em>“<\/strong> \u00e9 usada para verificar se um elemento est\u00e1 presente no filtro. O n\u00famero de elementos e a probabilidade de falso positivo podem ser ajustados ao criar uma nova inst\u00e2ncia da classe “BloomFilter”<\/em><\/strong>.<\/p>\n\n\n\n
Bibliotecas dispon\u00edveis<\/h3>\n\n\n\n
Existem diversas bibliotecas dispon\u00edveis para facilitar a implementa\u00e7\u00e3o do BloomFilter<\/em>. Algumas das mais populares incluem a bloom_filter<\/em><\/strong><\/code> para Python<\/em>, a Guava<\/strong><\/em><\/code> para Java<\/em> e a bloom<\/strong><\/em><\/code> para Go<\/em>.<\/p>\n\n\n\n
Melhorando o desempenho de aplica\u00e7\u00f5es com BloomFilter<\/h2>\n\n\n\n
Escolhendo os par\u00e2metros corretos<\/h3>\n\n\n\n
Para obter o melhor desempenho do BloomFilter<\/em>, \u00e9 importante escolher os par\u00e2metros corretos, como o tamanho do vetor de bits e o n\u00famero de fun\u00e7\u00f5es de hash<\/em>. Esses par\u00e2metros devem ser ajustados com base no tamanho do conjunto e na taxa de falsos positivos desejada.<\/p>\n\n\n\n
Integrando com outras estruturas de dados<\/h3>\n\n\n\n
O BloomFilter<\/em> pode ser integrado com outras estruturas de dados, como tabelas hash<\/em> ou \u00e1rvores de busca, para melhorar ainda mais o desempenho das aplica\u00e7\u00f5es. Isso pode ser \u00fatil para combinar a efici\u00eancia de espa\u00e7o e tempo do BloomFilter<\/em> com a capacidade de armazenamento e recupera\u00e7\u00e3o de outras estruturas de dados.<\/p>\n\n\n\n
Limita\u00e7\u00f5es e solu\u00e7\u00f5es alternativas<\/h2>\n\n\n\n
Falsos positivos<\/h3>\n\n\n\n
Uma das limita\u00e7\u00f5es do BloomFilter<\/em> \u00e9 a possibilidade de falsos positivos, ou seja, quando o filtro indica que um elemento est\u00e1 presente no conjunto, mesmo que ele n\u00e3o esteja. A taxa de falsos positivos pode ser minimizada ajustando os par\u00e2metros corretamente, mas nunca ser\u00e1 completamente eliminada.<\/p>\n\n\n\n
Gerenciamento de capacidade<\/h3>\n\n\n\n
Outra limita\u00e7\u00e3o do BloomFilter<\/em> \u00e9 a dificuldade de gerenciar a capacidade. Quando o conjunto de elementos cresce al\u00e9m do tamanho previsto, a taxa de falsos positivos tamb\u00e9m aumenta. Uma solu\u00e7\u00e3o para esse problema \u00e9 usar filtros de Bloom<\/em> escal\u00e1veis, que podem ser expandidos dinamicamente \u00e0 medida que a capacidade \u00e9 necess\u00e1ria.<\/p>\n\n\n\n
Concluindo: BloomFilter como uma estrutura de dados vers\u00e1til e indispens\u00e1vel<\/h2>\n\n\n\n
O BloomFilter<\/em> \u00e9 uma estrutura de dados eficiente e vers\u00e1til que pode ser usada para melhorar o desempenho de v\u00e1rias aplica\u00e7\u00f5es. Ao entender seu funcionamento, vantagens e limita\u00e7\u00f5es, \u00e9 poss\u00edvel implement\u00e1-lo de forma eficaz e obter resultados significativos em termos de efici\u00eancia de espa\u00e7o e tempo.<\/p>\n\n\n\n
Esse conte\u00fado \u00e9 parte do material disponibilizado para os participantes do meu grupo de estudos de Algoritmos e Estruturas de Dados<\/strong>. Voc\u00ea quer participar desse grupo? Clique aqui e veja como funciona<\/a><\/strong>.<\/p>\n\n\n\n
D\u00favidas Frequentes<\/h2>\n\n\n\n
O que \u00e9 um BloomFilter<\/em>?<\/strong>
\u00c9 uma estrutura de dados probabil\u00edstica que permite verificar a exist\u00eancia de elementos em um conjunto de forma eficiente em termos de espa\u00e7o e tempo.<\/p>\n\n\n\n
Quais s\u00e3o as principais vantagens do BloomFilter<\/em>?<\/strong>
As principais vantagens s\u00e3o a efici\u00eancia de espa\u00e7o e tempo, permitindo opera\u00e7\u00f5es r\u00e1pidas de inser\u00e7\u00e3o e consulta com o uso m\u00ednimo de mem\u00f3ria.<\/p>\n\n\n\n
Em quais aplica\u00e7\u00f5es o BloomFilter<\/em> pode ser utilizado?<\/strong>
O BloomFilter<\/em> pode ser usado em v\u00e1rias aplica\u00e7\u00f5es, como verifica\u00e7\u00e3o de exist\u00eancia, filtragem de spam e otimiza\u00e7\u00e3o de sistemas de cache.<\/p>\n\n\n\n
Quais s\u00e3o as limita\u00e7\u00f5es do BloomFilter<\/em>?<\/strong>
As principais limita\u00e7\u00f5es s\u00e3o a possibilidade de falsos positivos e a dificuldade de gerenciar a capacidade quando o conjunto de elementos cresce al\u00e9m do tamanho previsto.<\/p>\n\n\n\n
Como escolher os par\u00e2metros corretos para um BloomFilter<\/em>?<\/strong>
Os par\u00e2metros, como o tamanho do vetor de bits<\/em> e o n\u00famero de fun\u00e7\u00f5es de hash<\/em>, devem ser ajustados com base no tamanho do conjunto e na taxa de falsos positivos desejada.<\/p>\n","protected":false},"featured_media":4475,"parent":0,"template":"","cursos":[5],"class_list":["post-4474","artigos","type-artigos","status-publish","has-post-thumbnail","hentry","cursos-algortimos"],"acf":[],"_links":{"self":[{"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/artigos\/4474","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/artigos"}],"about":[{"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/types\/artigos"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/media\/4475"}],"wp:attachment":[{"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/media?parent=4474"}],"wp:term":[{"taxonomy":"cursos","embeddable":true,"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/cursos?post=4474"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}