布隆过滤器：原理与leveldb中的实现
布隆过滤器参考资料：
[*]bloom filter
[*]leveldb
目录
[*]布隆过滤器
[*]根本介绍
[*]算法形貌
[*]记号说明
[*]算法说明
[*]leveldb中的布隆过滤器
[*]根本架构
[*]基类FilterPolicy
[*]BloomHash布隆哈希函数
根本介绍
[*]布隆过滤器是一个空间优化的概率性数据布局，在1970年由Howard Bloom计划而成。
[*]用于判断一个元素是否属于一个聚集（即预先判断是否存在，不存在则不实验查找）。
[*]会有两种返回的情况：(a) 元素不存在聚集中。(b) 元素可能存在于聚集之中。
[*]发明布隆过滤器的目的：当数据特殊巨大，以至于传统的无错误哈希技术占用了巨大的内存。
[*]在RAM内存告急的时间，布隆过滤器可以大量减少不必要的内存读写。
算法形貌
记号说明
我们将采用以下的符号来说明一下布隆过滤器的根本思想。我们有：
(1) m: 布隆过滤器的位宽(bit width).
(2) n: 插入元素的数目。
(3) k: 哈希函数的数目。
算法说明
1.初始化
布隆过滤器将会初始化成一个m位数组，初始时间所有的位将会设成0.同时，它将配有k个哈希函数，每个哈希函数将会把一个元素映射到m个位中的1个位上，这样对于每个元素，在插入后，将会有k个位被置位。k的选取与错误率（假阳率）有关系，而且m与k，n都成一定的比例关系。
2.增长元素（插入）
将元素传递给k和哈希函数，而且将k个位全部置位。
3.检查元素是否位于聚集内。
将元素传递给k和哈希函数，得到k个位置。这时间我们有两种情况。
(1) 存在一个位没有被置位。那么元素肯定不位于聚集内。
(2) 所有的k个位均被置位。那么元素可能在聚集内。
4.删除元素
不可能。对于布隆过滤器，我们无法决定k个bit中应该清零哪一个位。如果我们随意选择了一个位，将影响到其他的元素。会导致假阴性情况的出现。
有人会问：我可以再增长一个布隆过滤器，内里记录了被删除的元素吗？答案是不推荐。由于在这样的一个对偶过滤器中，其假阳性(觉得删除了但现实没有删除)就对应了原布隆过滤器的假阴性(存在于聚集中的元素现实没有存在)，没有很大的意义。而且，我们也有可能把重新删除的元素又到场回去，这样就会导致新设立的布隆过滤器不太有现实意义。ref
5.重修过滤器
有时间，假阳性可能太高以至于我们需要重修过滤器。我们应该避免这样的情况。
6.较优设置
布隆过滤器的较优设置是 \(k=\dfrac{m}{n}\ln{2}\), 同时，每个元素应使用的bit数目最优应该为 \(\dfrac{m}{n}=2.08\ln{\dfrac{1}{\varepsilon}}=1.44\log_2{\dfrac{1}{\varepsilon}}\)。证实参见
leveldb中的布隆过滤器
布隆过滤器在leveldb中的实现在util/bloom.cc中。
根本架构
基类FilterPolicy
继续了FilterPolicy这个类。这个类主要有四个虚函数：
[*]虚析构函数virtual ~FilterPolicy()
[*]纯虚函数virtual const char* Name() const = 0;，返回调用的过滤器的名字。
[*]纯虚函数
void CreateFilter(const Slice* keys, int n, std::string* dst) const = 0
[*]传入切片 (其实就是管理字符串的一个类，后面有空在分析) 类指针对象，这个对象是根据用户指定的规则进行排序后的有序列表。一个n代表切片列表的大小。一个string指针地址。
[*]根据切片列表，天生过滤器，并将它添加到目的地址。
[*]LEVELDB_EXPORT const FilterPolicy* NewBloomFilterPolicy(int bits_per_key);一个新的布隆过滤器，采用自行界说的 \(\dfrac{m}{n}\)。前面的宏与符号导出有关。
#ifndef STORAGE_LEVELDB_INCLUDE_FILTER_POLICY_H_
#define STORAGE_LEVELDB_INCLUDE_FILTER_POLICY_H_
#include <string>
#include "leveldb/export.h"
namespace leveldb {
class Slice;
class LEVELDB_EXPORT FilterPolicy {
public:
virtual ~FilterPolicy();
virtual const char* Name() const = 0;
virtual void CreateFilter(const Slice* keys, int n, std::string* dst) const = 0;
virtual bool KeyMayMatch(const Slice& key, const Slice& filter) const = 0;
};
LEVELDB_EXPORT const FilterPolicy* NewBloomFilterPolicy(int bits_per_key);
}
#endifBloomHash布隆哈希函数
[*]uint32_t Hash(const char* data, size_t n, uint32_t seed)
[*]采用近似于murmur hash的方式天生一个哈希值。传入一个字符串，字符串的大小和一个随机种子。种子是一个魔数，笔者不懂数学因此不予深究。（也没有查询到解释的相关资料）
这里的哈希函数将进行以下操作：
1. 分析字符串。
在C++中，一个char所占的存储空间为1字节(8bit)，因此我们可以将这个字符串看作是uint8数组。每次我们读取4个字节（四个uint8数），将指针向右移动4位。
哈希值的计算：起首根据种子，字符串大小和魔数天生基础的值 \(h\)。随后，将字符串按上述方式分析后，加上分析值，乘以魔数m而且取前16位。
2. 处置惩罚剩余字符串。
上述处置惩罚将处置惩罚到终极只剩下不满4个字符（4个byte）为止。终极的处置惩罚仍然是加上剩余字符的分析值，乘以魔数m。
注意到在进行剩余的字符处置惩罚时，我们使用了switch case布局。在C/C++中，switch-case布局在没有使用break的情况下将自动贯穿，也就是自上而下序次实验每个case，直到实验default结束。为了告诉开发者贯穿是有意为之的并提示忽略警告，将会界说一个FALLTHROUGH。现代C++17 尺度已经有[]可以使用。
uint32_t Hash(const char* data, size_t n, uint32_t seed) {
// Similar to murmur hash
const uint32_t m = 0xc6a4a793;
const uint32_t r = 24;
const char* limit = data + n;
uint32_t h = seed ^ (n * m);
// Pick up four bytes at a time
while (limit - data >= 4) {
uint32_t w = DecodeFixed32(data);
data += 4;
h += w;
h *= m;
h ^= (h >> 16);
}
// Pick up remaining bytes
switch (limit - data) {
case 3:
h += static_cast<uint8_t>(data) << 16;
FALLTHROUGH_INTENDED;
case 2:
h += static_cast<uint8_t>(data) << 8;
FALLTHROUGH_INTENDED;
case 1:
h += static_cast<uint8_t>(data);
h *= m;
h ^= (h >> r);
break;
}
return h;
}未完待续...
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]