Based on this implementation it supports multiple hashes for better positive hit ratio. Can be initializes with size in bits and number of hashes to perform, like this:

bloom_filter bloom(128, 5);

As always, complete implementation on GitHub: bloom.hpp.

#pragma once

#include 
#include 
#include 
#include 
#include 

namespace
{
	template>
	class mixer
	{
	public:
		mixer(std::size_t size, const Key& key)
		: m_size(size), m_random(Hash{}(key))
		{
			assert(size > 0);
		}

		std::size_t operator()() { return m_random() % m_size; }

	private:
		std::size_t m_size;
		std::mt19937 m_random;
	};
}

template >
class bloom_filter
{
public:
	bloom_filter(std::size_t size, std::size_t hashes)
	: m_size(size), m_hashes(hashes), m_bits(size)
	{
		assert(size > 0);
		assert(hashes > 0);
	}

	void add(const Key& key)
	{
		mixer m(m_size, key);
		for(std::size_t i = 0; i < m_hashes; ++i)
			m_bits[m()] = true;
	}

	bool contains(const Key& key) const
	{
		mixer m(m_size, key);
		for(std::size_t i = 0; i < m_hashes; ++i)
			if(!m_bits[m()]) return false;
		return true;
	}

private:
	std::size_t m_size;
	std::size_t m_hashes;
	std::vector m_bits;
};

One Reply to “Better bloom filter”

Leave a Reply