数据结构之BloomFilter

标签: 数据结构 bloomfilter | 发表时间:2014-12-04 10:12 | 作者:ljl_xyf
出处:http://www.iteye.com
  • BloomFilter是什么?

       BloomFilter主要提供两种操作: add()和contains(),作用分别是将元素加入其中以及判断一个元素是否在其中,类似于Java中的Set接口,它内部采用的byte数组来节 省空间。其独特之处在于contains()方法,当我们需要查询某个元素是否包含在BloomFilter中时,如果返回true,结果可能是不正确 的,也就是元素也有可能不在其中;但是如果返回的是false,那么元素一定不在其中。这也就是所谓的no false negative和small probability of  false  positive。通俗地来就是,“说了没有就是没有”,“说有但实际上有可能没有”。

 

  • 为什么要使用BloomFilter?

       任何一种数据结构,特别是比较巧妙的,都有它的应用场景,BloomFilter也不例外。许多实际背景和应用这里不再啰嗦,举个简单例子:我们需要存储 大量的URL,并且对于新得到的URL需要知道是否已经存储了。如果将这些URL全扔进Set,那就悲剧了,内存可吃不消。这个时候就要想到用byte来 存储了,可以节省大量的空间。

 

  • BloomFilter实现

        既然涉及到byte存储,那么必然需要一种映射关系了,也就是需要知道一个元素用哪些byte来表示,这也就是hash函数所干的事情。直观地想,一个元 素一个byte基本上不可能,一般情况下这样的hash函数可以说不存在,所以这里假设用k位来表示,一般采用k次hash来确定这些byte。实际 上,BloomFilter中一般包含m(byte数组的大小),k(hash次数)和n(需要存储的数据量)。 在元素加入实现add()操作时,连续k次hash,将得到的对应k位全置为1。当查询元素是否在集合中时,也是连续k次hash,如果这k次得到的位不 是全为1,那么返回false;否则返回 true。传统的算法优化都是以时间换空间或者以空间换时间,BloomFilter则是以正确率换空间。

Java代码   收藏代码
  1. Class BloomFilter<E> {  
  2.     public BloomFilter(int m, int k){……}  
  3.     public void add(E obj){……}  
  4.     public boolean contains(E obj){……}  
  5. }  

 

  • BloomFilter相关结论

      根据上面的标记,可以采用数学方法推导出false positive的概率大约是p = (1-exp(-kn/m))^k,那么由此可得出,最优的k=ln(2)*(m/n)。我们可以计算一下上面提到的例子,假设共有10000000个 URL(n=10000000),如果采用m=80000000,k=8,得出p大约2%;但是所占用的内存只有10M,相同情况下使用Set则需要1G 的内存。

