思路：从简单的排序谈到BitMap算法，再谈到数据去重问题，谈到大数据量处理利器：布隆过滤器。
情景1：对无重复的数据进行排序
@给定数据（2，4，1，12，9，7，6）如何对它排序？
方法1：基本的排序方法包括冒泡，快排等。
方法2：使用BitMap算法
方法1就不介绍了，方法2中所谓的BitMap是一个位数组，跟平时使用的数组的唯一差别在于操作的是位。
首先是开辟2个字节大小的位数组，长度为16（该长度由上述数据中最大的数字12决定的）如图
然后，读取数据，2存放在位数组中下标为1的地方，值从0改为1，4存放在下标为3的地方，值从0改为1....结果如图
最后，读取该位数组，得到排好序的数据是：（1，2，4，6，7，9，12）
比较方法1和方法2的差别：方法2中，排序需要的时间复杂度和空间复杂度很依赖与数据中最大的数字比如12，因此空间上讲需要开2个字节大小的内存，时间上需要遍历完整个数组。当数据类似（1，1000，10万）只有3个数据的时候，显然用方法2，时间复杂度和空间复杂度相当大，但是当数据比较密集时该方法就会显示出来优势。
情景2：对有重复的数据进行判重
数据（2，4，1，12，2，9，7，6，1，4）如何找出重复出现的数字？
首先是开辟2个字节大小的位数组，长度为16（该长度由上述数据中最大的数字12决定的）如图
当读取完12后，数组中的数据如下图：
当读取2的时候，发现数组中的值是1，则判断出2是重复出现的。
应用
应用1：某文件中包含一些8位的电话号码，统计出现的号码的个数？（判断有谁出现）
8为最大是99 999 999，大约是99M的bit，12.5MB的内存，就可以统计出来出现的号码。
应用2：某文件中包含一些8位的电话号码，统计只出现一次的号码？（判断有谁出现并且指出现1次）
需要扩展一下，可以用两个bit表示一个号码，0代表没有出现过，1代表只出现过1次，2代表至少出现2次。
应用3：有两个文件，文件1中有1亿个10位的qq号码，文件2中有5千万个10位qq号码，判断两个文件中重复出现的qq号。
首先建立10的10次方个大小的位数组（占用内存大约是1.25G），全部初始化为0，读取第一个文件，对应的qq号存放到对应的未知，数值改为1，如果重复出现仍是1.读取完毕第一个文件后，读取第二个文件，对应的位置为1则表示重复出现。
应用4：有两个文件，文件1中有1亿个15位的qq号码，文件2中有5千万个15位的qq号码，判断两个文件中重复出现的qq号。
应用4中，qq号码上升为15位的时候，显然内存是不够用了，这个时候怎么办？使用Bloom Filter（布隆过滤器）
Bloom Filter（布隆过滤器）：
对于Bit-Map分析一下，每次都会开辟一块表示最大数值大小的bit数组，比如情景1中的16，将对应的数据经过映射到bit数组的下标，这其实是一种最简单的hash算法，对1去模。在上述应用4中，当qq号码改为15位的时候，Bit-Map就不太好用了，如何改进呢？解决办法：减少bit数组的长度，但是增加hash函数的个数
对于每一个qq号码，我用K个hash函数，经过k次映射，得到k个不同位置，假设k=3，那么对于一个qq号码，映射到位数组中3个不同的位置
当读取第二个包含5千万个qq号码的文件的时候，使用同样的3个hash函数进行映射，当3个位置全部是1的时候才表示出现过，否则表示没有出现过。
有什么疑问吗？
显然，对于一个qq号码，如果它在第一个文件中没有出现过，但是它映射的3个位置已经全部是1的情况会有吗？答案是会的，但是这种概率是可控的，可控的意思是：这种误差跟hash函数的个数和质量是有关系的，可以通过控制hash函数的个数和位数组的大小来控制误差概率。至于表示3者之间的关系精确的数学公式就不再详细研究了。
可以这样讲，布隆过滤器是Bit-Map的进一步扩展，对于大数据量判重，布隆过滤器可以在内存中进行判断，避免了对磁盘的读写，效率是很高的。以上是自己关于两者的理解，有错误望指教。
分享到：
相关推荐
布隆过滤器是一种高效的数据结构，特别适用于大数据集的快速查询场景。通过本篇文章的学习，我们不仅了解了布隆过滤器的基本原理，还通过具体的C/C++实现代码深入理解了其内部机制。在未来的工作中，可以根据具体...
布隆过滤器是一种空间效率极高的概率型数据结构，用于判断一个元素是否可能在一个集合中。在Go语言中实现一个简单的布隆过滤器可以帮助我们高效地处理大数据集，尤其是在内存有限的情况下。以下是对这个主题的详细...
布隆过滤器的优点是：空间效率高，可以在使用有限内存的情况下处理海量数据；插入和查询都是常数复杂度，即 O(k)。缺点是：存在误判；删除元素困难，因为简单地将对应的位置 0 会影响其他元素的判断。 在 LevelDB ...
布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，用于判断一个元素是否在一个集合中。它可能会误判，但不会漏判，即如果它说一个元素在集合中，那可能是错误的，但如果它说一个元素不在集合中，那么...
在Java开发中，特别是在处理大数据、内存限制或需要快速查询是否存在某个元素的场景下，布隆过滤器是一个非常实用的工具。`krisives-jbloomer-7afec7a`这个压缩包文件很可能包含了一个简单的Java实现的布隆过滤器库...
布隆过滤器是一种概率数据结构，用于判断一个元素是否可能在一个集合中存在。它通过使用位数组和几个独立的哈希函数来实现，具有高效、节省空间的特点，但可能会产生假阳性错误，即误判一个不在集合中的元素为在集合...
布隆过滤器是一种空间效率极高的概率型数据结构，用于判断一个元素是否可能在一个集合中。它是由 Burton Howard Bloom 在1970年提出的，主要应用于大数据和分布式系统中，以减少内存消耗并提高查询效率。在C语言实现...
布隆过滤器是一种空间效率极高的概率型数据结构，用于判断一个元素是否可能在一个集合中。它是由 Burton Howard Bloom 在1970年提出的，主要应用于大数据存储和检索，尤其在数据库、缓存系统和网络搜索等领域有广泛...
做成dll可以在很多场合使用，如自己写爬虫，要判断一个url是否已经访问过，判断一个单词是否在某个字典内，当集合很大的时候，用布隆过滤器很有优势，不过使用前，请了解它的优缺点（缺点是有一定的误判率）
总之，Go语言的布隆过滤器实现是通过结合其语言特性，如并发处理和内存模型，来提供一个高效且灵活的数据结构，用于处理大规模数据集的成员资格查询。通过分析`kevburnsjr-bloomfilter-dde4081`中的源代码，我们可以...
通过理解和掌握布隆过滤器，我们可以更有效地处理大规模数据，尤其是在资源有限的环境中。虽然它有误判的风险，但在很多场景下，这种小概率的误判是可以接受的，换取的是显著的空间节省和性能提升。
布隆过滤器是一种概率型数据结构，用于判断一个元素是否可能在一个集合中存在。它由布伦南·布隆在1970年提出，主要应用于大数据存储和检索，尤其是在空间效率和查询效率方面有着显著优势。由于布隆过滤器会存在一定...
布隆过滤器是一种高效的空间节省的数据结构，用于判断一个元素是否可能在一个集合中，但可能会产生一定的误判率。它由一个很长的二进制向量和多个独立的哈希函数组成。布隆过滤器的基本原理是，当一个元素被添加到...
布隆过滤器，大家学过数据结构的应该都清楚，一般的字典树要实现嵌入和查找都内存的消耗非常大，布隆过滤器有BloomFilter,string, BKDRHash, APHash, DJBHash> bf五个参数你要查找的元素个数，查找元素类型，三个...
Redis布隆过滤器插件是Redis数据库中一个非常实用的扩展功能，主要用于高效地判断一个元素是否可能存在于集合中。由于其独特的数据结构和算法，它在存储空间和查询效率之间取得了良好的平衡，尤其适用于大数据场景下...
布隆过滤器是一种空间效率高、查询速度快的概率性数据结构，广泛应用于大规模数据处理、网络爬虫、云计算等领域。然而，在分布式网络爬虫应用中，布隆过滤器仍然存在一些缺陷，例如误判率高、容忍能力差等问题。本文...
布隆过滤器是一种概率型数据结构，用于判断一个元素是否可能在一个集合中存在。它在处理大量数据时，能够高效地进行存在性查询，而牺牲一定的误判率。在PHP和Redis结合应用中，布隆过滤器常被用来解决缓存穿透问题，...
布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，用于判断一个元素是否可能在一个集合中。由布隆在1970年提出，它不像传统的数据结构如哈希表那样保证不误判，而是允许有一定的错误率。这种特性使得...
布隆过滤器是一种高效的空间节省的数据结构，常用于判断一个元素是否可能在一个大规模集合中存在。它是由 Burton Howard Bloom 在1970年提出的，因此得名“布隆过滤器”。在Java中，我们可以利用开源库如RedisBloom...
由于布隆过滤器可能会产生假阳性（误判一个元素存在于集合中），但不会产生假阴性（误判一个元素不存在于集合中），因此在处理大规模数据时，它比传统数据结构更为高效。 RedisBloom模块为Redis提供了以下主要功能...