The Algorithms logo
The Algorithms
AboutDonate

Bloom Filter

S
A
O
D
/**
 * @file
 * @brief [Bloom Filter](https://en.wikipedia.org/wiki/Bloom_filter)
 * generic implementation in C++
 * @details A Bloom filter is a space-efficient probabilistic data structure,
 * a query returns either "possibly in set" or "definitely not in set".
 *
 * More generally, fewer than 10 bits per element are required for a 1% false
 * positive probability, independent of the size or number of elements in the
 * set.
 *
 * It helps us to not make an "expensive operations", like disk IO - we can
 * use bloom filter to check incoming request, and with a good probability
 * get an answer of bloom filter, that we don't need to make our "expensive
 * operation"
 *
 *
 * [Very good use case example](https://stackoverflow.com/a/30247022)
 *
 * Basic bloom filter doesn't support deleting of elements, so
 * we don't need to implement deletion in bloom filter and bitset in our case.
 * @author [DanArmor](https://github.com/DanArmor)
 */

#include <cassert>           /// for assert
#include <functional>        /// for list of hash functions for bloom filter constructor
#include <initializer_list>  /// for initializer_list for bloom filter constructor
#include <string>            /// for testing on strings
#include <vector>            /// for std::vector
#include <iostream>          /// for IO operations

/**
 * @namespace data_structures
 * @brief Data Structures algorithms
 */
namespace data_structures {
/**
 * @brief Simple bitset implementation for bloom filter
 */
class Bitset {
 private:
    std::vector<std::size_t> data;  ///< short info of this variable
    static const std::size_t blockSize =
        sizeof(std::size_t);  ///< size of integer type, that we are using in
                              ///< our bitset
 public:
    explicit Bitset(std::size_t);
    std::size_t size();
    void add(std::size_t);
    bool contains(std::size_t);
};

/**
 * @brief Utility function to return the size of the inner array
 * @returns the size of inner array
 */
std::size_t Bitset::size() { return data.size(); }

/**
 * @brief BitSet class constructor
 * @param initSize amount of blocks, each contain sizeof(std::size_t) bits
 */
Bitset::Bitset(std::size_t initSize) : data(initSize) {}

/**
 * @brief Turn bit on position x to 1s
 *
 * @param x position to turn bit on
 * @returns void
 */
void Bitset::add(std::size_t x) {
    std::size_t blockIndex = x / blockSize;
    if (blockIndex >= data.size()) {
        data.resize(blockIndex + 1);
    }
    data[blockIndex] |= 1 << (x % blockSize);
}

/**
 * @brief Doest bitset contains element x
 *
 * @param x position in bitset to check
 * @returns true if bit position x is 1
 * @returns false if bit position x is 0
 */
bool Bitset::contains(std::size_t x) {
    std::size_t blockIndex = x / blockSize;
    if (blockIndex >= data.size()) {
        return false;
    }
    return data[blockIndex] & (1 << (x % blockSize));
}

/**
 * @brief Bloom filter template class
 * @tparam T type of elements that we need to filter
 */
template <typename T>
class BloomFilter {
 private:
    Bitset set;  ///< inner bitset for elements
    std::vector<std::function<std::size_t(T)>>
        hashFunks;  ///< hash functions for T type

