1// Copyright 2011 Google Inc. All Rights Reserved.
2
3package com.google.common.hash;
4
5import com.google.common.primitives.Ints;
6import com.google.common.testing.SerializableTester;
7
8import junit.framework.TestCase;
9
10import java.util.Random;
11
12/**
13 * Tests for SimpleGenericBloomFilter and derived BloomFilter views.
14 *
15 * @author andreou@google.com (Dimitris Andreou)
16 */
17public 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