{"id":7413,"date":"2024-09-23T15:44:10","date_gmt":"2024-09-23T15:44:10","guid":{"rendered":"https:\/\/paybis.com\/blog\/?post_type=glossary&p=7413"},"modified":"2024-09-23T15:44:11","modified_gmt":"2024-09-23T15:44:11","slug":"bloom-filter","status":"publish","type":"glossary","link":"https:\/\/paybis.com\/blog\/glossary\/bloom-filter\/","title":{"rendered":"Bloom Filter"},"content":{"rendered":"\n

<\/a>What is a Bloom Filter?<\/h2>\n\n\n\n

A blloom filter is a fast and effective tool that\u2019s used in computer science to verify elements in a list, without using a lot of memory. However, even though bloom filters are time and memory-efficient, they can produce false positives. They might mistakenly claim an object is contained within the set when it isn\u2019t.<\/p>\n\n\n\n

Still, unlike other data structures, bloom filters don\u2019t produce false-negative responses, meaning they always provide correct answers. This makes is highly reliable for list verifications.<\/p>\n\n\n\n

<\/a>How a Bloom Filter Works<\/h2>\n\n\n\n

Understanding how a Bloom Filter works involves several key components and steps. Here\u2019s a brief rundown:<\/p>\n\n\n\n

<\/a>1. Initialization<\/h3>\n\n\n\n

A bloom filter is represented as a bit array of size m, initially, all set to 0. It uses k independent hash functions, each of which maps an element to one of the m array positions with a uniform random distribution.<\/p>\n\n\n\n

<\/a>2. Adding an Element<\/h3>\n\n\n\n

When an element is added to the bloom filter, it is passed through each of the k hash functions<\/a>. Each hash function produces an index corresponding to a position in the bit array. The bits at all k positions are set to 1.<\/p>\n\n\n\n

<\/a>3. Checking Membership<\/h3>\n\n\n\n

To check if an element is in the set, the element is hashed using the same k hash functions. If all the bits at the k hash positions are 1, the element is considered to be in the set (with a probability of false positive). If any bit at the k position is 0, the element is not in the set.<\/p>\n\n\n\n

<\/a>Example of Bloom Filter Operations<\/h2>\n\n\n\n

Consider a Bloom Filter with a bit array of size 10 and 3 hash functions.<\/p>\n\n\n\n

<\/a>Adding Elements:<\/h3>\n\n\n\n