bloom_filter.cpp File Reference

Bloom Filter generic implementation in C++ More...

#include <cassert>
#include <functional>
#include <initializer_list>
#include <string>
#include <vector>
#include <iostream>

Include dependency graph for bloom_filter.cpp:

Classes
class	data_structures::Bitset
	Simple bitset implementation for bloom filter. More...
class	data_structures::BloomFilter< T >
	Bloom filter template class. More...

Namespaces
namespace	data_structures
	for IO operations

Functions
static std::size_t	data_structures::hashDJB2 (std::string const &s)
	Function djb2 to get hash for the given string.
static std::size_t	data_structures::hashStr (std::string const &s)
	Hash function, to get hash for the given string.
std::size_t	data_structures::hashInt_1 (int x)
	Hash function for test
std::size_t	data_structures::hashInt_2 (int x)
	Hash function for test
static void	test_bloom_filter_string ()
	Test for bloom filter with string as generic type.
static void	test_bloom_filter_int ()
	Test for bloom filter with int as generic type.
static void	test_bitset ()
	Test for bitset.
int	main ()
	Main function.

Detailed Description

Bloom Filter generic implementation in C++

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

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

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

           {
    // 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;
}

Here is the call graph for this function:

test_bitset()

static void test_bitset ( )

static

Test for bitset.

Returns

void

                          {
    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);
}

Here is the call graph for this function:

test_bloom_filter_int()

static void test_bloom_filter_int ( )

static

Test for bloom filter with int as generic type.

Returns

void

                                    {
    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));
    }
}

Here is the call graph for this function:

test_bloom_filter_string()

static void test_bloom_filter_string ( )

static

Test for bloom filter with string as generic type.

Returns

void

                                       {
    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));
    }
}

Here is the call graph for this function: