BloomFilter in C++ using the MurmurHash3 hash function

Question

I am trying to code a C++ implementation of a Bloom filter using the MurmurHash3 hash function. My implementation is based on this site: http://blog.michaelschmatz.com/2016/04/11/how-to-write-a-bloom-filter-cpp/

Somehow, in my BloomFilter header file, the hash function throws an incomplete type error, also, when I use the hash function inside of the add function, I get a "hash is ambigious error".

What can I do to fix this? I am somewhat new to C++ so I'm not exactly sure if I am using the interface/implementation of a structure correctly.

I am also using a main function that will include this file and run some tests to analyze the false positive rate, number of bits, filter size etc . . .

#ifndef BLOOM_FILTER_H
#define BLOOM_FILTER_H
#include "MurmurHash3.h"
#include <vector>


//basic structure of a bloom filter object
struct BloomFilter {
BloomFilter(uint64_t size, uint8_t numHashes);
void add(const uint8_t *data, std::size_t len);
bool possiblyContains(const uint8_t *data, std::size_t len) const;
private:
uint8_t m_numHashes;
   std::vector<bool> m_bits;
};
//Bloom filter constructor
BloomFilter::BloomFilter(uint64_t size, uint8_t numHashes)
   : m_bits(size),
   m_numHashes(numHashes) {}
//Hash array created using the MurmurHash3 code
std::array<uint64_t, 2> hash(const uint8_t *data, std::size_t len)
{
   std::array<uint64_t, 2> hashValue;
   MurmurHash3_x64_128(data, len, 0, hashValue.data());
   return hashValue;
}
//Hash array created using the MurmurHash3 code
inline uint64_t nthHash(uint8_t n,
   uint64_t hashA,
   uint64_t hashB,
   uint64_t filterSize) {
   return (hashA + n * hashB) % filterSize;
}
//Adds an element to the array
void BloomFilter::add(const uint8_t *data, std::size_t len) {
   auto hashValues = hash(data, len);
   for (int n = 0; n < m_numHashes; n++)
   {
       m_bits[nthHash(n, hashValues[0], hashValues[1], m_bits.size())]        = true;
   }
}
//Returns true or false based on a probabilistic assesment of the array         using MurmurHash3
bool BloomFilter::possiblyContains(const uint8_t *data, std::size_t   len) const {
   auto hashValues = hash(data, len);
   for (int n = 0; n < m_numHashes; n++)
   {
       if (!m_bits[nthHash(n, hashValues[0], hashValues[1],         m_bits.size())])
        {
           return false;
       }
   }
   return true;
}
#endif

Answer 1

If your MurmurHash3_x64_128 returns two 64-bit numbers as a hash value, I'd treat that as 4 distinct uint32_t hashes as long as you don't need more than 4 billion bits in your bit string. Most likely you don't need more than 2-3 hashses, but that depends on your use case. To figure out how many hashes you need you can check "How many hash functions does my bloom filter need?".

Using MurmurHash3_x64_128 I'd do it this way (if I were to treat it as 4 x uint32_t hashses):

void BloomFilter::add(const uint8_t *data, std::size_t len) {
    auto hashValues = hash(data, len);
    uint32_t* hx = reinterpret_cast<uint32_t*>(&hashValues[0]);
    assert(m_numHashes <= 4);
    for (int n = 0; n < m_numHashes; n++)
        m_bits[hx[n] % m_bits.size()] = true;
}

Your code has some issues with types conversion that's why it didn't compile:

• missing #include <array>
• you have to use size_t for size (it might be 32-bit unsigned or 64-bit unsigned int)
• it's better to name your hash to something else (e.g. myhash) and make it static.

Here's version of your code with these correction and this should work:

#ifndef BLOOM_FILTER_H
#define BLOOM_FILTER_H
#include "MurmurHash3.h"
#include <vector>
#include <array>


//basic structure of a bloom filter object
struct BloomFilter {
    BloomFilter(size_t size, uint8_t numHashes);
    void add(const uint8_t *data, std::size_t len);
    bool possiblyContains(const uint8_t *data, std::size_t len) const;
private:
    uint8_t m_numHashes;
    std::vector<bool> m_bits;
};
//Bloom filter constructor
BloomFilter::BloomFilter(size_t size, uint8_t numHashes)
    : m_bits(size),
    m_numHashes(numHashes) {}
//Hash array created using the MurmurHash3 code
static std::array<uint64_t, 2> myhash(const uint8_t *data, std::size_t len)
{
    std::array<uint64_t, 2> hashValue;
    MurmurHash3_x64_128(data, len, 0, hashValue.data());
    return hashValue;
}
//Hash array created using the MurmurHash3 code
inline size_t nthHash(int n,
    uint64_t hashA,
    uint64_t hashB,
    size_t filterSize) {
    return (hashA + n * hashB) % filterSize; // <- not sure if that is OK, perhaps it is.
}
//Adds an element to the array
void BloomFilter::add(const uint8_t *data, std::size_t len) {
    auto hashValues = myhash(data, len);
    for (int n = 0; n < m_numHashes; n++)
    {
        m_bits[nthHash(n, hashValues[0], hashValues[1], m_bits.size())] = true;
    }
}
//Returns true or false based on a probabilistic assesment of the array         using MurmurHash3
bool BloomFilter::possiblyContains(const uint8_t *data, std::size_t   len) const {
    auto hashValues = myhash(data, len);
    for (int n = 0; n < m_numHashes; n++)
    {
        if (!m_bits[nthHash(n, hashValues[0], hashValues[1], m_bits.size())])
        {
            return false;
        }
    }
    return true;
}
#endif

Run this code on ideone.

If you are just starting with c++, at first start with basic example, try to use std::hash maybe? Create working implementation, then extend it with optional hash function parameter. If you need your BloomFilter to be fast I'd probably stay away from vector<bool> and use array of unsigned ints instead.

Basic impl could something like this, provided that your have MurmurHash3 implemented:

uint32_t MurmurHash3(const char *str, size_t len);

class BloomFilter
{
public:
    BloomFilter(int count_elements = 0, double bits_per_element = 10)
    {
        mem = NULL;
        init(count_elements, bits_per_element);
    }
    ~BloomFilter()
    {
        delete[] mem;
    }

    void init(int count_elements, double bits_per_element)
    {
        assert(!mem);
        sz = (uint32_t)(count_elements*bits_per_element + 0.5);
        mem = new uint8_t[sz / 8 + 8];
    }

    void add(const std::string &str)
    {
        add(str.data(), str.size());
    }

    void add(const char *str, size_t len)
    {
        if (len <= 0)
            return;
        add(MurmurHash3(str, len));
    }

    bool test(const std::string &str)
    {
        return test(str.data(), str.size());
    }

    bool test(const char *str, size_t len)
    {
        return test_hash(MurmurHash3(str, len));
    }

    bool test_hash(uint32_t h)
    {
        h %= sz;
        if (0 != (mem[h / 8] & (1u << (h % 8))))
            return true;
        return false;
    }

    int mem_size() const
    {
        return (sz + 7) / 8;
    }

private:
    void add(uint32_t h)
    {
        h %= sz;
        mem[h / 8] |= (1u << (h % 8));
    }

public:
    uint32_t sz;
    uint8_t *mem;
};