BloomFilter.java
上传用户:quxuerui
上传日期:2018-01-08
资源大小:41811k
文件大小:7k
源码类别:

网格计算

开发平台:

Java

  1. /**
  2.  *
  3.  * Copyright (c) 2005, European Commission project OneLab under contract 034819 (http://www.one-lab.org)
  4.  * All rights reserved.
  5.  * Redistribution and use in source and binary forms, with or 
  6.  * without modification, are permitted provided that the following 
  7.  * conditions are met:
  8.  *  - Redistributions of source code must retain the above copyright 
  9.  *    notice, this list of conditions and the following disclaimer.
  10.  *  - Redistributions in binary form must reproduce the above copyright 
  11.  *    notice, this list of conditions and the following disclaimer in 
  12.  *    the documentation and/or other materials provided with the distribution.
  13.  *  - Neither the name of the University Catholique de Louvain - UCL
  14.  *    nor the names of its contributors may be used to endorse or 
  15.  *    promote products derived from this software without specific prior 
  16.  *    written permission.
  17.  *    
  18.  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
  19.  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
  20.  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 
  21.  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 
  22.  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 
  23.  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 
  24.  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
  25.  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
  26.  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
  27.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 
  28.  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
  29.  * POSSIBILITY OF SUCH DAMAGE.
  30.  */
  31. /**
  32.  * Licensed to the Apache Software Foundation (ASF) under one
  33.  * or more contributor license agreements.  See the NOTICE file
  34.  * distributed with this work for additional information
  35.  * regarding copyright ownership.  The ASF licenses this file
  36.  * to you under the Apache License, Version 2.0 (the
  37.  * "License"); you may not use this file except in compliance
  38.  * with the License.  You may obtain a copy of the License at
  39.  *
  40.  *     http://www.apache.org/licenses/LICENSE-2.0
  41.  *
  42.  * Unless required by applicable law or agreed to in writing, software
  43.  * distributed under the License is distributed on an "AS IS" BASIS,
  44.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  45.  * See the License for the specific language governing permissions and
  46.  * limitations under the License.
  47.  */
  48. package org.apache.hadoop.util.bloom;
  49. import java.io.DataInput;
  50. import java.io.DataOutput;
  51. import java.io.IOException;
  52. import java.util.BitSet;
  53. /**
  54.  * Implements a <i>Bloom filter</i>, as defined by Bloom in 1970.
  55.  * <p>
  56.  * The Bloom filter is a data structure that was introduced in 1970 and that has been adopted by 
  57.  * the networking research community in the past decade thanks to the bandwidth efficiencies that it
  58.  * offers for the transmission of set membership information between networked hosts.  A sender encodes 
  59.  * the information into a bit vector, the Bloom filter, that is more compact than a conventional 
  60.  * representation. Computation and space costs for construction are linear in the number of elements.  
  61.  * The receiver uses the filter to test whether various elements are members of the set. Though the 
  62.  * filter will occasionally return a false positive, it will never return a false negative. When creating 
  63.  * the filter, the sender can choose its desired point in a trade-off between the false positive rate and the size. 
  64.  * 
  65.  * <p>
  66.  * Originally created by
  67.  * <a href="http://www.one-lab.org">European Commission One-Lab Project 034819</a>.
  68.  * 
  69.  * @see Filter The general behavior of a filter
  70.  * 
  71.  * @see <a href="http://portal.acm.org/citation.cfm?id=362692&dl=ACM&coll=portal">Space/Time Trade-Offs in Hash Coding with Allowable Errors</a>
  72.  */
  73. public class BloomFilter extends Filter {
  74.   private static final byte[] bitvalues = new byte[] {
  75.     (byte)0x01,
  76.     (byte)0x02,
  77.     (byte)0x04,
  78.     (byte)0x08,
  79.     (byte)0x10,
  80.     (byte)0x20,
  81.     (byte)0x40,
  82.     (byte)0x80
  83.   };
  84.   
  85.   /** The bit vector. */
  86.   BitSet bits;
  87.   /** Default constructor - use with readFields */
  88.   public BloomFilter() {
  89.     super();
  90.   }
  91.   
  92.   /**
  93.    * Constructor
  94.    * @param vectorSize The vector size of <i>this</i> filter.
  95.    * @param nbHash The number of hash function to consider.
  96.    * @param hashType type of the hashing function (see
  97.    * {@link org.apache.hadoop.util.hash.Hash}).
  98.    */
  99.   public BloomFilter(int vectorSize, int nbHash, int hashType) {
  100.     super(vectorSize, nbHash, hashType);
  101.     bits = new BitSet(this.vectorSize);
  102.   }
  103.   @Override
  104.   public void add(Key key) {
  105.     if(key == null) {
  106.       throw new NullPointerException("key cannot be null");
  107.     }
  108.     int[] h = hash.hash(key);
  109.     hash.clear();
  110.     for(int i = 0; i < nbHash; i++) {
  111.       bits.set(h[i]);
  112.     }
  113.   }
  114.   @Override
  115.   public void and(Filter filter) {
  116.     if(filter == null
  117.         || !(filter instanceof BloomFilter)
  118.         || filter.vectorSize != this.vectorSize
  119.         || filter.nbHash != this.nbHash) {
  120.       throw new IllegalArgumentException("filters cannot be and-ed");
  121.     }
  122.     this.bits.and(((BloomFilter) filter).bits);
  123.   }
  124.   @Override
  125.   public boolean membershipTest(Key key) {
  126.     if(key == null) {
  127.       throw new NullPointerException("key cannot be null");
  128.     }
  129.     int[] h = hash.hash(key);
  130.     hash.clear();
  131.     for(int i = 0; i < nbHash; i++) {
  132.       if(!bits.get(h[i])) {
  133.         return false;
  134.       }
  135.     }
  136.     return true;
  137.   }
  138.   @Override
  139.   public void not() {
  140.     bits.flip(0, vectorSize - 1);
  141.   }
  142.   @Override
  143.   public void or(Filter filter) {
  144.     if(filter == null
  145.         || !(filter instanceof BloomFilter)
  146.         || filter.vectorSize != this.vectorSize
  147.         || filter.nbHash != this.nbHash) {
  148.       throw new IllegalArgumentException("filters cannot be or-ed");
  149.     }
  150.     bits.or(((BloomFilter) filter).bits);
  151.   }
  152.   @Override
  153.   public void xor(Filter filter) {
  154.     if(filter == null
  155.         || !(filter instanceof BloomFilter)
  156.         || filter.vectorSize != this.vectorSize
  157.         || filter.nbHash != this.nbHash) {
  158.       throw new IllegalArgumentException("filters cannot be xor-ed");
  159.     }
  160.     bits.xor(((BloomFilter) filter).bits);
  161.   }
  162.   @Override
  163.   public String toString() {
  164.     return bits.toString();
  165.   }
  166.   /**
  167.    * @return size of the the bloomfilter
  168.    */
  169.   public int getVectorSize() {
  170.     return this.vectorSize;
  171.   }
  172.   // Writable
  173.   @Override
  174.   public void write(DataOutput out) throws IOException {
  175.     super.write(out);
  176.     byte[] bytes = new byte[getNBytes()];
  177.     for(int i = 0, byteIndex = 0, bitIndex = 0; i < vectorSize; i++, bitIndex++) {
  178.       if (bitIndex == 8) {
  179.         bitIndex = 0;
  180.         byteIndex++;
  181.       }
  182.       if (bitIndex == 0) {
  183.         bytes[byteIndex] = 0;
  184.       }
  185.       if (bits.get(i)) {
  186.         bytes[byteIndex] |= bitvalues[bitIndex];
  187.       }
  188.     }
  189.     out.write(bytes);
  190.   }
  191.   @Override
  192.   public void readFields(DataInput in) throws IOException {
  193.     super.readFields(in);
  194.     bits = new BitSet(this.vectorSize);
  195.     byte[] bytes = new byte[getNBytes()];
  196.     in.readFully(bytes);
  197.     for(int i = 0, byteIndex = 0, bitIndex = 0; i < vectorSize; i++, bitIndex++) {
  198.       if (bitIndex == 8) {
  199.         bitIndex = 0;
  200.         byteIndex++;
  201.       }
  202.       if ((bytes[byteIndex] & bitvalues[bitIndex]) != 0) {
  203.         bits.set(i);
  204.       }
  205.     }
  206.   }
  207.   
  208.   /* @return number of bytes needed to hold bit vector */
  209.   private int getNBytes() {
  210.     return (vectorSize + 7) / 8;
  211.   }
  212. }//end class