Introduction to Bloom Filter

-

 A Bloom filter is a probabilistic data structure used to test whether an element is possibly in a set or definitely not in a set.

It’s designed to be memory-efficient and very fast, but it allows false positives (saying an element might be in the set when it’s not) while guaranteeing no false negatives (if it says something is not in the set, it really isn’t).

How it works:

  1. You start with a bit array (all bits set to 0).

  2. You have k different hash functions.

  3. To add an item:

    • Compute its k hashes.

    • Set the corresponding k positions in the bit array to 1.

  4. To check if an item is in the set:

    • Compute its k hashes.

    • If all those positions are 1 → item might be in the set (possible false positive).

    • If any position is 0 → item is definitely not in the set.

Example:

  • Suppose you insert "cat".
    Hash functions map "cat" to positions [3, 7, 12], so you set those bits.

  • Later, you check "dog".
    Its hashes are [3, 12, 20]. Since positions 3 and 12 are already set (from "cat"), and 20 is also set (maybe by "fish"), the filter might say "dog" is in the set—even if you never added it.

Key properties:

  • Fast lookups: O(k) time (constant if k is fixed).

  • Space-efficient: Much smaller than storing full items.

  • No deletions (in the basic version, though variants like counting Bloom filters exist).

  • False positives possible, false negatives impossible.

Common use cases:

  • Web browsers: Checking if a URL is in a blacklist.

  • Databases: Quickly filtering out keys that aren’t present.

  • Networking: Cache membership checks, routing, etc.

  • Big data systems (e.g., Hadoop, Cassandra, Bitcoin).



Recommended articles:
https://www.baeldung.com/cs/bloom-filter 

Comments

Post a Comment

Popular posts from this blog

REST vs RPC vs GraphQL: Choosing the Right API Style

-
 APIs are the glue that connects modern applications. Whether you’re building a public-facing service or a complex microservices ecosystem, the design style of your API plays a huge role in performance, usability, and maintainability. Three common approaches dominate today’s landscape: REST , RPC , and GraphQL . Each comes from a different philosophy, and each has strengths and trade-offs. Let’s compare them. 1. REST (Representational State Transfer) REST treats everything as a resource and interacts with those resources using standard HTTP methods. It’s resource-oriented and built on the web’s existing semantics. Example : GET / users / 123 → fetch user 123 PUT / users / 123 → update user 123 GET / users / 123 / orders → fetch orders for user 123 ✅ Pros Standardized and predictable Widely supported by tools and libraries Leverages HTTP features (caching, status codes, headers) Great for resource-centric systems ❌ Cons ...
Read more

Fibonacci Agile Estimation

-
Image
  Most agile teams opt to combine the Fibonacci sequence with an estimation method called   planning poker . In Planning Poker, each team member has a modified deck of cards that corresponds with the Fibonacci sequence. When a task is up for estimation, each member individually picks a card that best matches their estimate for that item. Everyone then reveals their cards simultaneously and discusses their estimates until they reach a consensus. Why is the Fibonacci sequence used in agile estimation? The point of Fibonacci is to force your hand when estimating larger, complex tasks instead of wasting time nitpicking over minor differences . This is best explained through an example that compares simple time-based estimation with Fibonacci estimation. Let’s say you estimated your stories on a steady scale of 1-50.  When you discuss your backlog item with the team, one picks 31, the other 36, and a third 38. When the gap between each estimate is a single integer it’s hard to...
Read more

How to Add LICENSE.txt to Your .NET Project Using Azure Pipelines

-
Image
   Including a license file in your NuGet package is a best practice that improves transparency and compliance for your open-source or internal packages. If you store your   LICENSE.txt   securely in Azure DevOps, you can automate its inclusion into your .NET project using Azure Pipelines. In this guide, I’ll walk you through how to: Download the LICENSE.txt from Azure DevOps secure files Copy the file into your project directory Modify the .csproj file dynamically to include the license file during build and packaging 🔐 Step 1: Download  LICENSE.txt  from Secure Files First, upload your  LICENSE.txt  to the  Secure Files  library in Azure DevOps. Then, in your YAML pipeline, use the  DownloadSecureFile  task to fetch it at runtime. - task: DownloadSecureFile@1 displayName: 'Download LICENSE.txt' inputs: secureFile: 'LICENSE.txt' This will download the file to a temporary location on the build agent ( $(Agent.Te...
Read more