bloomfilter.java

pastry的java实现的2.0b版

/*************************************************************************

"FreePastry" Peer-to-Peer Application Development Substrate 

Copyright 2002, Rice University. All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

- Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.

- Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in the
documentation and/or other materials provided with the distribution.

- Neither  the name  of Rice  University (RICE) nor  the names  of its
contributors may be  used to endorse or promote  products derived from
this software without specific prior written permission.

This software is provided by RICE and the contributors on an "as is"
basis, without any representations or warranties of any kind, express
or implied including, but not limited to, representations or
warranties of non-infringement, merchantability or fitness for a
particular purpose. In no event shall RICE or contributors be liable
for any direct, indirect, incidental, special, exemplary, or
consequential damages (including, but not limited to, procurement of
substitute goods or services; loss of use, data, or profits; or
business interruption) however caused and on any theory of liability,
whether in contract, strict liability, or tort (including negligence
or otherwise) arising in any way out of the use of this software, even
if advised of the possibility of such damage.

********************************************************************************/

package rice.p2p.util;

import java.io.*;
import java.math.*;
import java.util.*;

import rice.environment.random.RandomSource;
import rice.environment.random.simple.SimpleRandomSource;
import rice.p2p.commonapi.Endpoint;
import rice.p2p.commonapi.rawserialization.*;

/**
 * @(#) BloomFilter.java Class which is an implementation of a bloom filter.
 * This class takes in the size which the underlying bit set should be, as well
 * as the number of hash functions which should be used. The hash functions are
 * parametrized by pre-pending and post-pending input elements with randomly
 * generates byte arrays. Thus, if the user requests two hash functions be used,
 * two random byte arrays will be generated (B_1 and B_2) and the hash functions
 * will be h_1(x) = h(B_1 || x || B_1) h_2(x) = h(B_2 || x || B_2) where h(y) is
 * the real hash function (say SHA-1). Note that the randomly generated byte
 * arrays must also be sent across the wire.
 *
 * @version $Id: BloomFilter.java 3274 2006-05-15 16:17:47Z jeffh $
 * @author Alan Mislove
 */
public class BloomFilter implements Serializable {

  /**
   * The parameters to the hash functions for this bloom filter
   */
  protected int[] parameters;

  /**
   * The length of the set to use
   */
  protected int length;

  /**
   * The underlying bitset representation for this bloom filter
   */
  protected BitSet set;

  // cant parameterize, because object is serializable
  /**
   * The length of the random byte arrays which are generated
   */
  public static int PARAMETER_LENGTH = 4;

  /**
   * Constructor which takes the number of hash functions to use and the length
   * of the set to use.
   *
   * @param num The number of hash functions to use
   * @param length The length of the underlying bit set
   */
  public BloomFilter(int num, int length) {
    RandomSource rand = new SimpleRandomSource(null);
    this.length = length;
    this.set = new BitSet(length);
    this.parameters = new int[num];

    for (int i = 0; i < parameters.length; i++) {
      this.parameters[i] = MathUtils.randomInt(rand);
    }
  }

  /**
   * Constructor for BloomFilter.
   *
   * @param buf DESCRIBE THE PARAMETER
   * @exception IOException DESCRIBE THE EXCEPTION
   */
  public BloomFilter(InputBuffer buf) throws IOException {
    length = buf.readInt();

    parameters = new int[buf.readInt()];
    for (int i = 0; i < parameters.length; i++) {
      parameters[i] = buf.readInt();
    }

    int numBits = buf.readInt();
    set = new BitSet(numBits);

    byte curByte = buf.readByte();
    for (int i = 0; i < numBits; i++) {
      if (((curByte >>> i % 8) & 0x1) == 0x1) {
        set.set(i);
      }
      if (i < numBits - 1 && i % 8 == 7) {
        curByte = buf.readByte();
      }
    }
  }

  /**
   * Method which returns what the internal bit set looks like as a string
   *
   * @return The internal bit set as a string
   */
  public String getBitSet() {
    StringBuffer buffer = new StringBuffer();
    buffer.append("[BloomFilter ");
    for (int i = 0; i < length; i++) {
      if (set.get(i)) {
        buffer.append("1");
      } else {
        buffer.append("0");
      }
    }

    buffer.append("]");

    return buffer.toString();
  }

  /**
   * Method which adds an element to this bloom filter. This is done by
   * computing h_1(x), h_2(x), ... and then setting bits (h_1(x) % length),
   * (h_2(x) % length) and so forth.
   *
   * @param array The element to add
   */
  public void add(byte[] array) {
    for (int i = 0; i < parameters.length; i++) {
      set.set(hash(array, i));
    }
  }

  /**
   * Method which returns whether or not an element *may* be in the set.
   * Specifically, if this method returns false, the element is definately not
   * in the set. Otherwise, if true is returned, the element may be in the set,
   * but it is not guaranteed.
   *
   * @param array The element to check for
   * @return DESCRIBE THE RETURN VALUE
   */
  public boolean check(byte[] array) {
    for (int i = 0; i < parameters.length; i++) {
      if (!set.get(hash(array, i))) {
        return false;
      }
    }

    return true;
  }

