BloomFilter в C ++ с использованием хэш-функции MurmurHash3

Если ваш MurmurHash3_x64_128 возвращает два 64-битных числа в качестве значения хеш-функции, я бы отнесся к этому как к 4 различным хэшам uint32_t, если вам не нужно более 4 миллиардов битов в вашей битовой строке. Скорее всего, вам не нужно больше 2-3 хешей, но это зависит от вашего варианта использования. Чтобы выяснить, сколько хэшей вам нужно, вы можете проверить «Сколько хеш-функций нужно моему фильтру Блума?».

Используя MurmurHash3_x64_128, я бы сделал это следующим образом (если бы я рассматривал это как 4 хеша uint32_t):

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

У вашего кода есть некоторые проблемы с преобразованием типов, поэтому он не компилируется:

• отсутствует #include <array>
• Вы должны использовать size_t для размера (это может быть 32-битный без знака или 64-битный без знака int)
• лучше назвать свой хэш чем-то другим (например, myhash) и сделать это статичным.

Вот версия вашего кода с этими исправлениями, и это должно работать:

#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

Запустите этот код на ideone.

Если вы только начинаете с c ++, сначала начните с базового примера, попробуйте использовать станд :: хэш может быть? Создайте рабочую реализацию, затем расширьте ее необязательным параметром хеш-функции. Если вам нужен BloomFilter, чтобы быть быстрым, я бы, вероятно, держался подальше от vector<bool> и вместо этого используйте массив беззнаковых целых.

Основной импл может что-то вроде этого, при условии, что у вас есть MurmurHash3 внедрено:

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