布隆过滤器的实现

布隆过滤器
需求

①、原本有10亿个号码，现在又来了10万个号码，要快速准确判断这10万个号码是否在10亿个号码库中？ 解决办法一：将10亿个号码存入数据库中，进行数据库查询，准确性有了，但是速度会比较慢。 解决办法二：将10亿号码放入内存中，比如Redis缓存中，这里我们算一下占用内存大小：10亿*8字节=8GB，通过内存查询，准确性和速度都有了，但是大约8gb的内存空间，挺浪费内存空间的。
②、接触过爬虫的，应该有这么一个需求，需要爬虫的网站千千万万，对于一个新的网站url，我们如何判断这个url我们是否已经爬过了？ 解决办法还是上面的两种，很显然，都不太好。
③、同理还有垃圾邮箱的过滤 大数据量集合，如何准确快速的判断某个数据是否在大数据量集合中，并且不占用内存。

布隆过滤器定义
一种数据结构，是由一串很长的二进制向量组成，可以将其看成一个二进制数组。既然是二进制，那么里面存放的不是0，就是1，但是初始默认值都是0。将布隆过滤器看成一个容器，那么如何向布隆过滤器中添加一个数据呢？数组是从0开始计数的，当要向布隆过滤器中添加一个元素key时，我们通过多个hash函数，算出一个值，然后将这个值所在的方格置为1。

布隆过滤器判断数据是否存在？
将这个新的数据通过自定义的几个哈希函数，分别算出各个值，然后看其对应的地方是否都是1，如果存在一个不是1的情况，那么我们可以说，该新数据一定不存在于这个布隆过滤器中。多个不同的数据通过hash函数算出来的结果是会有重复的，所以会存在某个位置是别的数据通过hash函数置为的1。布隆过滤器可以判断某个数据一定不存在，但是无法判断一定存在。

布隆过滤器优缺点
优点：二进制组成的数组，占用内存极少，并且插入和查询速度都足够快。
缺点：随着数据的增加，误判率会增加，无法判断数据一定存在，无法删除数据。

布隆过滤器的实现
guava 工具包提供了布隆过滤器的实现。
Redis 实现布隆过滤器的底层就是通过 bitmap数据结构实现的，计算机以二进制位作为底层存储的基础单位，一个字节等于8位，可以通过修改二进制某个位置上的0或者1达到修改值的目的。比如：将big改为cig，"b"的二进制表示为0110 0010，我们将第7位（从0开始）设置为1，那0110 0011表示的就是字符“c”，所以最后的字符 “big”变成了“cig”。
Redis分布式寻址算法
在集群模式下，Redis 的 key 是如何寻址的？分布式寻址都有哪些算法？了解一致性 hash 算法吗？如何动态增加和删除一个节点？

hash 算法（大量缓存重建） 一致性 hash 算法（自动缓存迁移）+ 虚拟节点（自动负载均衡） Redis cluster 的 hash slot 算法

hash 算法
来了一个 key，首先计算 hash 值，然后对节点数取模，接着打在不同的 master 节点上。缺点也很明显：某一个 master 节点宕机，所有请求过来，都会基于最新的剩余 master 节点数去取模，尝试去库中取数据进行缓存。这会导致大部分的请求过来，全部无法拿到有效的缓存，导致大量的流量涌入数据库。

一致性 hash 算法
将整个 hash 值空间组织成一个虚拟的圆环，整个空间按顺时针方向组织，下一步将各个 master 节点（使用服务器的 ip 或主机名）进行 hash。来了一个 key，首先计算 hash 值，并确定此数据在环上的位置，从此位置沿环顺时针“行走”，遇到的第一个 master 节点就是 key 所在位置，这样就能确定每个节点在其哈希环上的位置。在一致性哈希算法中，如果一个节点挂了，受影响的数据仅仅是此节点到环空间前一个节点（沿着逆时针方向行走遇到的第一个节点）之间的数据，其它不受影响。增加一个节点也同理。 虚拟节点：一致性哈希算法在节点太少时，容易因为节点分布不均匀而造成缓存热点的问题。为了解决这种热点问题，一致性 hash 算法引入了虚拟节点机制，即对每一个节点计算多个 hash，每个计算结果位置都放置一个虚拟节点。这样就实现了数据的均匀分布，负载均衡。

hash slot 算法
Redis cluster 有固定的 16384 个 hash slot，slot是槽的概念（理解为数据管理和迁移的基本单位），所有的键根据哈希函数映射到 0~16383 整数槽内，每个节点负责维护一