布隆过滤器应用场景在实际中，大家都收到过各类的垃圾邮件，垃圾短信，但一般来说，邮箱都会主动帮助你过滤垃圾邮件。那么邮箱是怎么做到的呢？某个接口被调用太多次，是不是服务器受到攻击呢？如何加速比特币客户端？海量违法网站如何快速检测？我们来看下缓存穿透。为了减轻落盘数据库mysql的压力，一般都会在mysql和server中间加入一层热点缓冲数据库(redis)当请求大量不存在的数据时，redis没有查到，大量请求给到mysql。请求步骤如下图所示发生原因大多数是：不法分子利用漏洞伪造数据攻击或者内部业务bug来重复请求大量不存在的数据。我们来看下缓存穿透的解决方案1.在redis端设置key,null键值对，以此避免访问mysql，并且需要定时expirekeyms.2.在server端设置一个布隆过滤器，将需要请求的数据放入布隆过滤器中，布隆过滤器可以过滤一定不存在的数据。所以我们的需求即为：从海量字符串查询某个字符串是否存在

我们想到使用c++中的setmap容器。由于内部使用红黑树，所以他的综合效率非常好。但试想一下，如果有w的字符串，假设每个字符串长度平均下来是20个字节，单个节点约占40个字节左右，w*40bit/(*)=38.GB，可能此时你的服务器内存要炸开了。你的进程就被kill掉了。

我们也很容易想到c++中的unorderedmapstd::string,bool,内部使用哈希表数据结构。

利用一个数组+哈希函数即可构成。内部是将字符串通过hash函数生成一个整数在映射到数组中，他的增删查改的时间复杂度是o(1),可以说非常快了。hash函数一般返回的是一个64位整数，计算出来的值通常会对数组取模分配在数组之中。但当数据量庞大时，也就会引起hash冲突。hash冲突解决方案链表法将冲突元素用链表链接起来；当链表元素太多时，一般都把该链表转换为红黑树。

开放寻址法

插入时，使用哈希函数定位元素位置若不存在，直接插入即可若存在，则需要加一定步长来接着检查，步长一般来说不是固定的。当插入新的元素冲突时，一般使用线性探查的方案

双重散列哈希

这里不展开介绍，感兴趣可以看看这一篇博客[

转载请注明:http://www.aideyishus.com/lkzp/111.html