BloomFilterTest.java revision 1d580d0f6ee4f21eb309ba7b509d2c6d671c4044
11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert// Copyright 2011 Google Inc. All Rights Reserved. 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.hash; 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.primitives.Ints; 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.testing.SerializableTester; 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport junit.framework.TestCase; 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Random; 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Tests for SimpleGenericBloomFilter and derived BloomFilter views. 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author andreou@google.com (Dimitris Andreou) 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpublic class BloomFilterTest extends TestCase { 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Sanity checking with many combinations of false positive rates and expected insertions 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testBasic() { 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (double fpr = 0.0000001; fpr < 0.1; fpr *= 10) { 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int expectedInsertions = 1; expectedInsertions <= 10000; expectedInsertions *= 10) { 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkSanity(BloomFilter.create(HashTestUtils.BAD_FUNNEL, expectedInsertions, fpr)); 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Tests that we never get an optimal hashes number of zero. 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testOptimalHashes() { 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int n = 1; n < 1000; n++) { 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int m = 0; m < 1000; m++) { 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(BloomFilter.optimalNumOfHashFunctions(n, m) > 0); 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Tests that we always get a non-negative optimal size. 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testOptimalSize() { 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int n = 1; n < 1000; n++) { 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (double fpp = Double.MIN_VALUE; fpp < 1.0; fpp += 0.001) { 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(BloomFilter.optimalNumOfBits(n, fpp) >= 0); 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // some random values 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Random random = new Random(0); 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int repeats = 0; repeats < 10000; repeats++) { 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(BloomFilter.optimalNumOfBits(random.nextInt(1 << 16), random.nextDouble()) >= 0); 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // and some crazy values 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(Integer.MAX_VALUE, BloomFilter.optimalNumOfBits( 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Integer.MAX_VALUE, Double.MIN_VALUE)); 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private void checkSanity(BloomFilter<Object> bf) { 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertFalse(bf.mightContain(new Object())); 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < 100; i++) { 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object o = new Object(); 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert bf.put(o); 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(bf.mightContain(o)); 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testSerialization() { 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert BloomFilter<byte[]> bf = BloomFilter.create(Funnels.byteArrayFunnel(), 100); 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < 10; i++) { 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert bf.put(Ints.toByteArray(i)); 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert bf = SerializableTester.reserialize(bf); 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < 10; i++) { 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(bf.mightContain(Ints.toByteArray(i))); 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 82