下载文档原格式
redisson布隆过滤器原理Redisson布隆过滤器是一种基于Redis的高性能、高可靠性的布隆过滤器实现，主要用于判断一个元素是否存在于一个大集合中。
布隆过滤器是一种概率型数据结构，它利用多个哈希函数和一个二进制位数组来判断一个元素是否存在于集合中。
当有一个元素要加入到集合中时，通过多个哈希函数将元素映射到二进制位数组中的多个位置，将这些位置的二进制位设为1、当判断一个元素是否存在时，通过多个哈希函数将元素映射到二进制位数组中的多个位置，如果这些位置的二进制位都为1，则说明元素可能存在于集合中；如果有任何一个位置的二进制位为0，则说明元素一定不存在于集合中。
Redisson布隆过滤器的原理如下：1. 创建布隆过滤器：使用Redisson创建布隆过滤器实例时，会在Redis服务器上创建一个字符串类型的键，用于存储布隆过滤器的二进制位数组。
同时，还会创建一个Redis的BitSet数据结构，用于在内存中表示二进制位数组。
2. 添加元素：当有一个元素要添加到布隆过滤器中时，首先会经过多个哈希函数的映射，将元素映射到二进制位数组中的多个位置。
然后，通过Redis的BitSet数据结构将这些位置的二进制位设置为13. 判断元素是否存在：当判断一个元素是否存在于布隆过滤器中时，同样需要通过多个哈希函数的映射，将元素映射到二进制位数组中的多个位置。
然后，通过Redis的BitSet数据结构判断这些位置的二进制位是否为1，如果有任何一个位置的二进制位为0，则说明元素一定不存在于布隆过滤器中；如果这些位置的二进制位都为1，则说明元素可能存在于布隆过滤器中。
4. 删除元素：由于布隆过滤器无法删除元素，因此Redisson布隆过滤器也无法删除元素。
如果需要删除元素，只能重置整个布隆过滤器。
5.误判率控制：由于布隆过滤器是概率型数据结构，存在一定的误判率。
误判率主要受两个因素影响：布隆过滤器的容量和哈希函数的数量。
布隆过滤器的时间复杂度布隆过滤器（Bloom Filter）是一种快速判断某个元素是否存在于大规模数据集中的数据结构，它通过位数组和不同的哈希函数实现。
由于其高效的查询性能和低内存占用，被广泛应用于网络缓存、关键词过滤、数据重复性判断等领域。
本文将详细介绍布隆过滤器的时间复杂度。
1. 布隆过滤器的原理和特点布隆过滤器通过将每个元素经过多个哈希函数得到的哈希值在位数组中对应的位置标记为1，来表示元素的存在。
当查询某个元素是否存在时，同样对该元素进行多次哈希函数计算，并检查对应的位数组位置是否都为1。
如果存在任意一个位置不为1，则可以确定该元素不存在于数据集中。
布隆过滤器的特点包括：- 快速查询：布隆过滤器的查询时间只与哈希函数的个数有关，与数据集大小无关，具有常量级的查询时间复杂度。
- 低内存占用：布隆过滤器只需要开辟一个位数组空间，并通过哈希函数计算得到的位置进行标记，不存储实际数据，因此占用的内存空间相对较小。
- 可能的误判：布隆过滤器判断元素是否存在时，可能会出现误判的情况。
当位数组中的某个位置被其他元素的哈希值所标记时，查询元素的哈希值可能也会被认为存在，但实际上该元素并不存在。
2. 插入元素的时间复杂度插入元素到布隆过滤器中的时间复杂度主要取决于哈希函数的个数和哈希值计算的效率。
假设布隆过滤器的位数组长度为m，哈希函数的个数为k，要插入的元素个数为n。
每个元素的哈希函数计算次数为k，因此插入n个元素的总哈希函数计算次数为nk。
对于每个元素的哈希值，在位数组中标记位置为1的时间复杂度是O(1)。
因此，插入元素的总时间复杂度可以表示为：O(nk)需要注意的是，为了保证布隆过滤器的效果，位数组的长度和哈希函数的个数需要合理选择。
位数组的长度过小容易导致误判率升高，而哈希函数的个数过多则会增加计算的时间开销。
3. 查询元素的时间复杂度查询元素是否存在于布隆过滤器中的时间复杂度也主要取决于哈希函数的个数和哈希值计算的效率。
布隆过滤器底层原理布隆过滤器是一种数据结构，用于快速判断一个元素是否存在于一个集合中。
它通过使用位数组和多个哈希函数来实现这一功能。
布隆过滤器的底层原理非常巧妙，可以高效地处理大规模的数据集。
布隆过滤器的核心是位数组，它通常是一个固定长度的二进制数组。
位数组的每个位置都对应一个位，初始时都被设置为0。
当一个元素被加入到布隆过滤器中时，它会经过多个哈希函数的处理，得到多个哈希值。
这些哈希值对应的位置在位数组中被设置为1。
当需要判断一个元素是否存在时，同样会经过多个哈希函数的处理，得到多个哈希值。
如果这些哈希值对应的位置都为1，那么可以判断该元素可能存在于集合中。
如果有任何一个位置为0，那么可以确定该元素一定不存在于集合中。
布隆过滤器的核心思想是通过多个哈希函数的处理，将元素分散到位数组中的不同位置。
这样可以减少冲突的概率，提高判断的准确性。
同时，布隆过滤器的空间效率也非常高。
由于位数组的长度是固定的，不受存入元素的个数影响，所以在存储大规模数据集时，布隆过滤器所占用的空间相对较小。
然而，由于布隆过滤器的特殊性，它也存在一些缺点。
首先，布隆过滤器在判断一个元素是否存在时，有一定的误判率。
也就是说，有可能判断一个元素存在于集合中，但实际上并不存在。
这是因为多个元素可能被哈希到同一个位置上，导致冲突。
其次，布隆过滤器只能判断元素是否存在，而不能得到元素的具体信息。
因此，在实际应用中，布隆过滤器通常用于判断一个元素是否存在，如果需要获取具体信息，还需要进一步查询其他数据结构。
布隆过滤器在实际应用中有着广泛的应用。
例如，它可以用于网络爬虫中，判断一个URL是否已经被访问过，从而避免重复爬取。
又如，在大规模的分布式系统中，布隆过滤器可以用于判断一个元素是否已经存在于缓存中，从而减少对数据库的查询次数。
此外，布隆过滤器还可以用于垃圾邮件过滤、黑名单检测等方面。
总的来说，布隆过滤器是一种高效、节省空间的数据结构，用于判断一个元素是否存在于一个集合中。
redisson布隆过滤器原理Redisson布隆过滤器原理一、背景介绍布隆过滤器是一种高效的数据结构，用于判断一个元素是否存在于集合中。
它通过使用多个哈希函数将元素映射到一个大的二进制位数组中，并将对应位置的值设为1，表示该元素存在于集合中。
当需要判断一个元素是否存在时，只需要将该元素经过相同的哈希函数映射到位数组中，并检查对应位置的值是否为1即可。
Redisson是一个基于Redis实现的Java分布式对象框架，提供了丰富的数据结构和分布式服务。
其中之一就是布隆过滤器。
二、Redisson布隆过滤器特点1. 高效性：Redisson布隆过滤器可以在常数时间内判断一个元素是否存在于集合中，而不需要遍历整个集合。
2. 空间效率高：Redisson布隆过滤器只需要占用很小的空间就可以存储大量数据。
3. 可扩展性强：Redisson布隆过滤器支持动态扩容和缩容，可以根据实际需求灵活调整大小。
三、Redisson布隆过滤器实现原理1. 哈希函数选择在使用布隆过滤器时，需要选择多个哈希函数将元素映射到位数组中。
Redisson布隆过滤器默认使用了MurmurHash算法和JenkinsHash 算法，这两种算法都具有良好的散列性能和低碰撞率。
2. 位数组大小计算在创建Redisson布隆过滤器时，需要指定期望容量和误判率。
根据这两个参数，可以计算出需要的位数组大小和哈希函数个数。
其中，位数组大小的计算公式为：m = (n * ln(p)) / ln(2)^2其中，m表示位数组大小，n表示期望容量，p表示误判率。
3. 元素添加当向Redisson布隆过滤器中添加一个元素时，会将该元素经过多个哈希函数映射到位数组中，并将对应位置的值设为1。
如果该位置已经被设为1，则不需要再次设置。
4. 元素判断当需要判断一个元素是否存在于Redisson布隆过滤器中时，会将该元素经过相同的哈希函数映射到位数组中，并检查对应位置的值是否为1。
布隆过滤器课程设计
布隆过滤器是一种空间效率高的数据结构，通常用于快速检索一个元素是否属于一个集合中。
在进行布隆过滤器的课程设计时，需要考虑以下几个方面：
1. 布隆过滤器的原理：首先，需要深入理解布隆过滤器的原理，包括如何进行元素的插入和查询，以及误判率的计算方法。
布隆过滤器的实现依赖于位数组和多个哈希函数，通过位数组和哈希函数的组合，可以实现高效的元素检索。
2. 数据结构设计：在设计布隆过滤器的课程项目时，需要考虑如何设计数据结构来存储位数组和哈希函数。
位数组的大小需要根据预期的元素数量和误判率进行合理的选择，而哈希函数的选择也会影响到布隆过滤器的性能。
3. 实现算法：在实现布隆过滤器的算法时，需要考虑如何高效地插入和查询元素。
可以采用现成的哈希函数库，也可以自己实现哈希函数来提高性能。
此外，需要考虑如何处理哈希冲突，以及如何优化位数组的内存使用。
4. 性能优化：在设计布隆过滤器的课程项目时，可以考虑如何优化布隆过滤器的性能。
例如，可以通过调整位数组的大小和哈希函数的选择来减少误判率，也可以通过并行化的方式来加速元素的插入和查询过程。
5. 应用场景：最后，可以考虑如何将布隆过滤器应用到实际的场景中。
布隆过滤器常用于网络爬虫的URL去重、缓存的数据查询等场景，可以通过设计相关的应用案例来加深对布隆过滤器的理解。
通过以上几个方面的考虑，可以设计出一个完整的布隆过滤器的课程项目，帮助学生深入理解布隆过滤器的原理和实现方式，提高他们的数据结构和算法的实践能力。
同时，也可以通过布隆过滤器的课程设计，帮助学生将理论知识应用到实际的项目中，提高他们的解决问题的能力。
Snoop Filter的工作原理引言在计算机科学中，布隆过滤器（Bloom Filter）是一种空间效率高、查询效率快的概率数据结构，用于检测一个元素是否属于一个集合。
然而，布隆过滤器存在一定的误判率。
为了解决这个问题，Snoop Filter被提出。
Snoop Filter是一种基于布隆过滤器的改进版本，它通过引入额外的信息来减少误判率。
布隆过滤器的基本原理布隆过滤器是由一个位数组和多个哈希函数组成的数据结构。
它的基本原理如下：1.初始化：创建一个长度为m的位数组，并将所有的位初始化为0。
2.添加元素：将待添加的元素通过多个哈希函数映射到位数组的不同位置上，并将这些位置的位设置为1。
3.查询元素：将待查询的元素通过多个哈希函数映射到位数组的不同位置上，如果这些位置的位都为1，则说明元素可能存在于集合中；如果至少有一个位置的位为0，则说明元素一定不在集合中。
布隆过滤器的优点是空间效率高，因为它只需要一个位数组和多个哈希函数即可。
但是它的缺点是存在一定的误判率，即有可能将不在集合中的元素误判为存在于集合中。
Snoop Filter的改进原理Snoop Filter在布隆过滤器的基础上进行了改进，通过引入额外的信息来减少误判率。
它的基本原理如下：1.初始化：创建一个长度为m的位数组，并将所有的位初始化为0。
2.添加元素：将待添加的元素通过多个哈希函数映射到位数组的不同位置上，并将这些位置的位设置为1。
同时，将这些位置的位与一个额外的掩码进行按位与操作，并将结果保存下来。
3.查询元素：将待查询的元素通过多个哈希函数映射到位数组的不同位置上，并将这些位置的位与保存的结果进行按位与操作。
如果结果都为1，则说明元素可能存在于集合中；如果至少有一个位置的位为0，则说明元素一定不在集合中。
Snoop Filter的改进之处在于，它在添加元素时引入了额外的掩码，并在查询元素时使用这个掩码进行按位与操作。
这样做的目的是为了减少误判率。
布隆过滤器快速判断元素是否存在的数据结构布隆过滤器（Bloom Filter）是一种快速判断元素是否存在的数据结构，它通过位数组和一系列哈希函数来实现这一目标。
布隆过滤器在大规模数据集中判断元素的存在性能优于传统的查找算法，且具有较低的空间复杂度。
一、布隆过滤器的基本原理布隆过滤器的基本原理包括初始化、插入元素和判断元素存在性三个步骤。
1. 初始化：布隆过滤器使用一个位数组（bit array）为基础数据结构，同时包含多个哈希函数。
位数组的长度通常为m位，初始时全部初始化为0。
2. 插入元素：当需要将一个元素加入到布隆过滤器中时，首先使用哈希函数对元素进行计算，将其映射到位数组中的多个位置上，并将这些位置的值设置为1。
3. 判断元素存在性：当需要判断一个元素是否存在于布隆过滤器中时，同样使用哈希函数对该元素进行计算，然后在位数组中查找对应的位置的值。
若所有位置上的值都为1，则元素可能存在于布隆过滤器中；若存在任一位置的值为0，则元素一定不存在于布隆过滤器中。
二、布隆过滤器的应用场景布隆过滤器适用于需要快速判断元素存在性，但对判断结果的精确性要求不高的场景。
它主要应用于大规模数据的快速查找、缓存击穿和垃圾邮件过滤等领域。
1. 大规模数据的快速查找：在海量数据集中，通过布隆过滤器可以快速判断某个元素是否存在，从而避免了昂贵的磁盘或数据库查询操作。
在搜索引擎、数据库等场景中，布隆过滤器可以用来过滤掉一部分明显不存在的数据，从而提高查询效率。
2. 缓存击穿的防范：当缓存中不存在某个元素时，为了防止大量请求同时查询数据库，可以使用布隆过滤器来判断元素是否一定不存在于缓存中。
如果布隆过滤器判断元素不存在，则可以提前返回给用户“数据不存在”的结果。
3. 垃圾邮件过滤：在垃圾邮件过滤中，布隆过滤器可以用来存储垃圾邮件的特征，比如发件人、邮件主题等信息。
当新的邮件到达时，通过布隆过滤器可以快速判断该邮件是否为垃圾邮件，从而进行相应的处理。
布隆过滤器原理布隆过滤器是一种数据结构，用于快速判断一个元素是否存在于一个集合中。
它的原理是基于哈希函数和位数组实现的。
哈希函数是将任意长度的输入（又叫做预映射，pre-image），通过散列算法，变换成固定长度的输出，该输出就是哈希值。
布隆过滤器使用多个哈希函数，将一个元素映射成多个位数组中的位置。
例如，如果有三个哈希函数，将一个元素映射成三个位置，分别为第1、5、9位。
如果这三个位置都为1，那么就认为该元素存在于集合中。
位数组是一种只包含0和1的数组，用于表示一个元素是否存在于集合中。
布隆过滤器使用位数组来存储元素的存在情况。
当一个元素被加入集合时，它会被哈希函数映射成多个位置，这些位置的值都被设为1。
当需要判断一个元素是否存在于集合中时，它会被哈希函数映射成多个位置，如果这些位置的值都为1，那么就认为该元素存在于集合中。
布隆过滤器的优点是空间效率和查询时间都比较优秀。
因为它只需要一个位数组和多个哈希函数，所以它的空间占用比较小。
同时，它的查询时间只需要进行多次哈希函数计算和位数组查询，所以查询时间也比较快。
但是，布隆过滤器也有一些缺点。
首先，它可能会误判一个元素存在于集合中，因为多个元素可能会映射到同一个位置上。
其次，它无法删除一个元素，因为删除一个元素可能会影响其他元素的判断结果。
最后，它的哈希函数和位数组的大小需要事先确定，如果集合的大小变化比较大，就需要重新调整哈希函数和位数组的大小。
布隆过滤器是一种比较实用的数据结构，可以用于快速判断一个元素是否存在于一个集合中。
它的原理是基于哈希函数和位数组实现的，具有空间效率和查询时间优秀的优点，但也存在误判、无法删除和哈希函数和位数组大小需要事先确定等缺点。
布隆过滤器的原理和应用场景布隆过滤器的概述布隆过滤器是一种空间效率非常高的概率型数据结构，用于判断一个元素是否在一个集合中。
它由布隆过滤器的位数组和哈希函数组成，可以高效地判断一个元素是否存在于集合中，但有一定的误判率。
布隆过滤器的原理布隆过滤器的主要原理是利用位数组和多个哈希函数来表示一个集合，并判断一个元素是否存在于集合中。
1.初始化：将位数组初始化为全0。
2.添加元素：对于要添加的元素，使用多个哈希函数计算出多个哈希值，然后将对应的位数组位置设为1。
3.判断元素：对于要判断的元素，同样使用多个哈希函数计算出多个哈希值，然后检查对应的位数组位置是否都是1。
若有任意一个位数组位置为0，则判定元素不存在于集合中；若全部位数组位置都为1，则判定元素可能存在于集合中。
布隆过滤器的优点布隆过滤器具有以下优点： - 空间效率高：布隆过滤器只需要占用很少的内存空间，比其他数据结构如散列表等要小得多。
- 查询效率高：布隆过滤器只需要进行位操作和哈希计算，所以查询效率非常高。
- 可并行处理：布隆过滤器的查询和插入操作可以并行处理，因为它们对位数组的操作没有依赖关系。
布隆过滤器的应用场景布隆过滤器在以下场景中具有较大的应用价值：1.网络爬虫中的URL去重：爬虫在抓取网页时，通常需要判断一个URL是否已经抓取过，布隆过滤器可以非常高效地进行URL去重。
2.邮件服务器中的垃圾邮件过滤：布隆过滤器可以帮助邮件服务器快速判断一封邮件是否是垃圾邮件，从而提高邮件过滤的效率。
3.分布式系统中的缓存穿透控制：布隆过滤器可以用于控制分布式系统中的缓存穿透问题，减轻数据库压力。
4.数据库查询缓存：布隆过滤器可以用于缓存数据库的部分查询结果，提高数据库查询效率。
布隆过滤器的误判率布隆过滤器的误判率是根据哈希函数的数量和位数组的大小决定的。
误判率主要取决于以下两个因素： - 哈希函数的数量：哈希函数越多，误判率越低，但算法的效率也会降低。
布隆过滤器(Bloom Filter)是由Burton Howard Bloom于1970年提出，它是一种space efficient的概率型数据结构，用于判断一个元素是否在集合中。
在垃圾邮件过滤的黑白名单方法、爬虫(Crawler)的网址判重模块中等等经常被用到。
哈希表也能用于判断元素是否在集合中，但是布隆过滤器只需要哈希表的1/8或1/4的空间复杂度就能完成同样的问题。
布隆过滤器可以插入元素，但不可以删除
已有元素。
其中的元素越多，false positive rate(误报率)越大，但是false negative (漏报)是不可能的。
一. 算法描述一个empty bloom filter是一个有m bits的bit array，每一个bit位都初始化为0。
并且定义有k个不同的hash function，每个都以uniform random distribution将元素hash到m个不同位置中的一个。
在下面的介绍中n为元素数，m为布隆过滤器或哈希表的slot数，k为布隆过滤器重hash function数。
为了add一个元素，用k个hash function将它hash得到bloom filter中k个bit位，将这k个bit位置1。
为了query一个元素，即判断它是否在集合中，用k个hash function将它hash得到k个bit位。
若这k bits全为1，则此元素在集合中；若其中任一位不为1，则此元素比不在集合中（因为如果在，则在add时已经把对应的k个bits位置为1）。
不允许remove元素，因为那样的话会把相应的k个bits位置为0，而其中很有可能有其他元素对应的位。
因此remove会引入false negative，这是绝对不被允许的。
当k很大时，设计k个独立的hash function是不现实并且困难的。
对于一个输出范围很大的hash function（例如MD5产生的128 bits数），如果不同bit位的相关性很小，则可把此输出分割为k份。
或者可将k个不同的初始值（例如0,1,2, … ,k-1）结合元素，feed 给一个hash function从而产生k个不同的数。
当add的元素过多时，即n/m过大时（n是元素数，m是bloom filter的bits数），会导致false positive过高，此时就需要重新组建filter，但这种情况相对少见。
二. 时间和空间上的优势
当可以承受一些误报时，布隆过滤器比其它表示集合的数据结构有着很大的空间优势。
例如self-balance BST, tries, hash table或者array, chain，它们中大多数至少都要存储元素本身，对于小整数需要少量的bits，对于字符串则需要任意多的bits（tries是个例外，因为对于有相同prefixes的元素可以共享存储空间）；而chain结构还需要为存储指针付出额外的代价。
对于一个有1%误报率和一个最优k值的布隆过滤器来说，无论元素的类型及大小，每个元素只需要9.6 bits来存储。
这个优点一部分继承自array的紧凑性，一部分来源于它的概率性。
如果你认为1%的误报率太高，那么对每个元素每增加4.8 bits，我们就可将误报率降低为原来的1/10。
add和query的时间复杂度都为O(k)，与集合中元素的多少无关，这是其他数据结构都不能完成的。
如果可能元素范围不是很大，并且大多数都在集合中，则使用确定性的bit array远远胜过使用布隆过滤器。
因为bit array对于每个可能的元素空间上只需要1 bit，add和query的时间复杂度只有O(1)。
注意到这样一个哈希表（bit array）只有在忽略collision并且只存储元素是否在其中的二进制信息时，才会获得空间和时间上的优势，而在此情况下，它就有效地称为了k=1的布隆过滤器。
而当考虑到collision时，对于有m个slot的bit array或者其他哈希表（即k=1的布隆过滤器），如果想要保证1%的误判率，则这个bit array只能存储m/100个元素，因而有大量的空间被浪费，同时也会使得空间复杂度急剧上升，这显然不是space efficient的。
解决的方法很简单，使用k>1的布隆过滤器，即k个hash function将每个元素改为对应于k个bits，因为误判度会降低很多，并且如果参数k和m选取得好，一半的m可被置为为1，这充分说明了布隆过滤器的space efficient性。
三. 举例说明
以垃圾邮件过滤中黑白名单为例：现有1亿个email的黑名单，每个都拥有8 bytes的指纹信息，则可能的元素范围
为，对于bit array来说是根本不可能的范围，而且元素的数量（即email列表）为，相比于元素范围过于稀疏，而且还没有考虑到哈希表中的collision问题。
若采用哈希表，由于大多数采用open addressing来解决collision，而此时的search时间复杂度为：
即若哈希表半满(n/m = 1/2)，则每次search需要probe 2次，因此在保证效率的情况下哈希表的存储效率最好不超过50%。
此时每个元素占8 bytes，总空间为：
若采用Perfect hashing（这里可以采用Perfect hashing是因为主要操作是search/query，而并不是add和remove），虽然保证worst-case也只有一次probe，但是空间利用率更低，一般情况下为50%，worst-case时有不到一半的概率为25%。
若采用布隆过滤器，取k=8。
因为n为1亿，所以总共需要被置位为1，又因为在保证误判率低且k和m选取合适时，空间利用率为50%（后面会解释），所以总空间为：
所需空间比上述哈希结构小得多，并且误判率在万分之一以下。
四. 误判概率的证明和计算
假设布隆过滤器中的hash function满足simple uniform hashing假设：每个元素都等概率地hash到m个slot中的任何一个，与其它元素被hash到哪个slot无关。
若m为bit数，则对某一特定bit位在一个元素由某特定hash function插入时没有被置位为1的概率为：
则k个hash function中没有一个对其置位的概率为：
如果插入了n个元素，但都未将其置位的概率为：
则此位被置位的概率为：
现在考虑query阶段，若对应某个待query元素的k bits全部置位为1，则可判定其在集合中。
因此将某元素误判的概率为：
由于，并且当m很大时趋近于0，所以
从上式中可以看出，当m增大或n减小时，都会使得误判率减小，这也符合直觉。
现在计算对于给定的m和n，k为何值时可以使得误判率最低。
设误判率为k的函数为：
设，则简化为
，两边取对数
, 两边对k求导
下面求最值
因此，即当时误判率最低，此时误判率为：
可以看出若要使得误判率≤1/2，则：
这说明了若想保持某固定误判率不变，布隆过滤器的bit数m与被add的元素数n应该是线性同步增加的。
五. 设计和应用布隆过滤器的方法
应用时首先要先由用户决定要add的元素数n和希望的误差率P。
这也是一个设计完整的布隆过滤器需要用户输入的仅有的两个参数，之后的所有参数将由系统计算，并由此建立布隆过滤器。
系统首先要计算需要的内存大小m bits:
再由m，n得到hash function的个数：
至此系统所需的参数已经备齐，接下来add n个元素至布隆过滤器中，再进行query。
根据公式，当k最优时：
因此可验证当P=1%时，存储每个元素需要9.6 bits：
而每当想将误判率降低为原来的1/10，则存储每个元素需要增加4.8 bits：
这里需要特别注意的是，9.6 bits/element不仅包含了被置为1的k位，还把包含了没有被置为1的一些位数。
此时的
才是每个元素对应的为1的bit位数。
从而使得P(error)最小时，我们注意到：
中的，即
此概率为某bit位在插入n个元素后未被置位的概率。
因此，想保持错误率低，布隆过滤器的空间使用率需为50%。
