Home | History | Annotate | Download | only in hash 
      1 // Copyright 2011 Google Inc. All Rights Reserved.
      2 
      3 package com.google.common.hash;
      4 
      5 import com.google.common.primitives.Ints;
      6 import com.google.common.testing.SerializableTester;
      7 
      8 import junit.framework.TestCase;
      9 
     10 import java.util.Random;
     11 
     12 /**
     13  * Tests for SimpleGenericBloomFilter and derived BloomFilter views.
     14  *
     15  * @author andreou (at) google.com (Dimitris Andreou)
     16  */
     17 public class BloomFilterTest extends TestCase {
     18   /**
     19    * Sanity checking with many combinations of false positive rates and expected insertions
     20    */
     21   public void testBasic() {
     22     for (double fpr = 0.0000001; fpr < 0.1; fpr *= 10) {
     23       for (int expectedInsertions = 1; expectedInsertions <= 10000; expectedInsertions *= 10) {
     24         checkSanity(BloomFilter.create(HashTestUtils.BAD_FUNNEL, expectedInsertions, fpr));
     25       }
     26     }
     27   }
     28 
     29   /**
     30    * Tests that we never get an optimal hashes number of zero.
     31    */
     32   public void testOptimalHashes() {
     33     for (int n = 1; n < 1000; n++) {
     34       for (int m = 0; m < 1000; m++) {
     35         assertTrue(BloomFilter.optimalNumOfHashFunctions(n, m) > 0);
     36       }
     37     }
     38   }
     39 
     40   /**
     41    * Tests that we always get a non-negative optimal size.
     42    */
     43   public void testOptimalSize() {
     44     for (int n = 1; n < 1000; n++) {
     45       for (double fpp = Double.MIN_VALUE; fpp < 1.0; fpp += 0.001) {
     46         assertTrue(BloomFilter.optimalNumOfBits(n, fpp) >= 0);
     47       }
     48     }
     49 
     50     // some random values
     51     Random random = new Random(0);
     52     for (int repeats = 0; repeats < 10000; repeats++) {
     53       assertTrue(BloomFilter.optimalNumOfBits(random.nextInt(1 << 16), random.nextDouble()) >= 0);
     54     }
     55 
     56     // and some crazy values
     57     assertEquals(Integer.MAX_VALUE, BloomFilter.optimalNumOfBits(
     58         Integer.MAX_VALUE, Double.MIN_VALUE));
     59   }
     60 
     61   private void checkSanity(BloomFilter<Object> bf) {
     62     assertFalse(bf.mightContain(new Object()));
     63     for (int i = 0; i < 100; i++) {
     64       Object o = new Object();
     65       bf.put(o);
     66       assertTrue(bf.mightContain(o));
     67     }
     68   }
     69 
     70   public void testSerialization() {
     71     BloomFilter<byte[]> bf = BloomFilter.create(Funnels.byteArrayFunnel(), 100);
     72     for (int i = 0; i < 10; i++) {
     73       bf.put(Ints.toByteArray(i));
     74     }
     75 
     76     bf = SerializableTester.reserialize(bf);
     77     for (int i = 0; i < 10; i++) {
     78       assertTrue(bf.mightContain(Ints.toByteArray(i)));
     79     }
     80   }
     81 }
     82