{"id":1861,"date":"2019-01-01T12:00:00","date_gmt":"2019-01-01T11:00:00","guid":{"rendered":"https:\/\/kindsonthegenius.com\/blog\/how-bloom-filters-work\/"},"modified":"2026-07-05T03:20:58","modified_gmt":"2026-07-05T01:20:58","slug":"how-bloom-filters-work","status":"publish","type":"post","link":"https:\/\/kindsonthegenius.com\/blog\/how-bloom-filters-work\/","title":{"rendered":"Bloom Filters \u2013 A Clear Explanation of How They Work"},"content":{"rendered":"

We would cover the following:<\/p>\n

    \n
  1. Introduction to Bloom Filters<\/a><\/li>\n
  2. Applications of Bloom Filters<\/a><\/li>\n
  3. How Bloom Filters Work<\/a><\/li>\n
  4. Bloom Filter Setup<\/a><\/li>\n
  5. Analysis of Bloom Filters<\/a><\/li>\n
  6. Watch the Video<\/a><\/li>\n<\/ol>\n

    \"\"<\/p>\n

    1. Introduction to Bloom Filters<\/strong><\/p>\n

    A Bloom Filter is a a data structure (based on hashing) that lets us determine whether an element is a member of a set. In bloom filters, it is possible for false positive to occur but with low probability. But false negatives is not possible. It is a space efficient and probabilistic data structure.<\/p>\n

    Bloom filters allows us to used several hash functions for each key.<\/p>\n

     <\/p>\n

    2. Application of Bloom Filters<\/strong><\/p>\n

    A common application of bloom filters ins in caching. The browser maintains certain levels of caches carefully placed to speed up loading of web pages that are accessed frequently. If a user requests a particular URL, then the browser needs to determine if the requested page is already in one of the caches and then serves the page from the cache if it is there.<\/p>\n

    However, it may happen that the page may the reported to be in the cache while it is actually not there. This is called false positive. In this case, then fetches he page from the original url.\u00a0 Probability of this happening is small as we would see later.<\/p>\n

     <\/p>\n

    3. How Bloom Filters Work<\/strong><\/p>\n

    Remember that we mentioned that bloom filters are used to determine if an element is a member of a set.<\/p>\n

    So let’s assume we have a set of n elements S = {s1, s2, . . . , sn} which is taken from a very large universe U. (U may be a universe of all URLs and S is a set of urls existing in the cache). We want to allow for insertions into set S. Before insertion, the system checks if:<\/p>\n

    Given x\u00a0 \u2208\u00a0U, is x\u00a0\u2208 \u00a0 S?<\/p>\n

      \n
    • If the answer is No, then\u00a0 x is not in S (x \u2209\u00a0S)<\/li>\n
    • If the answer is Yes, then x may\u00a0 or may not be in S<\/li>\n<\/ul>\n

      The objective is to perform this query as well as insertion into the cache in constant time O(1)<\/p>\n

       <\/p>\n

      4. Bloom Filter Setup<\/strong><\/p>\n

      A bloom filter is a bit array of B of m bits and k independent hash functions, h1<\/sub>, . . . , hk<\/sub>. The has functions map each key in U to a set Rm<\/sub> = {0, 1, . . . , m-1}<\/p>\n

      We assume that each of the hash function hi<\/sub> maps a uniformly random key\u00a0 x\u00a0\u2208 \u00a0U to each element of Rm<\/sub> with equal probability.<\/p>\n

      Since the hash functions\u00a0h1<\/sub>, . . . , hk<\/sub> \u00a0are independent, then the result of the hashing, h1<\/sub>(x), . . . , hk<\/sub>(x) is equally likely to be any of the positions in Rm. All the m bits of B are initially set to 0. Therefore the process of insertion is as follows:<\/p>\n

      To Insert:\u00a0 Evaluate\u00a0 h1<\/sub>(x), . . . ,\u00a0hk<\/sub>(x) and set each of the bits to 1<\/p>\n

      To check is x\u00a0\u2208 S:\u00a0Evaluate\u00a0 h1<\/sub>(x), . . . ,\u00a0hk<\/sub>(x) . If all the bits are set to 1. then x\u00a0\u2208 \u00a0S else x\u00a0\u2209 S<\/p>\n

      This is illustrated in Figure 1.0<\/p>\n

      \"\"
      Figure 1.0: Bloom Filter. Initially all the bits are set to zero. Then we computer hk<\/sub>(x) and set the bits to 1 for each of the keys hk<\/sub>(x) maps to<\/figcaption><\/figure>\n

       <\/p>\n

      5. Analysis of Bloom Filters – Version 1<\/strong><\/p>\n

      In this version, we use k hash functions and k bit arrays.<\/p>\n

      To insert:<\/p>\n

        \n
      • h1<\/sub>(x) is stored in the first array<\/li>\n
      • h2<\/sub>(x is stored in the second array<\/li>\n
      • …<\/li>\n
      • hk<\/sub>(x) is stored in the kth<\/sup> array<\/li>\n<\/ul>\n

        To search:<\/p>\n

        Search hi<\/sub>(x) for each i and if hi<\/sub>(x) is not set to 1 for any i, then x is not in the set<\/p>\n

        Let’s now calculate the probability of false positive<\/p>\n

        Pr(false positive) occurs if h(y) = h(xi<\/sub>)\u00a0 where y\u00a0\u2209\u00a0 S. Probability that this happens is given by:<\/p>\n

        \"\"<\/p>\n

        We can also go ahead to calculate the number of bits required.<\/p>\n

         <\/p>\n

        6. Watch the Video<\/strong><\/p>\n