  /**
   * Internal method which hashes the input argument using the ith hash
   * function, and then mods the result by length.
   *
   * @param array The element to hash
   * @param i The hash function to use
   * @return DESCRIBE THE RETURN VALUE
   */
  protected int hash(byte[] array, int i) {
    if (length <= 0) {
      return 0;
    } else {
      return MathUtils.mod(doHash(array, parameters[i]), length);
    }
  }

  /**
   * Method which performs a dumb hash of the provided array and the seed value.
   *
   * @param array The input array
   * @param seed DESCRIBE THE PARAMETER
   * @return The result, which is guaranteed to be 0..length
   */
  protected int doHash(byte[] array, int seed) {
    int result = 0;
    byte[] tmp = new byte[4];

    for (int i = 0; i < array.length; i += 4) {
      System.arraycopy(array, i, tmp, 0, ((array.length - i < 4) ? (array.length - i) : 4));
      result += (result * seed) + MathUtils.byteArrayToInt(tmp);
    }

    return result;
  }

  /**
   * DESCRIBE THE METHOD
   *
   * @param buf DESCRIBE THE PARAMETER
   * @exception IOException DESCRIBE THE EXCEPTION
   */
  public void serialize(OutputBuffer buf) throws IOException {
    buf.writeInt(length);

    buf.writeInt(parameters.length);
    for (int i = 0; i < parameters.length; i++) {
      buf.writeInt(parameters[i]);
    }

    int numBits = set.length();
    buf.writeInt(numBits);
    byte curByte = 0x0;
    for (int i = 0; i < numBits; i++) {
      if (i > 0 && i % 8 == 0) {
        buf.writeByte(curByte);
        curByte = 0x0;
      }
      if (set.get(i)) {
        curByte |= (0x1 << i % 8);
      }
    }
    buf.writeByte(curByte);
  }

  /**
   * Test serialize/deserialize
   *
   * @param args
   * @exception IOException DESCRIBE THE EXCEPTION
   */
  public static void main(String[] args) throws IOException {
    Random rng = new Random();
    for (int i = 0; i < 135; i++) {
      BloomFilter a = new BloomFilter(1, i);

      for (int j = 0; j < i / 2; j++) {
        int flip = rng.nextInt(i);
        a.set.flip(flip);
      }
      System.out.println("a:" + a.set);
      final ByteArrayOutputStream baos = new ByteArrayOutputStream();
      OutputBuffer obuf =
        new OutputBuffer() {
          DataOutputStream dos = new DataOutputStream(baos);

          public ByteArrayOutputStream getBaos() {
            return baos;
          }

          public void writeInt(int v) throws IOException {
            dos.writeInt(v);
          }

          public void writeByte(byte v) throws IOException {
            dos.writeByte(v);
          }

          public int bytesRemaining() {
            throw new RuntimeException("Not Implemented.");
          }

          public void writeUTF(String str) throws IOException {
            throw new RuntimeException("Not Implemented.");
          }

          public void writeShort(short v) throws IOException {
            throw new RuntimeException("Not Implemented.");
          }

          public void writeLong(long v) throws IOException {
            throw new RuntimeException("Not Implemented.");
          }

          public void writeFloat(float v) throws IOException {
            throw new RuntimeException("Not Implemented.");
          }

          public void writeDouble(double v) throws IOException {
            throw new RuntimeException("Not Implemented.");
          }

          public void writeChar(char v) throws IOException {
            throw new RuntimeException("Not Implemented.");
          }

          public void writeBoolean(boolean v) throws IOException {
            throw new RuntimeException("Not Implemented.");
          }

          public void write(byte[] b, int off, int len) throws IOException {
            throw new RuntimeException("Not Implemented.");
          }
        };

      a.serialize(obuf);

      final ByteArrayInputStream bais = new ByteArrayInputStream(baos.toByteArray());
      InputBuffer buf =
        new InputBuffer() {
          DataInputStream dis = new DataInputStream(bais);

          public int readInt() throws IOException {
            return dis.readInt();
          }

          public byte readByte() throws IOException {
            return dis.readByte();
          }

          public int bytesRemaining() {
            throw new RuntimeException("Not Implemented.");
          }

          public String readUTF() throws IOException {
            throw new RuntimeException("Not Implemented.");
          }

          public short readShort() throws IOException {
            throw new RuntimeException("Not Implemented.");
          }

          public short peakShort() throws IOException {
            throw new RuntimeException("Not Implemented.");
          }

          public long readLong() throws IOException {
            throw new RuntimeException("Not Implemented.");
          }

          public float readFloat() throws IOException {
            throw new RuntimeException("Not Implemented.");
          }

          public double readDouble() throws IOException {
            throw new RuntimeException("Not Implemented.");
          }

          public char readChar() throws IOException {
            throw new RuntimeException("Not Implemented.");
          }

          public boolean readBoolean() throws IOException {
            throw new RuntimeException("Not Implemented.");
          }

          public int read(byte[] b) throws IOException {
            throw new RuntimeException("Not Implemented.");
          }

          public int read(byte[] b, int off, int len) throws IOException {
            throw new RuntimeException("Not Implemented.");
          }
        };

      BloomFilter b = new BloomFilter(buf);

      if (!b.set.equals(a.set)) {
        System.out.println(i + "a:" + a.set);
        System.out.println(i + "b:" + b.set);
        System.out.println();
      }
    }
  }
}