文件名称：实现-空间谱估计算法及应用 王永良
文件大小：8.18MB
文件格式：PDF
更新时间：2024-07-13 16:36:40
leveldb rocksdb leveldb架构
7.2 数数数学学学结结结论论论 http://blog.csdn.net/jiaomeng/article/details/1495500该文中从数学的角度阐述了布隆过滤器的原理，以及一系 列的数学结论。 首先，与布隆过滤器准确率有关的参数有： • 哈希函数的个数k； • 布隆过滤器位数组的容量m; • 布隆过滤器插入的数据数量n; 主要的数学结论有： 1. 为了获得最优的准确率，当k = ln2 * (m/n)时，布隆过滤器获得最优的准确性； 2. 在哈希函数的个数取到最优时，要让错误率不超过，m至少需要取到最小值的1.44倍； 7.3 实实实现现现 leveldb中的布隆过滤器实现较为简单，以goleveldb为例，有关的代码在filter/bloom.go中。 定义如下，bloom过滤器只是一个int数字。 type bloomFilter int 创建一个布隆过滤器时，只需要指定为每个key分配的位数即可，如结论2所示，只要该值（m/n）大 于1.44即可，一般可以取10。 func NewBloomFilter(bitsPerKey int) Filter { return bloomFilter(bitsPerKey) } 创建一个generator,这一步中需要指定哈希函数的个数k，可以看到k = f * ln2，而f = m/n，即数学结论1。 返回的generator中可以添加新的key信息，调用generate函数时，将所有的key构建成一个位数组写在指定的 位置。 func (f bloomFilter) NewGenerator() FilterGenerator { // Round down to reduce probing cost a little bit. k := uint8(f * 69 / 100) // 0.69 =~ ln(2) if k < 1 { k = 1 } else if k > 30 { k = 30 } return &bloomFilterGenerator{ n: int(f), k: k, } } 48 Chapter 7. 布布布隆隆隆过过过滤滤滤器器器