具体的实现如下(来自项目http://code.google.com/p/java-bloomfilter/,代码实现不错,可直接使用):

Java代码   收藏代码
  1. /** 
  2.  * This program is free software: you can redistribute it and/or modify 
  3.  * it under the terms of the GNU Lesser General Public License as published by 
  4.  * the Free Software Foundation, either version 3 of the License, or 
  5.  * (at your option) any later version. 
  6.  * 
  7.  * This program is distributed in the hope that it will be useful, 
  8.  * but WITHOUT ANY WARRANTY; without even the implied warranty of 
  9.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
  10.  * GNU Lesser General Public License for more details. 
  11.  * 
  12.  * You should have received a copy of the GNU Lesser General Public License 
  13.  * along with this program.  If not, see <http://www.gnu.org/licenses/>. 
  14.  */  
  15.   
  16. package com.skjegstad.utils;  
  17.   
  18. import java.io.Serializable;  
  19. import java.nio.charset.Charset;  
  20. import java.security.MessageDigest;  
  21. import java.security.NoSuchAlgorithmException;  
  22. import java.util.BitSet;  
  23. import java.util.Collection;  
  24.   
  25. /** 
  26.  * Implementation of a Bloom-filter, as described here: 
  27.  * http://en.wikipedia.org/wiki/Bloom_filter 
  28.  * 
  29.  * For updates and bugfixes, see http://github.com/magnuss/java-bloomfilter 
  30.  * 
  31.  * Inspired by the SimpleBloomFilter-class written by Ian Clarke. This 
  32.  * implementation provides a more evenly distributed Hash-function by 
  33.  * using a proper digest instead of the Java RNG. Many of the changes 
  34.  * were proposed in comments in his blog: 
  35.  * http://blog.locut.us/2008/01/12/a-decent-stand-alone-java-bloom-filter-implementation/ 
  36.  * 
  37.  * @param <E> Object type that is to be inserted into the Bloom filter, e.g. String or Integer. 
  38.  * @author Magnus Skjegstad <[email protected]
  39.  */  
  40. public class BloomFilter<E> implements Serializable {  
  41.     private BitSet bitset;  
  42.     private int bitSetSize;  
  43.     private double bitsPerElement;  
  44.     private int expectedNumberOfFilterElements;   
  45.     private int numberOfAddedElements;   
  46.     private int k; // number of hash functions  
  47.   
  48.     static final Charset charset = Charset.forName("UTF-8");   
  49.   
  50.     static final String hashName = "MD5";   
  51.     static final MessageDigest digestFunction;  
  52.     static { // The digest method is reused between instances  
  53.         MessageDigest tmp;  
  54.         try {  
  55.             tmp = java.security.MessageDigest.getInstance(hashName);  
  56.         } catch (NoSuchAlgorithmException e) {  
  57.             tmp = null;  
  58.         }  
  59.         digestFunction = tmp;  
  60.     }  
  61.   
  62.     /** 
  63.       * Constructs an empty Bloom filter. The total length of the Bloom filter will be 
  64.       * c*n. 
  65.       * 
  66.       * @param c is the number of bits used per element. 
  67.       * @param n is the expected number of elements the filter will contain. 
  68.       * @param k is the number of hash functions used. 
  69.       */  
  70.     public BloomFilter(double c, int n, int k) {  
  71.       this.expectedNumberOfFilterElements = n;  
  72.       this.k = k;  
  73.       this.bitsPerElement = c;  
  74.       this.bitSetSize = (int)Math.ceil(c * n);  
  75.       numberOfAddedElements = 0;  
  76.       this.bitset = new BitSet(bitSetSize);  
  77.     }  
  78.   
  79.     /** 
  80.      * Constructs an empty Bloom filter. The optimal number of hash functions (k) is estimated from 
  81.      * the total size of the Bloom 
  82.      * and the number of expected elements. 
  83.      * 
  84.      * @param bitSetSize defines how many bits should be used in total for the filter. 
  85.      * @param expectedNumberOElements defines the maximum number of elements the filter is  
  86.      * expected to contain. 
  87.      */  
  88.     public BloomFilter(int bitSetSize, int expectedNumberOElements) {  
  89.         this(bitSetSize / (double)expectedNumberOElements,  
  90.              expectedNumberOElements,  
  91.              (int) Math.round((bitSetSize / (double)expectedNumberOElements) * Math.log(2.0)));  
  92.     }  
  93.   
  94.     /** 
  95.      * Constructs an empty Bloom filter with a given false positive probability. The number of bits per 
  96.      * element and the number of hash functions is estimated 
  97.      * to match the false positive probability. 
  98.      * 
  99.      * @param falsePositiveProbability is the desired false positive probability. 
  100.      * @param expectedNumberOfElements is the expected number of elements in the Bloom filter. 
  101.      */  
  102.     public BloomFilter(double falsePositiveProbability, int expectedNumberOfElements) {  
  103.         this(Math.ceil(-(Math.log(falsePositiveProbability) / Math.log(2))) / Math.log(2),   
  104.              expectedNumberOfElements,  
  105.              (int)Math.ceil(-(Math.log(falsePositiveProbability) / Math.log(2))));   
  106.     }  
  107.   
  108.     /** 
  109.      * Construct a new Bloom filter based on existing Bloom filter data. 
  110.      * 
  111.      * @param bitSetSize defines how many bits should be used for the filter. 
  112.      * @param expectedNumberOfFilterElements defines the maximum number of elements the filter 
  113.      *    is expected to contain. 
  114.      * @param actualNumberOfFilterElements specifies how many elements have been inserted into  
  115.      *    the <code>filterData</code> BitSet. 
  116.      * @param filterData a BitSet representing an existing Bloom filter. 
  117.      */  
  118.     public BloomFilter(int bitSetSize, int expectedNumberOfFilterElements,   
  119.                                                        int actualNumberOfFilterElements, BitSet filterData) {  
  120.         this(bitSetSize, expectedNumberOfFilterElements);  
  121.         this.bitset = filterData;  
  122.         this.numberOfAddedElements = actualNumberOfFilterElements;  
  123.     }  
  124.   
  125.     /** 
  126.      * Generates a digest based on the contents of a String. 
  127.      * 
  128.      * @param val specifies the input data. 
  129.      * @param charset specifies the encoding of the input data. 
  130.      * @return digest as long. 
  131.      */  
  132.     public static int createHash(String val, Charset charset) {  
  133.         return createHash(val.getBytes(charset));  
  134.     }  
  135.   
  136.     /** 
  137.      * Generates a digest based on the contents of a String. 
  138.      * 
  139.      * @param val specifies the input data. The encoding is expected to be UTF-8. 
  140.      * @return digest as long. 
  141.      */  
  142.     public static int createHash(String val) {  
  143.         return createHash(val, charset);  
  144.     }  
  145.   
  146.     /** 
  147.      * Generates a digest based on the contents of an array of bytes. 
  148.      * 
  149.      * @param data specifies input data. 
  150.      * @return digest as long. 
  151.      */  
  152.     public static int createHash(byte[] data) {  
  153.         return createHashes(data, 1)[0];  
  154.     }  
  155.   
  156.     /** 
  157.      * Generates digests based on the contents of an array of bytes and splits the result into  
  158.      * 4-byte int's and store them in an array. The 
  159.      * digest function is called until the required number of int's are produced. For each call to 
  160.      * digest a salt 
  161.      * is prepended to the data. The salt is increased by 1 for each call. 
  162.      * 
  163.      * @param data specifies input data. 
  164.      * @param hashes number of hashes/int's to produce. 
  165.      * @return array of int-sized hashes 
  166.      */  
  167.     public static int[] createHashes(byte[] data, int hashes) {  
  168.         int[] result = new int[hashes];  
  169.   
  170.         int k = 0;  
  171.         byte salt = 0;  
  172.         while (k < hashes) {  
  173.             byte[] digest;  
  174.             synchronized (digestFunction) {  
  175.                 digestFunction.update(salt);  
  176.                 salt++;  
  177.                 digest = digestFunction.digest(data);                  
  178.             }  
  179.           
  180.             for (int i = 0; i < digest.length/4 && k < hashes; i++) {  
  181.                 int h = 0;  
  182.                 for (int j = (i*4); j < (i*4)+4; j++) {  
  183.                     h <<= 8;  
  184.                     h |= ((int) digest[j]) & 0xFF;  
  185.                 }  
  186.                 result[k] = h;  
  187.                 k++;  
  188.             }  
  189.         }  
  190.         return result;  
  191.     }  
  192.   
  193.     /** 
  194.      * Compares the contents of two instances to see if they are equal. 
  195.      * 
  196.      * @param obj is the object to compare to. 
  197.      * @return True if the contents of the objects are equal. 
  198.      */  
  199.     @Override  
  200.     public boolean equals(Object obj) {  
  201.         if (obj == null) {  
  202.             return false;  
  203.         }  
  204.         if (getClass() != obj.getClass()) {  
  205.             return false;  
  206.         }  
  207.         final BloomFilter<E> other = (BloomFilter<E>) obj;          
  208.         if (this.expectedNumberOfFilterElements != other.expectedNumberOfFilterElements) {  
  209.             return false;  
  210.         }  
  211.         if (this.k != other.k) {  
  212.             return false;  
  213.         }  
  214.         if (this.bitSetSize != other.bitSetSize) {  
  215.             return false;  
  216.         }  
  217.         if (this.bitset != other.bitset && (this.bitset == null || !this.bitset.equals(other.bitset))) {  
  218.             return false;  
  219.         }  
  220.         return true;  
  221.     }  
  222.   
  223.     /** 
  224.      * Calculates a hash code for this class. 
  225.      * @return hash code representing the contents of an instance of this class. 
  226.      */  
  227.     @Override  
  228.     public int hashCode() {  
  229.         int hash = 7;  
  230.         hash = 61 * hash + (this.bitset != null ? this.bitset.hashCode() : 0);  
  231.         hash = 61 * hash + this.expectedNumberOfFilterElements;  
  232.         hash = 61 * hash + this.bitSetSize;  
  233.         hash = 61 * hash + this.k;  
  234.         return hash;  
  235.     }  
  236.   
  237.   
  238.     /** 
  239.      * Calculates the expected probability of false positives based on 
  240.      * the number of expected filter elements and the size of the Bloom filter. 
  241.      * <br /><br /> 
  242.      * The value returned by this method is the <i>expected</i> rate of false 
  243.      * positives, assuming the number of inserted elements equals the number of 
  244.      * expected elements. If the number of elements in the Bloom filter is less 
  245.      * than the expected value, the true probability of false positives will be lower. 
  246.      * 
  247.      * @return expected probability of false positives. 
  248.      */  
  249.     public double expectedFalsePositiveProbability() {  
  250.         return getFalsePositiveProbability(expectedNumberOfFilterElements);  
  251.     }  
  252.   
  253.     /** 
  254.      * Calculate the probability of a false positive given the specified 
  255.      * number of inserted elements. 
  256.      * 
  257.      * @param numberOfElements number of inserted elements. 
  258.      * @return probability of a false positive. 
  259.      */  
  260.     public double getFalsePositiveProbability(double numberOfElements) {  
  261.         // (1 - e^(-k * n / m)) ^ k  
  262.         return Math.pow((1 - Math.exp(-k * (double) numberOfElements  
  263.                         / (double) bitSetSize)), k);  
  264.   
  265.     }  
  266.   
  267.     /** 
  268.      * Get the current probability of a false positive. The probability is calculated from 
  269.      * the size of the Bloom filter and the current number of elements added to it. 
  270.      * 
  271.      * @return probability of false positives. 
  272.      */  
  273.     public double getFalsePositiveProbability() {  
  274.         return getFalsePositiveProbability(numberOfAddedElements);  
  275.     }  
  276.   
  277.   
  278.     /** 
  279.      * Returns the value chosen for K.<br /> 
  280.      * <br /> 
  281.      * K is the optimal number of hash functions based on the size 
  282.      * of the Bloom filter and the expected number of inserted elements. 
  283.      * 
  284.      * @return optimal k. 
  285.      */  
  286.     public int getK() {  
  287.         return k;  
  288.     }  
  289.   
  290.     /** 
  291.      * Sets all bits to false in the Bloom filter. 
  292.      */  
  293.     public void clear() {  
  294.         bitset.clear();  
  295.         numberOfAddedElements = 0;  
  296.     }  
  297.   
  298.     /** 
  299.      * Adds an object to the Bloom filter. The output from the object's 
  300.      * toString() method is used as input to the hash functions. 
  301.      * 
  302.      * @param element is an element to register in the Bloom filter. 
  303.      */  
  304.     public void add(E element) {  
  305.        add(element.toString().getBytes(charset));  
  306.     }  
  307.   
  308.     /** 
  309.      * Adds an array of bytes to the Bloom filter. 
  310.      * 
  311.      * @param bytes array of bytes to add to the Bloom filter. 
  312.      */  
  313.     public void add(byte[] bytes) {  
  314.        int[] hashes = createHashes(bytes, k);  
  315.        for (int hash : hashes)  
  316.            bitset.set(Math.abs(hash % bitSetSize), true);  
  317.        numberOfAddedElements ++;  
  318.     }  
  319.   
  320.     /** 
  321.      * Adds all elements from a Collection to the Bloom filter. 
  322.      * @param c Collection of elements. 
  323.      */  
  324.     public void addAll(Collection<? extends E> c) {  
  325.         for (E element : c)  
  326.             add(element);  
  327.     }  
  328.           
  329.     /** 
  330.      * Returns true if the element could have been inserted into the Bloom filter. 
  331.      * Use getFalsePositiveProbability() to calculate the probability of this 
  332.      * being correct. 
  333.      * 
  334.      * @param element element to check. 
  335.      * @return true if the element could have been inserted into the Bloom filter. 
  336.      */  
  337.     public boolean contains(E element) {  
  338.         return contains(element.toString().getBytes(charset));  
  339.     }  
  340.   
  341.     /** 
  342.      * Returns true if the array of bytes could have been inserted into the Bloom filter. 
  343.      * Use getFalsePositiveProbability() to calculate the probability of this 
  344.      * being correct. 
  345.      * 
  346.      * @param bytes array of bytes to check. 
  347.      * @return true if the array could have been inserted into the Bloom filter. 
  348.      */  
  349.     public boolean contains(byte[] bytes) {  
  350.         int[] hashes = createHashes(bytes, k);  
  351.         for (int hash : hashes) {  
  352.             if (!bitset.get(Math.abs(hash % bitSetSize))) {  
  353.                 return false;  
  354.             }  
  355.         }  
  356.         return true;  
  357.     }  
  358.   
  359.     /** 
  360.      * Returns true if all the elements of a Collection could have been inserted 
  361.      * into the Bloom filter. Use getFalsePositiveProbability() to calculate the 
  362.      * probability of this being correct. 
  363.      * @param c elements to check. 
  364.      * @return true if all the elements in c could have been inserted into the Bloom filter. 
  365.      */  
  366.     public boolean containsAll(Collection<? extends E> c) {  
  367.         for (E element : c)  
  368.             if (!contains(element))  
  369.                 return false;  
  370.         return true;  
  371.     }  
  372.   
  373.     /** 
  374.      * Read a single bit from the Bloom filter. 
  375.      * @param bit the bit to read. 
  376.      * @return true if the bit is set, false if it is not. 
  377.      */  
  378.     public boolean getBit(int bit) {  
  379.         return bitset.get(bit);  
  380.     }  
  381.   
  382.     /** 
  383.      * Set a single bit in the Bloom filter. 
  384.      * @param bit is the bit to set. 
  385.      * @param value If true, the bit is set. If false, the bit is cleared. 
  386.      */  
  387.     public void setBit(int bit, boolean value) {  
  388.         bitset.set(bit, value);  
  389.     }  
  390.   
  391.     /** 
  392.      * Return the bit set used to store the Bloom filter. 
  393.      * @return bit set representing the Bloom filter. 
  394.      */  
  395.     public BitSet getBitSet() {  
  396.         return bitset;  
  397.     }  
  398.   
  399.     /** 
  400.      * Returns the number of bits in the Bloom filter. Use count() to retrieve 
  401.      * the number of inserted elements. 
  402.      * 
  403.      * @return the size of the bitset used by the Bloom filter. 
  404.      */  
  405.     public int size() {  
  406.         return this.bitSetSize;  
  407.     }  
  408.   
  409.     /** 
  410.      * Returns the number of elements added to the Bloom filter after it 
  411.      * was constructed or after clear() was called. 
  412.      * 
  413.      * @return number of elements added to the Bloom filter. 
  414.      */  
  415.     public int count() {  
  416.         return this.numberOfAddedElements;  
  417.     }  
  418.   
  419.     /** 
  420.      * Returns the expected number of elements to be inserted into the filter. 
  421.      * This value is the same value as the one passed to the constructor. 
  422.      * 
  423.      * @return expected number of elements. 
  424.      */  
  425.     public int getExpectedNumberOfElements() {  
  426.         return expectedNumberOfFilterElements;  
  427.     }  
  428.   
  429.     /** 
  430.      * Get expected number of bits per element when the Bloom filter is full. This value is set by the constructor 
  431.      * when the Bloom filter is created. See also getBitsPerElement(). 
  432.      * 
  433.      * @return expected number of bits per element. 
  434.      */  
  435.     public double getExpectedBitsPerElement() {  
  436.         return this.bitsPerElement;  
  437.     }  
  438.   
  439.     /** 
  440.      * Get actual number of bits per element based on the number of elements that have currently been inserted and the length 
  441.      * of the Bloom filter. See also getExpectedBitsPerElement(). 
  442.      * 
  443.      * @return number of bits per element. 
  444.      */  
  445.     public double getBitsPerElement() {  
  446.         return this.bitSetSize / (double)numberOfAddedElements;  
  447.     }  
  448. }  

   实际应用中,重要的往往是m,n,k的选择以及hash函数的设定。在Oracle 11g中就采用了BloomFilter来实现分布式数据库中两表的join操作;在网络中应用则更加广泛,例如分布式web代理Squid;此外还有拼 写检查、海量数据处理等领域中都能搞看到它的身影。



已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [数据结构 bloomfilter] 推荐:

数据结构之BloomFilter

- - 编程语言 - ITeye博客
BloomFilter是什么.        BloomFilter主要提供两种操作: add()和contains(),作用分别是将元素加入其中以及判断一个元素是否在其中,类似于Java中的Set接口,它内部采用的byte数组来节 省空间. 其独特之处在于contains()方法,当我们需要查询某个元素是否包含在BloomFilter中时,如果返回true,结果可能是不正确 的,也就是元素也有可能不在其中;但是如果返回的是false,那么元素一定不在其中.

BloomFilter--大规模数据处理利器

- - CSDN博客云计算推荐文章
Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法. 通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求100%正确的场合.   为了说明Bloom Filter存在的重要意义,举一个实例:.   假设要你写一个网络蜘蛛(web crawler).

Hbase 布隆过滤器BloomFilter介绍

- - CSDN博客推荐文章
bloom filter的数据存在StoreFile的meta中,一旦写入无法更新,因为StoreFile是不可变的. Bloomfilter是一个列族(cf)级别的配置属性,如果你在表中设置了Bloomfilter,那么HBase会在生成StoreFile时包含一份bloomfilter结构的数据,称其为MetaBlock;MetaBlock与DataBlock(真实的KeyValue数据)一起由LRUBlockCache维护.

如何使用bloomfilter构建大型Java缓存系统

- - ImportNew
在如今的软件当中,缓存是解决很多问题的一个关键概念. 你的应用可能会进行CPU密集型运算. 你当然不想让这些运算一边又一边的重复执行,相反,你可以只执行一次, 把这个结果放在内存中作为缓存. 有时系统的瓶颈在I/O操作上,比如你不想重复的查询数据库,你想把结果缓存起来,只在数据发生变化时才去数据查询来更新缓存.

使用graphviz画数据结构

- 王者自由 - Emacs中文网
今天下午用了些时间写了个小的函数,该函数配合 autoinsert + graphviz-dot-mode ,可以很方便的将 C 语言中指定的 struct 结构画出来. 这样,画了多个数据结构之后,再手动添加几条线, 数据结构之间的关系就一目了然了. 1.2 Graphviz 的安装. 1.3 Graphviz 的使用.

数据结构之红黑树

- Shengbin - 董的博客
红黑树是一种自平衡二叉查找树. 它的统计性能要好于平衡二叉树(AVL树),因此,红黑树在很多地方都有应用. 在C++ STL中,很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化,这些修改提供了更好的性能,以及对set操作的支持).

数据结构-二分法查找

- - 操作系统 - ITeye博客
1、二分查找(Binary Search).      二分查找又称折半查找,它是一种效率较高的查找方法.      二分查找要求:线性表是有序表,即表中结点按关键字有序,并且要用向量作为表的存储结构. 2、二分查找的基本思想.      二分查找的基本思想是:(设R[low..high]是当前的查找区间).

redis数据结构缓存运用

- - 企业架构 - ITeye博客
之前redis已经描述了redis 的基本作用与用处, 这一篇主要讲述redis运用场景以及分片,和spring整合. redis 存储数据结构大致5种,String 普通键值对,用的比较多. HASH针对 key 唯一标识 hashmap 键值对运用也比较多 list set 当然是集合运用 sortedSet 排序集合使用.

可视化的数据结构和算法

- greenar - 酷壳 - CoolShell.cn
还记得之前发布过的那个关于可视化排序的文章吗. 在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页,网址在这里,大家可以看看. 我把这个页面的目录列在下面并翻译了一下,大家可以直接点击了. 不知道国内的教育有没有相关的教学课件,至少在我大学的时候是没有的. Queues队列: 数组实现.