hbase bloomfilter filter 为什么3个hash 函数

来源：蜘蛛抓取(WebSpider) 时间：2016-08-23 10:16 标签： bloom filter java
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
您的访问请求被拒绝 403 Forbidden - ITeye技术社区
您的访问请求被拒绝
亲爱的会员，您的IP地址所在网段被ITeye拒绝服务，这可能是以下两种情况导致：
一、您所在的网段内有网络爬虫大量抓取ITeye网页，为保证其他人流畅的访问ITeye，该网段被ITeye拒绝
二、您通过某个代理服务器访问ITeye网站，该代理服务器被网络爬虫利用，大量抓取ITeye网页
请您点击按钮解除封锁&Bloom filter（布隆过滤器）和普通hash表对于碰撞和存储空间的不同？
我的理解1.普通hash表可以生成一个类似快照的数字记录在一个大表中，可以利用数组下标的方式，方便匹配；2.布隆过滤也是利用多张hash表，形成一个类似网的多张hash表形成的组来匹配；请问这与用一张普通hash表（我的理解是一维的），与使用多张hash表的布隆算法对比，可以从存储空间和碰撞率分析一下吗？最好加上通俗易懂的推导公式哈~谢谢。由也可以看出布隆中hash表的个数k由表长m与总元素个数n决定。难道说布隆过滤相对hash表其实也只是“将一个大hash表拆成多个小hahs表，方便计算机运算”这样的优点。不好意思，之前想表达的是如普通hash，也可以用一个md5表达一个点。应该想了解的是：普通hash表，和布隆过滤的不同--3.3更新--我觉得是不是可以这么来计算：【以下来自】假设 Hash 函数以等概率条件选择并设置 Bit Array 中的某一位，m 是该位数组的大小，k 是 Hash 函数的个数，那么位数组中某一特定的位在进行元素插入时的 Hash 操作中没有被置位的概率是：如果我们插入了 n 个元素，那么某一位仍然为 "0" 的概率是：&1&那么同理，如果仅仅用一个Hash表，假定我们使用与上面同样大小的空间，即为一个k*m大小的hash，对应的概率应该是：没有被置位的概率：重复了n个元素后为：&2&如上，比较&1&和&2&两个值的大小即可。但是高数还给大学语文老师的我不知道怎么算了，求教~
原理是：把哈希值 n 映射到 2**n, 那么做逻辑或就很少会碰撞了。不过一般 bloom filter 里说的哈希函数值域为 0和1，那么你算个 SHA256 就可以得到 256 个哈希函数啦
你说的不是“hash表”而是hash摘要算法，像crc，md5这种，相当于将较长内容转换为一个数字，用来做这个内容的标识，可能有碰撞但是概率能控制在可接受的范围bloom filter是用来判断一个元素是否属于一个集合，但不要求100%准确，比如用一个长度为N的bitmap，然后所有元素都会被转换成0~N-1的值，若值在集合，则对应bit位为1，于是若一个元素落在bit中为0的位置，则“必定不在”集合中，否则“可能存在于”集合中，这时候可以去集合中具体确认一把，换句话说就是先快速把不在的过滤掉，对于剩下的用较慢的查询确认到底在不在，如果bit为1的占比较少且空查询很多，就有很好的过滤效果了
已有帐号？
无法登录？
社交帐号登录<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
您的访问请求被拒绝 403 Forbidden - ITeye技术社区
您的访问请求被拒绝
亲爱的会员，您的IP地址所在网段被ITeye拒绝服务，这可能是以下两种情况导致：
一、您所在的网段内有网络爬虫大量抓取ITeye网页，为保证其他人流畅的访问ITeye，该网段被ITeye拒绝
二、您通过某个代理服务器访问ITeye网站，该代理服务器被网络爬虫利用，大量抓取ITeye网页
请您点击按钮解除封锁&我的理解1.普通hash表可以生成一个类似快照的数字记录在一个大表中，可以利用数组下标的方式，方便匹配；2.布隆过滤也是利用多张hash表，形成一个类似网的多张hash表形成的组来匹配；请问这与用一张普通hash表（我的理解是一维的），与使用多张hash表的布隆算法对比，可以从存储空间和碰撞率分析一下吗？最好加上通俗易懂的推导公式哈~谢谢。由也可以看出布隆中hash表的个数k由表长m与总元素个数n决定。难道说布隆过滤相对hash表其实也只是“将一个大hash表拆成多个小hahs表，方便计算机运算”这样的优点。不好意思，之前想表达的是如普通hash，也可以用一个md5表达一个点。应该想了解的是：普通hash表，和布隆过滤的不同--3.3更新--我觉得是不是可以这么来计算：【以下来自】假设 Hash 函数以等概率条件选择并设置 Bit Array 中的某一位，m 是该位数组的大小，k 是 Hash 函数的个数，那么位数组中某一特定的位在进行元素插入时的 Hash 操作中没有被置位的概率是：如果我们插入了 n 个元素，那么某一位仍然为 "0" 的概率是：&1&那么同理，如果仅仅用一个Hash表，假定我们使用与上面同样大小的空间，即为一个k*m大小的hash，对应的概率应该是：没有被置位的概率：重复了n个元素后为：&2&如上，比较&1&和&2&两个值的大小即可。但是高数还给大学语文老师的我不知道怎么算了，求教~
原理是：把哈希值 n 映射到 2**n, 那么做逻辑或就很少会碰撞了。不过一般 bloom filter 里说的哈希函数值域为 0和1，那么你算个 SHA256 就可以得到 256 个哈希函数啦
你说的不是“hash表”而是hash摘要算法，像crc，md5这种，相当于将较长内容转换为一个数字，用来做这个内容的标识，可能有碰撞但是概率能控制在可接受的范围&br&bloom filter是用来判断一个元素是否属于一个集合，但不要求100%准确，比如用一个长度为N的bitmap，然后所有元素都会被转换成0~N-1的值，若值在集合，则对应bit位为1，于是若一个元素落在bit中为0的位置，则“必定不在”集合中，否则“可能存在于”集合中，这时候可以去集合中具体确认一把，换句话说就是先快速把不在的过滤掉，对于剩下的用较慢的查询确认到底在不在，如果bit为1的占比较少且空查询很多，就有很好的过滤效果了
你说的不是“hash表”而是hash摘要算法，像crc，md5这种，相当于将较长内容转换为一个数字，用来做这个内容的标识，可能有碰撞但是概率能控制在可接受的范围bloom filter是用来判断一个元素是否属于一个集合，但不要求100%准确，比如用一个长度为N的bitmap…
已有帐号？
无法登录？
社交帐号登录
Helloworld 达人转自：http://blog.csdn.net/liuben/article/details/6602683
部分内容还译自：http://en.wikipedia.org/wiki/Bloom_filter
原文有C实现代码，这里略去了。
Bloom Filter是1970年由Bloom提出的，最初广泛用于拼写检查和数据库系统中。近年来，随着计算机和互联网技术的发展，数据集的不断扩张使得 Bloom filter获得了新生，各种新的应用和变种不断涌现。Bloom filter是一个空间效率很高的数据结构，它由一个位数组和一组hash映射函数组成。Bloom filter可以用于检索一个元素是否在一个集合中，它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
查找或判断一个元素是否存在于一个指定集合中，这是计算机科学中一个基本常见问题。通常，我们会采用线性表（数组或链表）、树（二叉树、堆、红黑树、 B&#43;/B-/B*树）等数据结构对所有元素进行存储，并在其上进行排序和查找。这里的查找时间复杂性通常都是O(n)或O(logn)的，如果集合元素非常庞大，不仅查找速度非常慢，对内存空间的需求也非常大。假设有10亿个元素，每个元素节点占用N个字节，则存储这个集合大致需求N
GB内存。大家可能很快会想到hashtable，它的查找时间复杂性是O(1)的，可以对元素进行映射索引并定位，但它并没有减少内存需求量。hash 函数的一个问题是可能会发生碰撞，即两个不同的元素产生相同的hash&#20540;，在某些场合下需要通过精确比较来解决这个问题。
实际上，判断一个元素是否存在于一个指定集合中，可能并不需要把所有集合元素的原始信息都保存下来，我们只需要记住“存在状态”即可，这往往仅仅需要几个bit就可表示。Hash函数可将一个元素映射成一个位数组中一个点，为了降低碰撞率可采用多个hash函数将元素映射成多个点。这样一来，只要看看几个位点是0或1 就可以判断某个元素是否存在于集合当中。这就是Bloom
filter的基本思想，不仅可大大缩减内存空间，查找速度非常快。
Bloom filter使用一个位数组来记录元素存在状态，并使用一组hash函数(h1, h2, hk...)来对元素进行位映射。插入元素时，对该元素分别进行K次hash计算，并将映射到位数组的相应bit置1。查找元素时，任何其中一个映射位为 0则表示该元素不存在于集合当中，只要当所有映射位均为1时才表示该元素有可能存在于集合当中。换句话说，如果Bloom filter判断一个元素不在集合中，那肯定就不存在；而如果判断存在，则不一定存在，虽然这个概率很低。这个问题是由hash函数会发生碰撞的特性所决定的，它造成了Bloom
filter的错误率产生。这个错误率可通过改变Bloom filter数组大小，或改变hash函数个数进行调节控制。由此可见，Bloom filter也不是完美的，它的高效也是有一定代价的，它通过容忍一定的错误率发生换取了存储空间的极大节省。另外，Bloom filter不能支持元素的删除操作，如果删除会影响其他元素的存在性正确判断。因此，Bloom Filter不适合那些“零错误”的应用场合，但是这个错误是正向的（false positive），不会发生反向的错误（false negative），判断元素不存在集合中是绝对正确的。Bloom
filter使用可控的错误率获得了空间的极大节省和极快的查找性能，得到广泛应用也是理所当然的。
一点数学基础
(1)错误率估计
设k为hash函数个数，且hash是完全随机的，n为项目数，m为位数组位数。
则一个特定位未被置为1的概率= 1-1/m
所有hash函数均未将该位置为1的概率 = (1-1/m)^k
若已经插入n个元素，则某一位为0的概率 = (1-1/m)^(kn)
于是该位为1的概率 = 1 - (1-1/m)^(kn)
hash函数出现冲突的条件是，某一位本该置为0，却被错误地置为1，即所有k个hash函数在该位上的&#20540;均为1，它的概率为：
((1 - (1-1/m)^(kn))^k
即错误率f = (1 - (1-1/m)^(kn))^k = (1 - e^(-kn/m))^k
令　p = e^(-kn/m)，给定m, n，则
f = (1 - p)^k = e^(kln(1-p))
(2)最优hash函数个数
令 g = kln(1-p)，当g极小时，f取极小&#20540;，因为 ln(e^(-kn/m)) = -kn/m，
&& g = -m/n * ln(p) * ln(1-p)
&根据对称性原理有，当 p =1/2时，g取极小&#20540;，因此，
&p = e^(-kn/m) = 1/2，得到，
&k = ln2 * (m/n)，此时错误率最小，即f = (1/2)^k = (0.618)^(m/n)
(3)位数组大小
给定错误率E，参考文献4中推算出当 m &= n * log2(1/E)时，f不超过E。上面我们已经推算出 k = ln2 * (m/n)时f最小，因此当hash函数个数最优时，为了让错误率不超过E，则有
m &= log2(e) * (n * log2(1/E))，这个&#20540;是正常情况下m最小&#20540;的1.44倍。
根据上面推导所得到的数学公式，假设错误率我们取0.01，则可以确定最优化情况下，m &= 9.567n，k = 7。
从以上对基本原理和数学基础的分析，我们可以得到Bloom filter的如下基本特征，用于指导实际应用。
(1)存在一定错误率，发生在正向判断上（存在性），反向判断不会发生错误（不存在性）；
(2)错误率是可控制的，通过改变位数组大小、hash函数个数或更低碰撞率的hash函数来调节；
(3)保持较低的错误率，位数组空位至少保持在一半以上;
(4)给定m和n，可以确定最优hash个数，即k = ln2 * (m/n)，此时错误率最小；
(5)给定允许的错误率E，可以确定合适的位数组大小，即m &= log2(e) * (n * log2(1/E))，继而确定hash函数个数k；
(6)正向错误率无法完全消除，即使不对位数组大小和hash函数个数进行限制，即无法实现零错误率；
(7)空间效率高，仅保存“存在状态”，但无法存储完整信息，需要其他数据结构辅助存储；
(8)不支持元素删除操作，因为不能保证删除的安全性。
与其它数据结构相比较，Bloom filter的最大优点是空间效率和查找时间复杂性，它的存储空间和插入/查询时间都是常数。Hash函数之间没有相关性，可以方便地由硬件并行实现。Bloom filter不需要存储元素本身，在某些对保密要求非常严&#26684;的场合有优势。另外，Bloom filter一般都可以表示大数据集的全集，而其它任何数据结构都难以做到。
Bloom filter的缺点和优点一样显著，首先就是错误率。随着插入的元素数量增加，错误率也随之增加。虽然可以通过增加位数组大小或hash函数个数来降低错误率，但同时也时影响空间效率和查找性能，而且这个错误率是无法从根本上消除的。这使得要求“零错误”的场合无法应用Bloom filter。其次，一般情况下不能从Bloom filter中删除元素。一方面是我们不能保证删除的元素一定存在Bloom filter中，另一方面是不能保证安全地删除元素，可能会对其他元素产生影响，究其原因还是hash函数可能产生的碰撞造成的。计数Bloom
filter可以在一定程度上支持元素删除，但保证安全地删除元素并非如此简单，它也不能从根本上解决这个问题，而且计数器回绕也会有问题。这两方面也是目前Bloom filter的重点研究方向，有不少工作，使得出现了很多Bloom filter的变种。
应用原则和案例
只要使用列表或集合，如果考虑空间效率，就可以考虑使用Bloom filter。应用时，要特别考虑bloom filter的正向错误率影响，对于“零错误”的应用需要相应的辅助机制来消除错误率，否则关键业务不可应用。
Bloom filter被广泛应用于各种领域，比如拼写检查、字符串匹配算法、网络包分析工具、Web Cache、文件系统、存储系统等，包括：
1. Google BigTable用它来查询有磁盘上的行或列是否存在
2. Squid用它缓存摘要数据
3. Venti存储系统用它检测已经存在的数据
4. Google Chrome用它来加速安全浏览（不知道具体用在哪里...）
这里着重介绍一下Bloom filter在重复数据删除中的应用。主流的重复数据删除技术的基本原理是对文件进行定长或变长分块，然后利用hash函数计算数据块指纹，如果两个数据块指纹相同则认为是重复数据块（同样这里存在数据碰撞问题），只保存一个数据块副本即可，其他相同数据块使用该副本索引号表示，从而实现数据缩减存储空间并提高存储效率。为了查询一个数据块是否重复或者已经存在，需要计算数据块指纹并进行查找，并记录所有唯一数据块的指纹。举一个例子：32TB的数据，平均数据块大小为8KB，每个数据块使用MD5和SHA1计算两个指纹并用64位整数表示唯一块号则共占用44字节((128&#43;160&#43;64)/8），则总共最多需要176GB（32TB/8KB
* 44 Byte）的存储空间来保存数据块信息。现在的去重系统数据容量通常多达数十到数百TB，如果把数据块信息全部保存在内存中，显然对内存的需求量非常巨大，出于成本考虑这对商业产品是不现实的。因此，为了在成本和性能两方面作折中，通常的做法是把数据块信息保存在磁盘或SSD上，使用一定内存量作 Cache缓存数据块指纹，利用时间局部性和空间局部性来提高查找性能。这种方法的一个关键问题是，如果新的数据块是不重复的，查找时会出现Cache不命中，从而引起大量的磁盘读写操作。由于磁盘或SSD性能要远远小于内存的，对查找性能影响非常大。Bloom
filter可以有效解决这个问题，DataDomain中的Summary Vector就是采用Bloom filter来实现的。对于前面的例子，一个数据块用3个hash函数计算指纹最多占用3个位，则Bloom filter仅需要1.5GB = 32TB/8KB * 3 /8 bytes的内存空间，这即使对于普通的PC机都不是问题。引入Bloom filter机制后，对于一个新数据块，首先查找Bloom filter，如果未命中则说明这是一个新的唯一数据块，直接保存数据块和并Cachr数据块信息即可；如果命中，则说明这有可能是一个重复数据块，需要通过进一步的hash或tree查找进行确认，此时需要Cache与Disk进行交互。受益于Bloom
filter以及Cache，DataDomain系统可以减少99%的磁盘访问，从而利用少量的内存空间大幅提高了数据块查重性能。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：232798次
积分：3172
积分：3172
排名：第7574名
原创：72篇
转载：29篇
评论：23条
(1)(2)(1)(1)(3)(1)(2)(6)(4)(7)(2)(1)(5)(1)(1)(2)(3)(5)(3)(6)(8)(5)(2)(5)(4)(6)(1)(1)(3)(3)(1)(4)(1)(1)(5)(2)

我要回帖

更多关于 bloom filter java 的文章

 

随机推荐