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