1
\$\begingroup\$

This is a bloom filter implementation in C++. To instantiate the BloomFilter class, supply it with the number of bool cells, and a HashFunction vector. The method addElement() adds a string to the set of strings the bloom filter test element membership against. The method searchElement() checks set membership against the aforementioned set.

#include <iostream>
#include <string>
#include <vector>
#include <iterator>


// bloom filter implementation

typedef unsigned int (*HashFunction)(std::string);

class BloomFilter {
    unsigned int numberOfCells;
    unsigned int numberOfFunctions;
    bool* cell;
    std::vector<HashFunction> hashFunctions;

public:

    BloomFilter(unsigned int numbCells, std::vector<HashFunction> funcs) : numberOfCells(numbCells), hashFunctions(funcs) {
        cell = (bool*)calloc(numbCells, sizeof(bool));
    }

    void addElement(std::string str) {
        for (std::vector<HashFunction>::iterator iter = hashFunctions.begin(); iter != hashFunctions.end(); iter++) {
            cell[(*iter)(str) % numberOfCells] = true;
        }
    }

    bool searchElement(std::string str) {
        bool strInSet = true;

        for (std::vector<HashFunction>::iterator iter = hashFunctions.begin(); iter != hashFunctions.end(); iter++) {
            if (cell[(*iter)(str) % numberOfCells] == false) {
                strInSet = false;
                break;
            }
        }

        return strInSet;
    }

    ~BloomFilter() {
        free(cell);
        cell = NULL;
    }
};

// implementing a couple of hash functions for testing

unsigned int djb2(std::string str) {
    unsigned int hash = 5381;

    for (std::string::iterator iter = str.begin(); iter != str.end(); iter++) {
        hash = ((hash << 5) + hash) + *iter;
    }

    return hash;
}

unsigned int sdbm(std::string str) {
    unsigned int hash = 0;

    for (std::string::iterator iter = str.begin(); iter != str.end(); iter++) {
        hash = ((hash << 6) + (hash << 16) - hash) + *iter;
    }

    return hash;
}


int main() {
    // create bloom filter
    std::vector<HashFunction> hashFunctions;
    hashFunctions.push_back(djb2);
    hashFunctions.push_back(sdbm);

    BloomFilter bf(1024, hashFunctions);

    // insert words into the filter
    std::vector<std::string> setOfStrings({
        "Hello World!",
        "sweet potato",
        "C++",
        "alpha",
        "beta",
        "gamma"
    });

    std::cout << "Bloom filter created." << std::endl;
    std::cout << "Bloom filter tests for the following set of strings:" << std::endl;

    for (std::vector<std::string>::iterator iter = setOfStrings.begin(); iter != setOfStrings.end(); iter++) {
        bf.addElement(*iter);
        std::cout << "\t" + *iter << std::endl;
    }

    // testing a set of strings against the bloom filter
    std::vector<std::string> testSetOfStrings({
        "Hello World!",
        "sweet potato",
        "C++",
        "alpha",
        "beta",
        "gamma",
        "delta",
        "where am i?",
        "foo",
        "bar"
    });

    std::cout << "Testing set inclusion for the following strings:" << std::endl;
    std::cout << std::boolalpha;

    for (std::vector<std::string>::iterator iter = testSetOfStrings.begin(); iter != testSetOfStrings.end(); iter++) {
        std::cout << "\t" + *iter + ": " << bf.searchElement(*iter) << std::endl;
    }

    getchar();
}
\$\endgroup\$
4
\$\begingroup\$

Thanks. I have been trying to learn about bloom filters. Had to do some research before the review :-)

Code Review

Hash Function

This is an old C style typedef.

typedef unsigned int (*HashFunction)(std::string);

Though not wrong I prefer the C++ style as they are easier to read.

typedef std::function<unsigned int(std::string)>   HashFunction;

Or using the newer C++11 using directive (I am beginning to use more of this myself).

using HashFunction = std::function<unsigned int(std::string)>;

While we are on the hash function. I note that you are passing std::string as a value and thus inducing a copy of the string. To avoid the copy pass by const reference.

using HashFunction = std::function<unsigned int(std::string const&)>;

Members

Looking at the data members of BloomFilter.

    // This member is not used anywhere.
    // but should also be the same value as hashFunctions.size()
    // So I think we can remove this.
    unsigned int numberOfFunctions;

    // Here we have a pointer data member. This is usually a bad
    // idea. We want to encourage the rule of zero. So we want to 
    // use classes that do their own memory management.
    bool* cell;
    // More about this in notes on the destructor.

So I would use:

    std::vector<bool>   cell;

Constructor

Just like normal variable declarations, prefer to initialize members one per line. There are no prizes for using the least number of rows possible.

Also like the hash function you are passing the parameters by value (and thus inducing a copy). Here we can pass funcs by const reference.

    BloomFilter(unsigned int numbCells, std::vector<HashFunction> funcs) : numberOfCells(numbCells), hashFunctions(funcs) {
        cell = (bool*)calloc(numbCells, sizeof(bool));
    }

    // Can be

    BloomFilter(unsigned int numbCells, std::vector<HashFunction> const& funcs)
        : numberOfCells(numbCells)
        , hashFunctions(funcs)
        , cell(numbCells)          // assuming we change cell to vector
    {}

