2020-10-26 18:46发布
在 1970 年的时候，有一个叫做布隆的前辈对于判断海量元素中元素是否存在的问题进行了研究，也就是到底需要多大的位图容量和多少个哈希函数，它发表了一篇论文，提出的这个容器就叫做布隆过滤器。
大家来看下这个图，我们看集合里面3个元素，现在我们要存了，比如说a，经过f1(a)，f2(a)，f3(a)经过三个哈希函数的计算，在相应的位置上存入1，元素b，c也是通过这三个函数计算放入相应的位置。当取的时候，元素a通过f1(a)函数计算，发现这个位置上是1，没问题，第二个位置也是1，第三个位置上也是 1，这时候我们说这个a在布隆过滤器中是存在的，没毛病，同理我们看下面的这个d，通过三次计算发现得到的结果也都是1，那么我们能说d在布隆过滤器中是存在的吗，显然是不行的，我们仔细看d得到的三个1其实是f1(a)，f1(b)，f2(c)存进去的，并不是d自己存进去的，这个还是哈希碰撞导致的，我们把这种本来不存在布隆过滤器中的元素误判为存在的情况叫做假阳性（False Positive Probability，FPP）。
我们再来看另一个元素，e 元素。我们要判断它在容器里面是否存在，一样地要用这三个函数去计算。第一个位置是 1，第二个位置是 1，第三个位置是 0。那么e元素能不能判断是否在布隆过滤器中？答案是肯定的，e一定不存在。你想啊，如果e存在的话，他存进去的时候这三个位置都置为1，现在查出来有一个位置是0，证明他没存进去啊。。通过上面这张图加说明，我们得出两个重要的结论
从容器的角度来说：如果布隆过滤器判断元素在集合中存在，不一定存在如果布隆过滤器判断不存在，一定不存在
从容器的角度来说：
从元素的角度来说：如果元素实际存在，布隆过滤器一定判断存在如果元素实际不存在，布隆过滤器可能判断存在
从元素的角度来说：
布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
可以把布隆过滤器理解为一个不怎么精确的set结构,当你使用它的 contains方法判断某个对象是否存在时,它可能会误判。 但是布隆过滤器也不是特别不精确,只要参数设置得合理,它的精确度也可以控制得相对足够精确,只会有小小的误判概率。当布隆过滤器说某个值存在时,这个值可能不存在; 当它说某个值不存在时,那就肯定不存在。 打个比方,当它说不认识你时,肯定就是真的不认识; 而当它说认识你时,却有可能根本没见过你,只是因为你的脸跟它认识的某人的脸比较相似(某些熟脸的系数组合),所以误判以前认识你。套在上面的使用场景中,布隆过滤器能准确过滤掉那些用户已经看过的内容,那些用户没有看过的新内容, 它也会过滤掉极小一部分(误判),但是绝大多数新内容它都能准确识别。 这样就可以保证推荐给用户的内容都是无重复的。
创建test文件夹hadoop fs -mkdir /test
Hadoop的三大核心组件分别是：1、HDFS(Hadoop Distribute File System)：hadoop的数据存储工具。2、YARN(Yet Another Resource Negotiator,另一种资源协调者)：Hadoop 的资源管理器。3、Hadoop MapReduce:分布式计算框架。HDFS是一个高度容错性的系统，适合部...
hbase依靠HDFS来存储底层数据。Hadoop分布式文件系统(HDFS)为HBase提供了高可靠性的底层存储支持，HBase中的所有数据文件都存储在Hadoop HDFS文件系统上。
HBase分布式数据库具有如下的显著特点：容量大：HBase分布式数据库中的表可以存储成千上万的行和列组成的数据。面向列：HBase是面向列的存储和权限控制，并支持独立检索。列存储，其数据在表中是按照某列存储的，根据数据动态的增加列，并且可以单独对列进行...
解决问题的层面不一样首先，Hadoop和Apache Spark两者都是大数据框架，但是各自存在的目的不尽相同。Hadoop实质上更多是一个分布式数据基础设施: 它将巨大的数据集分派到一个由普通计算机组成的集群中的多个节点进行存储，意味着您不需要购买和维护昂贵的服务...
1、HBase写快读慢，HBase的读取时长通常是几毫秒，而Redis的读取时长通常是几十微秒。性能相差非常大。2、HBase和Redis都支持KV类型。但是Redis支持List、Set等更丰富的类型。3、Redis支持的数据量通常受内存限制，而HBase没有这个限制，可以存储远超内存大小...
列式存储格式是指以列为单位存储数据的数据存储格式，相比于传统的行式存储格式，它具有压缩比高、读I/O少(此处指可避免无意义的读I/O)等优点，目前被广泛应用于各种存储引擎中。对于HBase而言，它并不是一个列式存储引擎，而是列簇式存储引擎，即同一列簇中...
一、简单理解Hadoop是一个大象：一个hadoop集群主要包含三个主要的模块：Mapreduce,hdfs,yarn。mapreduce是一个分离在合并的计算框架，注意他不是一个集群，而是一个编程框架。hdfs是一个分布式文件系统，是一个分布式集群，用于存放数据。yarn集群是负责集群...
01 网络公开数据集02 数据报采集03 网络爬虫04 日志收集05 社会调查06 业务数据集07 埋点采集08 传感器采集09 数据交易平台10 个人数据收集
1 Hadoop 各个目录的解释bin：Hadoop管理脚本和使用脚本所在目录， sbin目录下的脚本都是使用此目录下的脚本实现的。etc：Hadoop的所有配置文件所在的目录，所有hadoop的配置在etc/hadoop目录下include:对外提供的库的头文件lib ：对外提供的动态编程库和静态...
HDFS存储机制，包括HDFS的写入过程和读取过程两个部分： 1、写入过程： 1）客户端向namenode请求上传文件，namenode检查目标文件是否已存在，父目录是否存在。2）namenode返回是否可以上传。3）客户端请求第一个 block上传到哪几个datanode服务器上。4）nam...
adoop核心：MapReduce原理。 MR的核心是shuffle，被称为奇迹发生的地方。 shuffle，弄乱，洗牌的意思。partition 分区，sort 排序，spill溢出，disk 磁盘下面是官方对shuffle的配图： phase 阶段，fetch 最终，merge 合并...
Shuffle阶段分为两部分:Map端和Reduce端。一 map端shuffle过程；1-内存预排序：默认每个map有100M内存进行预排序（为了效率），超过阈值，会把内容写到磁盘； 此过程使用快速排序算法；2-根据key和reducer的数量进行分区和排序；首先根据数据所属的Parti...
大数据时代需要1存储大量数据2快速的处理大量数据3从大量数据中进行分析
hadoop的四种模式。1、本地模式：本地模式就是解压源码包，不需要做任何的配置。通常用于开发调试，或者感受hadoop。2、伪分布模式：在学习当中一般都是使用这种模式，伪分布模式就是在一台机器的多个进程运行多个模块。虽然每一个模块都有相应的进程，但是却...
进入和退出安全模式 [root@localhost bin]# ./hdfs dfsadmin -safemode enter15/08/03 07:26:24 WARN util.NativeCodeLoader: Unable to load native-hadoop library for your platform... using builtin-java classes where ......
最多设置5个标签!
{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','/static/images/logo.png', '推荐 wjmmjr 的问题《布隆过滤器是什么》','http://www.shouhuola.com/q-30641.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}
在 1970 年的时候，有一个叫做布隆的前辈对于判断海量元素中元素是否存在的问题进行了研究，也就是到底需要多大的位图容量和多少个哈希函数，它发表了一篇论文，提出的这个容器就叫做布隆过滤器。
我们再来看另一个元素，e 元素。我们要判断它在容器里面是否存在，一样地要用这三个函数去计算。第一个位置是 1，第二个位置是 1，第三个位置是 0。那么e元素能不能判断是否在布隆过滤器中？答案是肯定的，e一定不存在。你想啊，如果e存在的话，他存进去的时候这三个位置都置为1，现在查出来有一个位置是0，证明他没存进去啊。。通过上面这张图加说明，我们得出两个重要的结论
布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
可以把布隆过滤器理解为一个不怎么精确的set结构,当你使用它的 contains方法判断某个对象是否存在时,它可能会误判。 但是布隆过滤器也不是特别不精确,只要参数设置得合理,它的精确度也可以控制得相对足够精确,只会有小小的误判概率。
当布隆过滤器说某个值存在时,这个值可能不存在; 当它说某个值不存在时,那就肯定不存在。 打个比方,当它说不认识你时,肯定就是真的不认识; 而当它说认识你时,却有可能根本没见过你,只是因为你的脸跟它认识的某人的脸比较相似(某些熟脸的系数组合),所以误判以前认识你。
套在上面的使用场景中,布隆过滤器能准确过滤掉那些用户已经看过的内容,那些用户没有看过的新内容, 它也会过滤掉极小一部分(误判),但是绝大多数新内容它都能准确识别。 这样就可以保证推荐给用户的内容都是无重复的。
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
相关问题推荐
创建test文件夹hadoop fs -mkdir /test
Hadoop的三大核心组件分别是：1、HDFS(Hadoop Distribute File System)：hadoop的数据存储工具。2、YARN(Yet Another Resource Negotiator,另一种资源协调者)：Hadoop 的资源管理器。3、Hadoop MapReduce:分布式计算框架。HDFS是一个高度容错性的系统，适合部...
hbase依靠HDFS来存储底层数据。Hadoop分布式文件系统(HDFS)为HBase提供了高可靠性的底层存储支持，HBase中的所有数据文件都存储在Hadoop HDFS文件系统上。
HBase分布式数据库具有如下的显著特点：容量大：HBase分布式数据库中的表可以存储成千上万的行和列组成的数据。面向列：HBase是面向列的存储和权限控制，并支持独立检索。列存储，其数据在表中是按照某列存储的，根据数据动态的增加列，并且可以单独对列进行...
解决问题的层面不一样首先，Hadoop和Apache Spark两者都是大数据框架，但是各自存在的目的不尽相同。Hadoop实质上更多是一个分布式数据基础设施: 它将巨大的数据集分派到一个由普通计算机组成的集群中的多个节点进行存储，意味着您不需要购买和维护昂贵的服务...
1、HBase写快读慢，HBase的读取时长通常是几毫秒，而Redis的读取时长通常是几十微秒。性能相差非常大。2、HBase和Redis都支持KV类型。但是Redis支持List、Set等更丰富的类型。3、Redis支持的数据量通常受内存限制，而HBase没有这个限制，可以存储远超内存大小...
列式存储格式是指以列为单位存储数据的数据存储格式，相比于传统的行式存储格式，它具有压缩比高、读I/O少(此处指可避免无意义的读I/O)等优点，目前被广泛应用于各种存储引擎中。对于HBase而言，它并不是一个列式存储引擎，而是列簇式存储引擎，即同一列簇中...
一、简单理解Hadoop是一个大象：一个hadoop集群主要包含三个主要的模块：Mapreduce,hdfs,yarn。mapreduce是一个分离在合并的计算框架，注意他不是一个集群，而是一个编程框架。hdfs是一个分布式文件系统，是一个分布式集群，用于存放数据。yarn集群是负责集群...
01 网络公开数据集02 数据报采集03 网络爬虫04 日志收集05 社会调查06 业务数据集07 埋点采集08 传感器采集09 数据交易平台10 个人数据收集
1 Hadoop 各个目录的解释bin：Hadoop管理脚本和使用脚本所在目录， sbin目录下的脚本都是使用此目录下的脚本实现的。etc：Hadoop的所有配置文件所在的目录，所有hadoop的配置在etc/hadoop目录下include:对外提供的库的头文件lib ：对外提供的动态编程库和静态...
HDFS存储机制，包括HDFS的写入过程和读取过程两个部分： 1、写入过程： 1）客户端向namenode请求上传文件，namenode检查目标文件是否已存在，父目录是否存在。2）namenode返回是否可以上传。3）客户端请求第一个 block上传到哪几个datanode服务器上。4）nam...
adoop核心：MapReduce原理。 MR的核心是shuffle，被称为奇迹发生的地方。 shuffle，弄乱，洗牌的意思。partition 分区，sort 排序，spill溢出，disk 磁盘下面是官方对shuffle的配图： phase 阶段，fetch 最终，merge 合并...
Shuffle阶段分为两部分:Map端和Reduce端。一 map端shuffle过程；1-内存预排序：默认每个map有100M内存进行预排序（为了效率），超过阈值，会把内容写到磁盘； 此过程使用快速排序算法；2-根据key和reducer的数量进行分区和排序；首先根据数据所属的Parti...
大数据时代需要1存储大量数据2快速的处理大量数据3从大量数据中进行分析
hadoop的四种模式。1、本地模式：本地模式就是解压源码包，不需要做任何的配置。通常用于开发调试，或者感受hadoop。2、伪分布模式：在学习当中一般都是使用这种模式，伪分布模式就是在一台机器的多个进程运行多个模块。虽然每一个模块都有相应的进程，但是却...
进入和退出安全模式 [root@localhost bin]# ./hdfs dfsadmin -safemode enter15/08/03 07:26:24 WARN util.NativeCodeLoader: Unable to load native-hadoop library for your platform... using builtin-java classes where ......