布隆过滤器更多...

#include <bloom_filter.hpp>

Public 成员函数
	~bloom_filter ()=default
	析构函数
	bloom_filter (const size_t expected_insertions, const double false_positive_prob)
	基于预期插入数和误报率构造
	bloom_filter (const size_t m, const size_t k)
	基于直接参数构造
NEFORCE_NODISCARD size_t	capacity () const noexcept
	获取理论容量
NEFORCE_NODISCARD bool	empty () const noexcept
	检查过滤器是否为空
NEFORCE_NODISCARD size_t	bit_size () const noexcept
	获取位数组大小
NEFORCE_NODISCARD size_t	hash_count () const noexcept
	获取哈希函数数量
NEFORCE_NODISCARD size_t	approximate_count () const noexcept
	估计当前元素数量
NEFORCE_NODISCARD double	false_positive_rate () const noexcept
	估计当前误报率
NEFORCE_NODISCARD bool	contains (const T &key) const noexcept
	检查元素是否可能存在
void	insert (const T &key) noexcept
	插入元素
void	clear () noexcept
	清空过滤器
bloom_filter &	merge (const bloom_filter &other)
	合并另一个过滤器
bloom_filter	intersect (const bloom_filter &other) const
	交集操作
bloom_filter	unite (const bloom_filter &other) const
	并集操作
byte_vector	to_bytes () const
	转换为字节数组
void	from_bytes (const byte_vector &bytes)
	从字节数组恢复

详细描述

template<typename T, typename Hash = hash<T>>
class bloom_filter< T, Hash >

布隆过滤器

模板参数

T	元素类型
Hash	哈希函数类型，默认为hash<T>

布隆过滤器使用多个哈希函数将元素映射到一个位数组中。布隆过滤器有如下特性：

空间效率高，使用位数组存储
查询速度快，时间复杂度O(k)
不存在假阴性（如果元素在集合中，查询一定返回true）
存在假阳性（可能误判不存在的元素存在）
支持合并和交集操作

在文件 bloom_filter.hpp 第 40 行定义.

构造及析构函数说明

◆ bloom_filter() [1/2]

template<typename T, typename Hash = hash<T>>

bloom_filter< T, Hash >::bloom_filter	(	const size_t	expected_insertions,
		const double	false_positive_prob )

inline

基于预期插入数和误报率构造

参数

expected_insertions	预期插入元素数量
false_positive_prob	期望误报率

异常

value_exception 当预期插入数为0或误报率不在(0,1)范围内时抛出

根据预期插入数量和期望误报率自动计算最优参数。

在文件 bloom_filter.hpp 第 120 行定义.

◆ bloom_filter() [2/2]

template<typename T, typename Hash = hash<T>>

bloom_filter< T, Hash >::bloom_filter	(	const size_t	m,
		const size_t	k )

inline

基于直接参数构造

参数

m	位数组大小
k	哈希函数数量

异常

value_exception 当m或k为0时抛出

直接指定位数组大小和哈希函数数量。

在文件 bloom_filter.hpp 第 139 行定义.

成员函数说明

◆ approximate_count()

template<typename T, typename Hash = hash<T>>

NEFORCE_NODISCARD size_t bloom_filter< T, Hash >::approximate_count ( ) const

inlinenoexcept

估计当前元素数量

返回: 元素数量的近似值

根据位数组中1的比例估算实际插入的元素数量。

在文件 bloom_filter.hpp 第 190 行定义.

引用了 logarithm_e().

◆ bit_size()

template<typename T, typename Hash = hash<T>>

NEFORCE_NODISCARD size_t bloom_filter< T, Hash >::bit_size ( ) const

inlinenoexcept

获取位数组大小

返回: 位数

在文件 bloom_filter.hpp 第 176 行定义.

◆ capacity()

template<typename T, typename Hash = hash<T>>

NEFORCE_NODISCARD size_t bloom_filter< T, Hash >::capacity ( ) const

inlinenoexcept

获取理论容量

返回: 理论可容纳元素数量

基于当前参数计算理论可容纳元素数量。

在文件 bloom_filter.hpp 第 155 行定义.

引用了 logarithm_e().

◆ clear()

template<typename T, typename Hash = hash<T>>

void bloom_filter< T, Hash >::clear ( )

inlinenoexcept

清空过滤器

将所有位重置为0。

在文件 bloom_filter.hpp 第 256 行定义.

引用了 fill().

◆ contains()

