背景

对于大数据集合，如何判断某个元素或子集合元素在该大数据集合中。
如果将大数据集合存入数据库再进行查询，有查询效率问题。
如果将大数据集合存入内存集合中，有内存容量问题。

原理

我们都知道针对没一个元素，我们有一种哈希算法可以获取到一个int类型的数值，当然我们也知道，存在哈希冲突的概念，也就是不同元素哈希出来的数值先等。
如果我们先不考虑冲突的情况，是不是只要有一个int类型大小的哈希表，就可以将每一个元素唯一映射到表对应的下标上。而且由于我们知道需要知道是否存在，所以这个哈希表的存储内容只需要存储一个0/1即可，也就是1bit，想想看，2^31=21亿多bit，也就250Mb左右的空间，就能存储下21亿个元素的存在信息，且查询复杂度非常低。
基于这个思路，我们再来考虑哈希冲突的问题，我们都知道解决哈希冲突的其中一个方案就是重哈希，说白了就多定义几个哈希函数，然后同样按上述的方案进行置1。比如我们以3次哈希为例，首先我们认为不存在3次哈希之后还冲突的元素。那这样的话，上述的空间要增加3倍或则可处理数据要减少3倍了，但依然不失为一个非常高效的判重工具。
在查询的时候，同样将元素进行3次哈希，判断哈希结果对应下标下的值是否为1，如果不是1，那该元素肯定不存在，如果3个都是1，就一定能确定该值存在吗，不一定，因为比如元素1下标是123，元素2下标是345，元素3下标是567，元素4下标是789，那么查询某元素哈希出来357（实际不存在），也会被认为存在。这就是我们要说到布隆过滤器的缺点：存在误判概率。稍微思考就知道，该概率和元素数量+哈希表容量有关，即越密集误判概览越高。
而且无法删除数据，很显然因为同样的原因，因为不能保证删除的下标只有当前元素在用。

redis实现

redis通过bitmap数据结构来实现，因为位图天然适合用于存储bit结构数据。
java内存中可以用guava的BloomFilter来处理。

和hyperloglog的区别

BloomFilter用于判重，hyperloglog用于统计基数，两者相同点在于

  1. 都是基于无需存储元素的具体内容，而只需要存储元素是否存在的特点，通过哈希+bit存储，极大降低大量数据的存储空间。
  2. 都有误差。

    再次思考

    位图：基于对【某个元素是否存在在于某个集合中】这个需求的抽象，一般实现这个最暴力的方案是将所有元素存储到集合中（这里就要考虑元素数量和内存大小），拿到某个元素进行遍历，如果遍历结束前能找到同样的元素（这里就要考虑元素的对比以及遍历的效率）。拎出算法中我们最关心的两个点时间和空间复杂度。我们可以思考下，查找元素最优秀的方案是什么？显然不是遍历而是散列表，所以我们第一步优化就是将元素放入散列表中，时间解决了再来看空间，元素的信息是不可控的，一个元素可能是string也可能是更复杂的对象，就算是string如手机号和ip和文章标题等那占用空间也是不一样的，所以我们就要想有没有可能不存储元素，所以可以想到用hash函数来简化要存储的对象，但是hash有冲突如何处理，其中有一种方案是重hash，也就是我们可以hash出多个值出来放入散列表，再考虑我们是否一定要散列表？是否可以用hash值本身作为下标来表示是否存在，也就是二元的01，这就是bitmap的原理了。
    布隆过滤器：我们想下，hash函数的出参是一个int值，而int最大值是21亿左右，如果有一个21亿位的bitmap（大概占用内存250M），那么每一个int值都可以唯一在该位图上找到一个01信息，就可以判断21亿个数的存在信息。但实际情况中不太会有这么多数据，可能我只有几百万几千万的数据需要处理，如果也用21亿位图肯定没问题，但是占用内存太多了，那我就想是不是可以少点，那我们就要想，但凡散列表的size小于hash函数的范围，最大值就有可能出现哈希冲突（注意这里对比的范围是所有hash函数的可能取值也就是21亿，而不是元素数量，当然有一种情况例外，就是元素本身就是int值且有唯一性，比如元素内容是7位数的id最大也就是1KW，这时候就推荐不要用hash函数再处理一遍了，反而增大了范围，可以直接用元素本身作为散列表下标，这样既能避免散列，又可以直接根据元素数量来给定位图位数），由于位图的特点，我们不能和hashmap一样用拉链法解决，所以我们考虑用再hash来处理，但问题是我们在查询的时候也不知道哪些元素是经过多次hash去查找的，所以就需要对所有元素进行多次哈希，比如3次，我们认为不存在3次哈希出来的下标都冲突的两个不同元素，但多了另外一种情况，就是某个元素的3个哈希下标被其他多个元素的部分下标并集后占用，导致一个不存在的元素也可能找到其3个下标都是1。带来的好处就是可以减少空间成本，用更少量的位图大小来存储数据。而前者就是要承担的副作用。
    HLL：对于一个输入的字符串，首先得到64位的hash值。 用前14位来定位桶的位置，即桶的位个数为2^14个16384个。后面50位为伯努利过程（抛硬币的过程），每个桶有6bit，记录第一次出现1的位置count（6bit最大能表示64-1，63 > 50，满足条件），如果count > oldcount，就用count替换oldcount。 用于统计一个元素集合内出现基数也就是distinct(count(1))，要注意的是它不能用于判断元素是否存在（理论应该也可以，是否可以在pfadd命令中，如果添加结果为成功认为存在，失败认为不存在？）。