bloom_filter.hpp File Reference

Implements a generic bloom filter. The bloom filter allows for customisation of used hash functions and hash functions. More...

#include "compiler.hpp"
#include "hash_utils.hpp"
#include "hashes.hpp"
#include <algorithm>
#include <bit>
#include <cmath>
#include <numeric>
#include <vector>

Include dependency graph for bloom_filter.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	boxes::filter::bloom::Bloom< KeyT, HashT >
	A generic bloom filter implementation. More...

Functions
std::size_t	boxes::filter::bloom::calcSize (std::size_t maxElements, double collisionProb)
	Utility function to calculate the required size of the bloom filter's bitmap size to store the maximum number of elements with a given collision probability. More...
std::size_t	boxes::filter::bloom::calcHashes (std::size_t bloomSize, std::size_t maxElements)
	Utility function to calculate the number of hash functions required to store maximum number of elements, given the size of the bloom filter's bitmap. More...

Detailed Description

Implements a generic bloom filter. The bloom filter allows for customisation of used hash functions and hash functions.

Copyright 2024 Tomasz Wisniewski twdev.nosp@m..blo.nosp@m.gger@.nosp@m.gmai.nosp@m.l.com

Definition in file bloom_filter.hpp.

Function Documentation

calcHashes()

std::size_t boxes::filter::bloom::calcHashes	(	std::size_t	bloomSize,
		std::size_t	maxElements
	)

Utility function to calculate the number of hash functions required to store maximum number of elements, given the size of the bloom filter's bitmap.

Parameters

bloomSize	(m) size of the bloom filter's bitmap
maxElements	maximum number of elements the filter will store

Returns

required number of hash functions

Definition at line 188 of file bloom_filter.hpp.

calcSize()

std::size_t boxes::filter::bloom::calcSize	(	std::size_t	maxElements,
		double	collisionProb
	)

Utility function to calculate the required size of the bloom filter's bitmap size to store the maximum number of elements with a given collision probability.

Parameters

maxElements	maximum number of elements the filter will store
collisionProb	desired collision probability (range: 0.0 - 1.0) - the smaller, the better

Returns

m - number of bits in the filter

Definition at line 172 of file bloom_filter.hpp.