The Magic of Bloom Filters: A Probabilistic Data Structure for Checking Username Existence

6 min readJun 26, 2023

Have you ever wondered how computer programs quickly determine if a username already exists? Well, they often use a clever and efficient probabilistic data structure called a Bloom filter.

In this blog, we will explore Bloom filters, understand their probabilistic nature, and learn how they work by using the example of checking if a username exists or not.

What is a Bloom filter?

A Bloom filter is a special kind of data structure that allows us to quickly check if an item is a member of a set. It provides us with two possible answers: “definitely not in the set” or “maybe in the set.” However, it is important to note that Bloom filters have a probabilistic nature and can sometimes provide false positives.

Why we need bloom filters?

Bloom filters are useful in situations where we need to quickly check if an item might exist in a large set, while minimizing the amount of memory required.

They provide a way to perform approximate existence checks with a trade-off of a small chance of false positives. Here’s an example to illustrate the need for Bloom filters:

Imagine you have a social media website with millions of registered users. Whenever a new user signs up, you want to ensure that their chosen username is unique and doesn’t already exist in your database.

One approach might be to store all the usernames in a list and perform a linear search every time a new user signs up. However, with millions of usernames, this can become slow and resource-intensive.

Here’s where a Bloom filter comes to the rescue. Instead of storing the entire list of usernames, you can create a Bloom filter with a much smaller memory footprint. When a user signs up, you can quickly check if their chosen username might already exist in the set by querying the Bloom filter.

If the Bloom filter says the username is not in the set, you can allow the user to proceed. However, if the Bloom filter indicates a potential match, you can perform a secondary, more accurate check using a traditional data structure (e.g., a hash table) to confirm the username’s existence.

Example: Checking if a username exists

Let’s imagine we have a website where users can create accounts with unique usernames. To ensure that no two users have the same username, we can utilize a Bloom filter to quickly check if a username already exists.

👉 Setting up the Bloom filter: First, we create an empty Bloom filter with multiple compartments or “buckets.” Each bucket is initially empty and represented by a single bit. The more buckets we have, the lower the chance of false positives, but the larger the Bloom filter becomes in memory.
👉Adding usernames: As new users sign up, we hash their usernames using multiple hash functions. Each hash function generates a unique index in the Bloom filter. We then set the corresponding bits at those indexes to 1, indicating the presence of a username.
👉Checking if a username exists: Now, let’s say a user named John wants to sign up. Before we allow John to create an account, we perform a lookup in the Bloom filter. We hash John using the same hash functions and check the corresponding bits in the Bloom filter. If any of the bits are not set to 1, we can be certain that John does not exist in the username set. However, if all the bits are set to 1, we have a “maybe” scenario, and further verification is required.
👉Handling false positives: One of the interesting aspects of Bloom filters is that they can produce false positives but never false negatives. A false positive occurs when the Bloom filter indicates that a username exists, even though it might not be present in the actual username set. To mitigate this, we usually employ additional data structures, such as a traditional hash table, to store the actual usernames. If the Bloom filter suggests a potential match, we cross-verify the username in the hash table to confirm its existence.

Implementation of a Bloom filter in JavaScript

we define a BloomFilter class with the specified size and number of hash functions in the constructor. The bitArray is an array of booleans representing the Bloom filter's bits.

The add method adds an item (username) to the Bloom filter by calculating the hash values using the getHashValues method and setting the corresponding bits in the bitArray to true.

The contains method checks if an item (username) might exist in the Bloom filter. It retrieves the hash values using the getHashValues method and checks if all the corresponding bits in the bitArray are true. If any bit is false, it means the item is definitely not in the filter.

The getHashValues method generates multiple hash values for an item using a simple custom hash function. We append a number (0 to numHashFunctions - 1) to the item to create unique hash values.

The hash method is a custom hash function that calculates a hash value for a string.

In the example usage, we create a BloomFilter instance with a size of 100 and two hash functions. We add some usernames ("amy," "john," and "emma") to the Bloom filter using the add method. Finally, we check if the username "john" might exist in the Bloom filter using the contains method and print the appropriate message.

class BloomFilter {
  constructor(size, numHashFunctions) {
    this.size = size;
    this.numHashFunctions = numHashFunctions;
    this.bitArray = new Array(size).fill(false);
  }

  add(item) {
    const hashValues = this.getHashValues(item);
    hashValues.forEach((hashValue) => {
      this.bitArray[hashValue] = true;
    });
  }

  contains(item) {
    const hashValues = this.getHashValues(item);
    for (let i = 0; i < hashValues.length; i++) {
      if (!this.bitArray[hashValues[i]]) {
        return false;
      }
    }
    return true;
  }

  getHashValues(item) {
    const hashValues = [];
    for (let i = 0; i < this.numHashFunctions; i++) {
      const hash = this.hash(`${item}${i}`);
      const index = hash % this.size;
      hashValues.push(index);
    }
    return hashValues;
  }

  hash(item) {
    let hash = 0;
    for (let i = 0; i < item.length; i++) {
      hash = (hash << 5) + hash + item.charCodeAt(i);
      hash = hash & hash; // Convert to 32bit integer
      hash = Math.abs(hash);
    }
    return hash;
  }
}

// Example usage
const bloomFilter = new BloomFilter(100, 2);

// Adding usernames to the Bloom filter
bloomFilter.add("amy");
bloomFilter.add("john");
bloomFilter.add("emma");

// Checking if a username exists
const username = "john";
if (bloomFilter.contains(username)) {
  console.log(`The username '${username}' may exist.`);
} else {
  console.log(`The username '${username}' does not exist.`);
}

This custom implementation provides a basic understanding of how a Bloom filter works, but in practice, you might need to consider more robust hash functions, tuning parameters based on expected false positive rates, and other optimizations.

Benefits of using a Bloom filter

Space efficiency: Bloom filters require much less memory compared to storing the entire set of usernames.
Fast membership checks: Bloom filters provide constant-time lookups, allowing for quick existence checks.
Reduced resource usage: By using a Bloom filter as a preliminary check, you can avoid unnecessary database queries, saving processing power and database load.

Though Bloom filters may occasionally produce false positives (indicating an item is present when it’s not), they offer an efficient and scalable solution for approximate membership queries in large datasets.

By combining Bloom filters with secondary verification methods, we can achieve a balance between speed and accuracy, making them valuable tools in scenarios where approximate existence checks are acceptable and resource optimization is crucial.

Conclusion

Bloom filters are powerful probabilistic data structures that enable efficient membership checking. They find wide applications in scenarios where quick existence checks are required, such as determining username availability.

While Bloom filters provide fast responses, we should be aware that they can occasionally produce false positives. By combining Bloom filters with other data structures, we can achieve higher accuracy and ensure the reliability of our operations.

Bloom filters continue to be an invaluable tool in computer science, simplifying complex tasks and enhancing performance in various applications.