As a side note:

        // Please don't use C-Casts.
        // These are completely unchecked. You are basically
        // telling the compiler to ignore all errors.
        cell = (bool*)calloc(numbCells, sizeof(bool));
        // Also there is no check to see if calloc() failed.

It should look more like this:

        cell = static_cast<bool*>(calloc(number, sizeof(bool));
        if (cell == null) {
            throw bad_alloc;  // maybe another exception.
        }

        // or better yet use new/delete
        cell = new bool[number]();      // need a call to delete [] cell; in destructor: The braces force value initialization that is false.

        // or better yet use a type like vector that does memory management correctly.
           // No action needed as you did it all in the initializer list.

addElement

Passing parameter by value again. Prefer to pass by const reference.

    void addElement(std::string str) {
    // So prefer
    void addElement(std::string const& str) {

When using iterators prefer to use the pre-increment ++iter rather than the post increment iter++. There is slight performance environment.

So you use the standard for loop from C++03

        for (std::vector<HashFunction>::iterator iter = hashFunctions.begin(); iter != hashFunctions.end(); iter++) {
            cell[(*iter)(str) % numberOfCells] = true;
        }

We can improve this in C++11 using auto.

        for (auto iter = hashFunctions.begin(); iter != hashFunctions.end(); ++iter) {
            cell[(*iter)(str) % numberOfCells] = true;
        }

In C++14 we now have the range based for loop.

        for (auto const& item: hashFunctions) {
            cell[item(str) % numberOfCells] = true;
        }

searchElement

Passing parameter by value again. Prefer to pass by const reference.

    bool searchElement(std::string str) {
    // should be
    bool searchElement(std::string const & str) {

The first note I want to make is the name. A searchX() function usually return a reference to something. I would name it checkX().

In this case rather than using a for loop you can use one of the standard function. In this case we can use find(). You are looking for a failure (but that's a thing).

    auto f = std::find(std::begin(hashFunctions), std::end(hashFunctions),
                       [&cell, &str](HashFunction hash){
                           return !cell[hash(str)];
                       });
    return f != std::end(hashFunctions);

Destructor

We should note that in C++11 we moved to using nullptr rather than NULL. It is type safe.

    ~BloomFilter() {
        free(cell);
        cell = NULL;  // This is actually a bad idea.
                      // It hides errors that can be detected by the
                      // debug system.
    }

One of the issues you can get into with doing your own memory management is called the double free. Usually debug version of the standard library detects double free so you can catch it during testing. But by setting the value to nullptr in the destructor prevents that check.

The other thing you need to note is that by default the compiler will generate four methods for a class if you don't define them.

  BloomFilter();                             // Constructor.
  BloomFilter(BloomFilter const&);           // Copy constructor.
  BloomFilter& operator=(BloomFilter const&);// Assignment operator
  ~BloomFilter();                            // Destrutor.

You define the Constructor and Destructor but the other two you don't define. So the compiler will generate the other two for you. Usually these work fine. BUT if your class contains an owned RAW pointer then the default compiler generated versions don't work as you would expect.

So you should look up the rule of three.
If you have to define one of Copy Constructor/Copy Assignment or destructor you probably need to do all three. If your class only uses objects that obey the rule of three already then your class will obey the rule of zero automatically (look them up).

Design Review

Asking user to provide a large set of hash functions is unreasonable. Hash functions are hard to define in the first place and even harder to get a good distribution with over a set of them. You need to define some way that in most cases the hash is provided (though being able to provide your own is a nice touch).

\$\endgroup\$
1
\$\begingroup\$

Implementation

  • numberOfFunctions isn't actually used anywhere.
  • HashFunction could be replaced with or changed to std::function<unsigned int(std::string)> so it can also accept functors and lambdas with captures.
  • cell could as easily be a std::bitset, a std::vector<bool> or a std::unique_ptr<bool[]>. Any of those choices would guarantee correct resource cleanup in all cases, and the first two options would make BloomFilter trivially copyable
  • The result of calloc is never checked. If it returns a nullptr, it will be dereferenced!
  • C++ style casts (in this case static_cast<bool*>) should be preferred over C style casts. These can better declare the intentions behind the cast.
  • In the destructor, cell is set to NULL. Not only should that be nullptr instead of NULL (so the compiler can give better diagnostics due to type safety), it isn't even necessary (after all, the object is being destroyed, who should read it?).
  • All iters types should be deduced with auto. That way, if the container type (e.g. of hashFunctions) ever needs to be changed, the iterator types will be adjusted automatically.
  • All function arguments of BloomFilter member functions can be marked const.
  • BloomFilter::searchElement() can be marked const.
  • The prefix increment should be preferred, especially for iterators (postfix might create an unnecessary copy).
  • Naming: BloomFilter::searchElement doesn't search for an element (and return it), but checks whether it is contained in the set. Also, since it can give a false positive in case of hash collisions, a better name might be mightContainElement or similar.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.