 public:
    BloomFilter(std::size_t,
                std::initializer_list<std::function<std::size_t(T)>>);
    void add(T);
    bool contains(T);
};

/**
 * @brief Constructor for Bloom filter
 *
 * @tparam T type of elements that we need to filter
 * @param size initial size of Bloom filter
 * @param funks hash functions for T type
 * @returns none
 */
template <typename T>
BloomFilter<T>::BloomFilter(
    std::size_t size,
    std::initializer_list<std::function<std::size_t(T)>> funks)
    : set(size), hashFunks(funks) {}

/**
 * @brief Add function for Bloom filter
 *
 * @tparam T type of elements that we need to filter
 * @param x element to add to filter
 * @returns void
 */
template <typename T>
void BloomFilter<T>::add(T x) {
    for (std::size_t i = 0; i < hashFunks.size(); i++) {
        set.add(hashFunks[i](x) % (sizeof(std::size_t) * set.size()));
    }
}

/**
 * @brief Check element function for Bloom filter
 *
 * @tparam T type of elements that we need to filter
 * @param x element to check in filter
 * @return true if the element probably appears in the filter
 * @return false if the element certainly does not appear in the filter
 */
template <typename T>
bool BloomFilter<T>::contains(T x) {
    for (std::size_t i = 0; i < hashFunks.size(); i++) {
        if (set.contains(hashFunks[i](x) %
                         (sizeof(std::size_t) * set.size())) == false) {
            return false;
        }
    }
    return true;
}

/**
 * @brief [Function djb2](http://www.cse.yorku.ca/~oz/hash.html)
 * to get hash for the given string.
 *
 * @param s string to get hash from
 * @returns hash for a string
 */
static std::size_t hashDJB2(std::string const& s) {
    std::size_t hash = 5381;
    for (char c : s) {
        hash = ((hash << 5) + hash) + c;
    }
    return hash;
}

/**
 * @brief [Hash
 * function](https://stackoverflow.com/questions/8317508/hash-function-for-a-string),
 * to get hash for the given string.
 *
 * @param s string to get hash from
 * @returns hash for the given string
 */
static std::size_t hashStr(std::string const& s) {
    std::size_t hash = 37;
    std::size_t primeNum1 = 54059;
    std::size_t primeNum2 = 76963;
    for (char c : s) {
        hash = (hash * primeNum1) ^ (c * primeNum2);
    }
    return hash;
}

/**
 * @brief [Hash function for
 * test](https://stackoverflow.com/questions/664014/what-integer-hash-function-are-good-that-accepts-an-integer-hash-key)
 *
 * @param x to get hash from
 * @returns hash for the `x` parameter
 */
std::size_t hashInt_1(int x) {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = (x >> 16) ^ x;
    return x;
}

/**
 * @brief [Hash function for
 * test](https://stackoverflow.com/questions/664014/what-integer-hash-function-are-good-that-accepts-an-integer-hash-key)
 *
 * @param x to get hash from
 * @returns hash for the `x` parameter
 */
std::size_t hashInt_2(int x) {
    auto y = static_cast<std::size_t>(x);
    y = (y ^ (y >> 30)) * static_cast<std::size_t>(0xbf58476d1ce4e5b9);
    y = (y ^ (y >> 27)) * static_cast<std::size_t>(0x94d049bb133111eb);
    y = y ^ (y >> 31);
    return y;
}
}  // namespace data_structures

/**
 * @brief Test for bloom filter with string as generic type
 * @returns void
 */
static void test_bloom_filter_string() {
    data_structures::BloomFilter<std::string> filter(
        10, {data_structures::hashDJB2, data_structures::hashStr});
    std::vector<std::string> toCheck{"hello", "world", "!"};
    std::vector<std::string> toFalse{"false", "world2", "!!!"};
    for (auto& x : toCheck) {
        filter.add(x);
    }
    for (auto& x : toFalse) {
        assert(filter.contains(x) == false);
    }
    for (auto& x : toCheck) {
        assert(filter.contains(x));
    }
}

/**
 * @brief Test for bloom filter with int as generic type
 * @returns void
 */
static void test_bloom_filter_int() {
    data_structures::BloomFilter<int> filter(
        20, {data_structures::hashInt_1, data_structures::hashInt_2});
    std::vector<int> toCheck{100, 200, 300, 50};
    std::vector<int> toFalse{1, 2, 3, 4, 5, 6, 7, 8};
    for (int x : toCheck) {
        filter.add(x);
    }
    for (int x : toFalse) {
        assert(filter.contains(x) == false);
    }
    for (int x : toCheck) {
        assert(filter.contains(x));
    }
}

/**
 * @brief Test for bitset
 *
 * @returns void
 */
static void test_bitset() {
    data_structures::Bitset set(2);
    std::vector<std::size_t> toCheck{0, 1, 5, 8, 63, 64, 67, 127};
    for (auto x : toCheck) {
        set.add(x);
        assert(set.contains(x));
    }
    assert(set.contains(128) == false);
    assert(set.contains(256) == false);
}

/**
 * @brief Main function
 * @returns 0 on exit
 */
int main() {
    // run self-test implementations

    test_bitset();  // run test for bitset, because bloom filter is depending on it
    test_bloom_filter_string();
    test_bloom_filter_int();
    
    std::cout << "All tests have successfully passed!\n";
    return 0;
}
About this Algorithm