template<typename T, typename Hash = hash<T>>

NEFORCE_NODISCARD bool bloom_filter< T, Hash >::contains ( const T & key ) const

inlinenoexcept

检查元素是否可能存在

参数

key 要检查的元素

返回: 如果元素可能存在返回true，如果一定不存在返回false

如果返回false，则元素一定不在集合中。如果返回true，则元素可能存在（也可能误判）。

在文件 bloom_filter.hpp 第 226 行定义.

◆ empty()

template<typename T, typename Hash = hash<T>>

NEFORCE_NODISCARD bool bloom_filter< T, Hash >::empty ( ) const

inlinenoexcept

检查过滤器是否为空

返回: 如果没有元素被插入返回true

在文件 bloom_filter.hpp 第 163 行定义.

◆ false_positive_rate()

template<typename T, typename Hash = hash<T>>

NEFORCE_NODISCARD double bloom_filter< T, Hash >::false_positive_rate ( ) const

inlinenoexcept

估计当前误报率

返回: 误报率的近似值

根据位数组中1的比例估算当前的误报率。

在文件 bloom_filter.hpp 第 207 行定义.

引用了 power().

◆ from_bytes()

template<typename T, typename Hash = hash<T>>

void bloom_filter< T, Hash >::from_bytes ( const byte_vector & bytes )

inline

从字节数组恢复

参数

bytes 字节向量

异常

value_exception 当字节数组大小不足时抛出

从字节数组恢复位数组状态。

在文件 bloom_filter.hpp 第 337 行定义.

引用了 vector< T, Alloc >::size().

◆ hash_count()

template<typename T, typename Hash = hash<T>>

NEFORCE_NODISCARD size_t bloom_filter< T, Hash >::hash_count ( ) const

inlinenoexcept

获取哈希函数数量

返回: k值

在文件 bloom_filter.hpp 第 182 行定义.

◆ insert()

template<typename T, typename Hash = hash<T>>

void bloom_filter< T, Hash >::insert ( const T & key )

inlinenoexcept

插入元素

参数

key 要插入的元素

将元素的所有哈希位置设为1。

在文件 bloom_filter.hpp 第 243 行定义.

◆ intersect()

template<typename T, typename Hash = hash<T>>

bloom_filter bloom_filter< T, Hash >::intersect ( const bloom_filter< T, Hash > & other ) const

inline

交集操作

参数

other 另一个过滤器

返回: 新过滤器，为两个过滤器的交集

异常

value_exception 当过滤器参数不匹配时抛出

对两个过滤器的位进行AND操作。要求两个过滤器参数相同。

在文件 bloom_filter.hpp 第 289 行定义.

◆ merge()

template<typename T, typename Hash = hash<T>>

bloom_filter & bloom_filter< T, Hash >::merge ( const bloom_filter< T, Hash > & other )

inline

合并另一个过滤器

参数

other 要合并的过滤器

返回: 自身引用

异常

value_exception 当过滤器参数不匹配时抛出

将另一个过滤器的所有位与当前过滤器进行OR操作。要求两个过滤器参数相同。

在文件 bloom_filter.hpp 第 267 行定义.

被这些函数引用 unite().

◆ to_bytes()

template<typename T, typename Hash = hash<T>>

byte_vector bloom_filter< T, Hash >::to_bytes ( ) const

inline

转换为字节数组

返回: 字节向量表示

将位数组转换为字节数组以便序列化。

在文件 bloom_filter.hpp 第 320 行定义.

◆ unite()

template<typename T, typename Hash = hash<T>>

bloom_filter bloom_filter< T, Hash >::unite ( const bloom_filter< T, Hash > & other ) const

inline

并集操作

参数

other 另一个过滤器

返回: 新过滤器，为两个过滤器的并集

异常

value_exception 当过滤器参数不匹配时抛出

对两个过滤器的位进行OR操作。

在文件 bloom_filter.hpp 第 309 行定义.

引用了 merge().

该类的文档由以下文件生成:

bloom_filter.hpp

Public 成员函数

详细描述

构造及析构函数说明

◆ bloom_filter() [1/2]

◆ bloom_filter() [2/2]

成员函数说明

◆ approximate_count()

◆ bit_size()

◆ capacity()

◆ clear()

◆ contains()

◆ empty()

◆ false_positive_rate()

◆ from_bytes()

◆ hash_count()

◆ insert()

◆ intersect()

◆ merge()

◆ to_bytes()

◆ unite()