布隆过滤器的实现过程极其简单,同时具有非常高的储存效率和查询效率,因此在很多场景下十分有用。 首先,布隆过滤器作为基于选择的搜索引擎,可以被用于快速搜索某个字符串或者元素是否在一个大型字典中出现过。这类搜索引擎是应用在许多互联网公司的非常有用的组件,用于快速地搜索网站的URL和网页内容,例如Google的PageRank...
System.out.println("布隆过滤器元素总数为:" + bloomFilter.count());//布隆过滤器元素总数为:4System.out.println("是否包含kg:" + bloomFilter.contains("tom"));//是否包含kg:trueSystem.out.println("是否包含app:" + bloomFilter.contains("lei"));//是否包含app:falseclient.shutdown(); }...
4、使用场景 (1)google的guava包中有对Bloom Filter的实现 (2)通常使用布隆过滤器去解决redis中的缓存穿透,解决方案是redis中bitmap的实现, (3)钓鱼网站、垃圾邮件检测 大体就这些,可能还有很多!!! 二、代码实现布隆过滤器 上面只是给出了其原理,下面我们代码实现一下。 publicclassMyBloomFilter{// 2 << 25...
布隆过滤器是一个 bit 向量或者说 bit 数组,长这样: 如果我们要映射一个值到布隆过滤器中,我们需要使用多个不同的哈希函数生成多个哈希值,并对每个生成的哈希值指向的 bit 位置 1,例如针对值 “baidu” 和三个不同的哈希函数分别生成了哈希值 1、4、7,则上图转变为: Ok,我们现在再存一个值 “tencent”,...
布隆过滤器的使用场景: 由于布隆过滤器的空间效率和概率性特点,它在各种场景中得到广泛应用。以下是一些常见的使用场景: 缓存: 布隆过滤器可用于快速确定请求的项目是否存在于缓存中,从而避免不必要的磁盘I/O操作。 网络安全: 在网络安全应用中,布隆过滤器©...
布隆过滤器的巨大用处就是,能够迅速判断一个元素是否在一个集合中。因此他有如下三个使用场景: 网页爬虫对URL的去重,避免爬取相同的URL地址 反垃圾邮件,从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱(同理,垃圾短信) 缓存穿透,将所有可能存在的数据缓存放到布隆过滤器中,当黑客访问不存在的缓存时迅速返回避免缓存...
布隆过滤器是一种数据结构,特点是高效的插入和查询,而且非常节省空间。通过对位(bit)的操作,可以用来告诉你”某个值一定不存在或者可能存在“。相比于传统的 List、Set、Map 等数据结构,它更高效、占用空间更少,但是缺点是 hash 碰撞造成的误判。 场景
场景:不安全网页的黑名单包含100亿个黑名单网页,每个网页的URL最多占用64字节。现在想要实现一种网页过滤系统,可以根据网页的URL判断该网站是否在黑名单上,请设计该系统。要求该系统允许有万分之一以下的判断失误率,并且使用的额外空间不要超过30G。 思路:布隆过滤器的bitarray大小如何确定?
布隆过滤器使用场景 数据库查询: 在查询数据库之前,先检查布隆过滤器。如果布隆过滤器表示元素可能存在,再进行数据库查询;否则直接返回不存在。 URL黑名单: 可以使用布隆过滤器来检查URL是否在黑名单中,从而避免访问恶意网站。 垃圾邮件过滤: 对邮件内容进行哈希,使用布隆过滤器检查是否是垃圾邮件。