Bloom Filters are one of a class of probabilistic data structures. The Bloom Filter uses hashes and probability to determine whether a particular item is present in a set. It can do so in constant time: O(1) and sub-linear space, though technically still O(n). An important feature of a Bloom Filter is that it is guaranteed never to provide a false negative, saying an element isn't present when it is. However, it has a probability (based on the tuning of its parameters) of providing a false positive, saying an element is present when it is not. The Bloom Filter uses a multi-hash scheme. On insertion, the inserted object is run through each hash, which produces a slot number. That slot number is flipped to 1 in the bit array. During a presence check, the object is run through the same set of hashes, and if each corresponding slot is 1, the filter reports the object has been added. If any of them are 0, it reports that the object has not been added. The hashes must be deterministic and uniformly distributed over the slots for the Bloom filter to operate effectively.

Complexity

Operation Average
Initialize O(1)
Insertion O(1)
Query O(1)
Space O(n)

Steps

Initialization

  1. Bloom Filter is Initialized, with a number of hash functions that will be run against it (henceforth known as k), and with an array of bits of size M with each bit set to 0. There are 3 distinct schemes to tune these parameters.
    1. M and k are explicitly set by the user
    2. k and M are calculated based off the expected number of elements to minimize false positives.
    3. k and M are calculated based off a desired error rate.

Insertion

  1. Object is run through k hashes
  2. For each result of the hash n determine the slot within the filter m by calculating n % M = m
  3. Set slot m within the filter to 1

Query

  1. Object is run through k hashes
  2. For each result of the hash n determine the slot within the filter m by calculating n % M = m
  3. Check slot m, if m is set to 0 return false
  4. Return true

Example

Initialize

As an example, let us look at a Bloom Filter of Strings, we will initialize the Bloom Filter with 10 slots an we will use 3 hashes

slot 0 1 2 3 4 5 6 7 8 9
state 0 0 0 0 0 0 0 0 0 0

Insert

Let's try to insert foo, we will run foo through our three hash functions

h1(foo) = 2
h2(foo) = 5
h3(foo) = 6

With hashes run, we will flip the corresponding bits to 1

slot 0 1 2 3 4 5 6 7 8 9
state 0 0 1 0 0 1 1 0 0 0

Query

Query bar

Let's first try querying bar, to query bar we run bar through our three hash functions:

h1(bar) = 3
h2(bar) = 4
h3(bar) = 6

If we look at our bit array, bits 3 and 4 are both not set, if even just 1 bit is not set, we return false, so in this case we return false. bar has not been added

Query foo

Let's now try to query foo, when we run foo through our hashes we get:

h1(foo) = 2
h2(foo) = 5
h3(foo) = 6

Of course, since we already inserted foo, our table has each of the three bits our hashes produced set to 1, so we return true, foo is present

False Positive

Let's say we inserted bar and the current state of our table is:

slot 0 1 2 3 4 5 6 7 8 9
state 0 0 1 1 1 1 1 0 0 0

Let's now query baz, when we run baz through our hash functions we get:

h1(baz) = 3
h2(baz) = 5
h3(baz) = 6

Notice that this does not match either the result of foo or bar, however because slots 3, 5, and 6 are already set, we report true, that baz is in the set, and therefore produce a false positive.

Advantage Over HashSets

  • Significantly more space-efficient, Both are technically O(n) space complexity, but since bloom filters will only take up several bits per item, hash sets must hold the entire item.
  • Presence checks are guaranteed to be O(1) for Bloom Filters, for HashSets, the average is O(1), but worst case is O(n)

Disadvantage v.s. Hash Sets

  • Bloom Filters can report false positives. Optimally there should be about a 1% false-positive rate.
  • Bloom Filters do not store the objects inserted into it, so you cannot recover items inserted.

Optimizing

The probability of false positives increases with the probability of hash collisions within the filter. However, you can optimize the number of collisions if you have some sense of the cardinality of your set ahead of time. You can do this by optimizing k and M, M should be ~ 8-10 bits per expected item, and k should be (M/n) * ln2.

Examples

Implementations of the Bloom Filter are available for:

Video Explainer

Video Explainer by Narendra L