见龙在田，利见大人。 —— 《易经》之乾卦的第二爻(九二爻) 译为一个胸怀大志的人，已经崭露头角。今指一个人仕途顺利，初露锋芒，得到领导的赏识，前途光明。
一、基础
概念
布隆过滤器(Bloom Filter)是1970年由布隆提出的，是一个很长的二进制向量和一系列随机映射函数。实质上，它是一种概率型数据结构(probabilistic data structure)，其特点是高效地插入和查询，可以用来快速判断某个元素存在或不存在，空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。它被广泛用于网页黑名单系统、垃圾邮件过滤系统、爬虫的网址判重系统以及解决缓存穿透问题。原理
- 布隆过滤器是一个bit向量或者说bit数组
布隆过滤器离不开哈希函数，它有如下特点
- 经典的哈希函数都有无限大的输入值域(无穷大)。
- 经典的哈希函数的输出域都是固定的范围(有穷大，假设输出域为S)
- 当给哈希函数传入相同的值时，返回值必一样
- 当给哈希函数传入不同的输入值时，返回值可能一样，也可能不一样。
- 输入值会尽可能均匀的分布在S上
如果我们要映射一个值到布隆过滤器中，需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的bit位设为1，例如针对值“baidu”和三个不同的哈希函数分别生成了哈希值1、4、7，则上图转变为：
- 再存一个值“tencent”，假设三个不同的哈希函数得到的哈希值分别为3、4、8，图继续变为：
- 如图，4这个bit位由于两个值的哈希函数都返回了这个bit位，因此它被覆盖了。
- 当需要查询“dianping”这个值是否存在，假设三个哈希函数分别得到哈希值1、5、8。结果发现5这个bit位上的值为0，说明没有任何一个值映射到这个bit位上，因此可以很确定地说“dianping”这个值不存在。
- 当需要查询“baidu”这个值是否存在，那么三个哈希函数肯定会拿到1、4、7三个值。然后发现这三个bit位上的值均为1，那么可以说“baidu”这个值可能存在，即哈希冲突的问题。
- 适用场景
- 爬虫URL去重
- 缓存穿透问题
二、使用
- 使用原生bitmap
- 使用bloom-filter模块
全置为1的问题