BloomFilterTest.java revision 7dd252788645e940eada959bdde927426e2531c9
17dd252788645e940eada959bdde927426e2531c9Paul Duffin/* 27dd252788645e940eada959bdde927426e2531c9Paul Duffin * Copyright (C) 2011 The Guava Authors 37dd252788645e940eada959bdde927426e2531c9Paul Duffin * 47dd252788645e940eada959bdde927426e2531c9Paul Duffin * Licensed under the Apache License, Version 2.0 (the "License"); 57dd252788645e940eada959bdde927426e2531c9Paul Duffin * you may not use this file except in compliance with the License. 67dd252788645e940eada959bdde927426e2531c9Paul Duffin * You may obtain a copy of the License at 77dd252788645e940eada959bdde927426e2531c9Paul Duffin * 87dd252788645e940eada959bdde927426e2531c9Paul Duffin * http://www.apache.org/licenses/LICENSE-2.0 97dd252788645e940eada959bdde927426e2531c9Paul Duffin * 107dd252788645e940eada959bdde927426e2531c9Paul Duffin * Unless required by applicable law or agreed to in writing, software 117dd252788645e940eada959bdde927426e2531c9Paul Duffin * distributed under the License is distributed on an "AS IS" BASIS, 127dd252788645e940eada959bdde927426e2531c9Paul Duffin * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 137dd252788645e940eada959bdde927426e2531c9Paul Duffin * See the License for the specific language governing permissions and 147dd252788645e940eada959bdde927426e2531c9Paul Duffin * limitations under the License. 157dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.hash; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 197dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.collect.ImmutableSet; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.primitives.Ints; 217dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.testing.EqualsTester; 227dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.testing.NullPointerTester; 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.testing.SerializableTester; 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Random; 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 277dd252788645e940eada959bdde927426e2531c9Paul Duffinimport javax.annotation.Nullable; 287dd252788645e940eada959bdde927426e2531c9Paul Duffin 297dd252788645e940eada959bdde927426e2531c9Paul Duffinimport junit.framework.TestCase; 307dd252788645e940eada959bdde927426e2531c9Paul Duffin 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Tests for SimpleGenericBloomFilter and derived BloomFilter views. 337dd252788645e940eada959bdde927426e2531c9Paul Duffin * 347dd252788645e940eada959bdde927426e2531c9Paul Duffin * @author Dimitris Andreou 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpublic class BloomFilterTest extends TestCase { 377dd252788645e940eada959bdde927426e2531c9Paul Duffin 387dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testCreateAndCheckBloomFilterWithKnownFalsePositives() { 397dd252788645e940eada959bdde927426e2531c9Paul Duffin int numInsertions = 1000000; 407dd252788645e940eada959bdde927426e2531c9Paul Duffin BloomFilter<CharSequence> bf = BloomFilter.create(Funnels.stringFunnel(), numInsertions); 417dd252788645e940eada959bdde927426e2531c9Paul Duffin 427dd252788645e940eada959bdde927426e2531c9Paul Duffin // Insert "numInsertions" even numbers into the BF. 437dd252788645e940eada959bdde927426e2531c9Paul Duffin for (int i = 0; i < numInsertions * 2; i += 2) { 447dd252788645e940eada959bdde927426e2531c9Paul Duffin bf.put(Integer.toString(i)); 457dd252788645e940eada959bdde927426e2531c9Paul Duffin } 467dd252788645e940eada959bdde927426e2531c9Paul Duffin 477dd252788645e940eada959bdde927426e2531c9Paul Duffin // Assert that the BF "might" have all of the even numbers. 487dd252788645e940eada959bdde927426e2531c9Paul Duffin for (int i = 0; i < numInsertions * 2; i += 2) { 497dd252788645e940eada959bdde927426e2531c9Paul Duffin assertTrue(bf.mightContain(Integer.toString(i))); 507dd252788645e940eada959bdde927426e2531c9Paul Duffin } 517dd252788645e940eada959bdde927426e2531c9Paul Duffin 527dd252788645e940eada959bdde927426e2531c9Paul Duffin // Now we check for known false positives using a set of known false positives. 537dd252788645e940eada959bdde927426e2531c9Paul Duffin // (These are all of the false positives under 900.) 547dd252788645e940eada959bdde927426e2531c9Paul Duffin ImmutableSet<Integer> falsePositives = ImmutableSet.of( 557dd252788645e940eada959bdde927426e2531c9Paul Duffin 49, 51, 59, 163, 199, 321, 325, 363, 367, 469, 545, 561, 727, 769, 773, 781); 567dd252788645e940eada959bdde927426e2531c9Paul Duffin for (int i = 1; i < 900; i += 2) { 577dd252788645e940eada959bdde927426e2531c9Paul Duffin if (!falsePositives.contains(i)) { 587dd252788645e940eada959bdde927426e2531c9Paul Duffin assertFalse("BF should not contain " + i, bf.mightContain(Integer.toString(i))); 597dd252788645e940eada959bdde927426e2531c9Paul Duffin } 607dd252788645e940eada959bdde927426e2531c9Paul Duffin } 617dd252788645e940eada959bdde927426e2531c9Paul Duffin 627dd252788645e940eada959bdde927426e2531c9Paul Duffin // Check that there are exactly 29824 false positives for this BF. 637dd252788645e940eada959bdde927426e2531c9Paul Duffin int knownNumberOfFalsePositives = 29824; 647dd252788645e940eada959bdde927426e2531c9Paul Duffin int numFpp = 0; 657dd252788645e940eada959bdde927426e2531c9Paul Duffin for (int i = 1; i < numInsertions * 2; i += 2) { 667dd252788645e940eada959bdde927426e2531c9Paul Duffin if (bf.mightContain(Integer.toString(i))) { 677dd252788645e940eada959bdde927426e2531c9Paul Duffin numFpp++; 687dd252788645e940eada959bdde927426e2531c9Paul Duffin } 697dd252788645e940eada959bdde927426e2531c9Paul Duffin } 707dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals(knownNumberOfFalsePositives, numFpp); 717dd252788645e940eada959bdde927426e2531c9Paul Duffin double actualFpp = (double) knownNumberOfFalsePositives / numInsertions; 727dd252788645e940eada959bdde927426e2531c9Paul Duffin double expectedFpp = bf.expectedFpp(); 737dd252788645e940eada959bdde927426e2531c9Paul Duffin // The normal order of (expected, actual) is reversed here on purpose. 747dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals(actualFpp, expectedFpp, 0.00015); 757dd252788645e940eada959bdde927426e2531c9Paul Duffin } 767dd252788645e940eada959bdde927426e2531c9Paul Duffin 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Sanity checking with many combinations of false positive rates and expected insertions 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testBasic() { 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (double fpr = 0.0000001; fpr < 0.1; fpr *= 10) { 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int expectedInsertions = 1; expectedInsertions <= 10000; expectedInsertions *= 10) { 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkSanity(BloomFilter.create(HashTestUtils.BAD_FUNNEL, expectedInsertions, fpr)); 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 877dd252788645e940eada959bdde927426e2531c9Paul Duffin 887dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testPreconditions() { 897dd252788645e940eada959bdde927426e2531c9Paul Duffin try { 907dd252788645e940eada959bdde927426e2531c9Paul Duffin BloomFilter.create(Funnels.stringFunnel(), -1); 917dd252788645e940eada959bdde927426e2531c9Paul Duffin fail(); 927dd252788645e940eada959bdde927426e2531c9Paul Duffin } catch (IllegalArgumentException expected) {} 937dd252788645e940eada959bdde927426e2531c9Paul Duffin try { 947dd252788645e940eada959bdde927426e2531c9Paul Duffin BloomFilter.create(Funnels.stringFunnel(), -1, 0.03); 957dd252788645e940eada959bdde927426e2531c9Paul Duffin fail(); 967dd252788645e940eada959bdde927426e2531c9Paul Duffin } catch (IllegalArgumentException expected) {} 977dd252788645e940eada959bdde927426e2531c9Paul Duffin try { 987dd252788645e940eada959bdde927426e2531c9Paul Duffin BloomFilter.create(Funnels.stringFunnel(), 1, 0.0); 997dd252788645e940eada959bdde927426e2531c9Paul Duffin fail(); 1007dd252788645e940eada959bdde927426e2531c9Paul Duffin } catch (IllegalArgumentException expected) {} 1017dd252788645e940eada959bdde927426e2531c9Paul Duffin try { 1027dd252788645e940eada959bdde927426e2531c9Paul Duffin BloomFilter.create(Funnels.stringFunnel(), 1, 1.0); 1037dd252788645e940eada959bdde927426e2531c9Paul Duffin fail(); 1047dd252788645e940eada959bdde927426e2531c9Paul Duffin } catch (IllegalArgumentException expected) {} 1057dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1067dd252788645e940eada959bdde927426e2531c9Paul Duffin 1077dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testFailureWhenMoreThan255HashFunctionsAreNeeded() { 1087dd252788645e940eada959bdde927426e2531c9Paul Duffin try { 1097dd252788645e940eada959bdde927426e2531c9Paul Duffin int n = 1000; 1107dd252788645e940eada959bdde927426e2531c9Paul Duffin double p = 0.00000000000000000000000000000000000000000000000000000000000000000000000000000001; 1117dd252788645e940eada959bdde927426e2531c9Paul Duffin BloomFilter.create(Funnels.stringFunnel(), n, p); 1127dd252788645e940eada959bdde927426e2531c9Paul Duffin fail(); 1137dd252788645e940eada959bdde927426e2531c9Paul Duffin } catch (IllegalArgumentException expected) {} 1147dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1157dd252788645e940eada959bdde927426e2531c9Paul Duffin 1167dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testNullPointers() { 1177dd252788645e940eada959bdde927426e2531c9Paul Duffin NullPointerTester tester = new NullPointerTester(); 1187dd252788645e940eada959bdde927426e2531c9Paul Duffin tester.testAllPublicInstanceMethods(BloomFilter.create(Funnels.stringFunnel(), 100)); 1197dd252788645e940eada959bdde927426e2531c9Paul Duffin tester.testAllPublicStaticMethods(BloomFilter.class); 1207dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1217dd252788645e940eada959bdde927426e2531c9Paul Duffin 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1237dd252788645e940eada959bdde927426e2531c9Paul Duffin * Tests that we never get an optimal hashes number of zero. 1241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testOptimalHashes() { 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int n = 1; n < 1000; n++) { 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int m = 0; m < 1000; m++) { 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(BloomFilter.optimalNumOfHashFunctions(n, m) > 0); 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1327dd252788645e940eada959bdde927426e2531c9Paul Duffin 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1347dd252788645e940eada959bdde927426e2531c9Paul Duffin * Tests that we always get a non-negative optimal size. 1351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testOptimalSize() { 1371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int n = 1; n < 1000; n++) { 1381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (double fpp = Double.MIN_VALUE; fpp < 1.0; fpp += 0.001) { 1391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(BloomFilter.optimalNumOfBits(n, fpp) >= 0); 1401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1427dd252788645e940eada959bdde927426e2531c9Paul Duffin 1431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // some random values 1447dd252788645e940eada959bdde927426e2531c9Paul Duffin Random random = new Random(0); 1451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int repeats = 0; repeats < 10000; repeats++) { 1461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(BloomFilter.optimalNumOfBits(random.nextInt(1 << 16), random.nextDouble()) >= 0); 1471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1487dd252788645e940eada959bdde927426e2531c9Paul Duffin 1497dd252788645e940eada959bdde927426e2531c9Paul Duffin // and some crazy values (this used to be capped to Integer.MAX_VALUE, now it can go bigger 1507dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals(3327428144502L, BloomFilter.optimalNumOfBits( 1511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Integer.MAX_VALUE, Double.MIN_VALUE)); 1527dd252788645e940eada959bdde927426e2531c9Paul Duffin try { 1537dd252788645e940eada959bdde927426e2531c9Paul Duffin BloomFilter.create(HashTestUtils.BAD_FUNNEL, Integer.MAX_VALUE, Double.MIN_VALUE); 1547dd252788645e940eada959bdde927426e2531c9Paul Duffin fail("we can't represent such a large BF!"); 1557dd252788645e940eada959bdde927426e2531c9Paul Duffin } catch (IllegalArgumentException expected) { 1567dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals("Could not create BloomFilter of 3327428144502 bits", expected.getMessage()); 1577dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1597dd252788645e940eada959bdde927426e2531c9Paul Duffin 1601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private void checkSanity(BloomFilter<Object> bf) { 1611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertFalse(bf.mightContain(new Object())); 1627dd252788645e940eada959bdde927426e2531c9Paul Duffin assertFalse(bf.apply(new Object())); 1631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < 100; i++) { 1641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object o = new Object(); 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert bf.put(o); 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(bf.mightContain(o)); 1677dd252788645e940eada959bdde927426e2531c9Paul Duffin assertTrue(bf.apply(o)); 1681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1707dd252788645e940eada959bdde927426e2531c9Paul Duffin 1717dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testCopy() { 1727dd252788645e940eada959bdde927426e2531c9Paul Duffin BloomFilter<CharSequence> original = BloomFilter.create(Funnels.stringFunnel(), 100); 1737dd252788645e940eada959bdde927426e2531c9Paul Duffin BloomFilter<CharSequence> copy = original.copy(); 1747dd252788645e940eada959bdde927426e2531c9Paul Duffin assertNotSame(original, copy); 1757dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals(original, copy); 1767dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1777dd252788645e940eada959bdde927426e2531c9Paul Duffin 1787dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testExpectedFpp() { 1797dd252788645e940eada959bdde927426e2531c9Paul Duffin BloomFilter<Object> bf = BloomFilter.create(HashTestUtils.BAD_FUNNEL, 10, 0.03); 1807dd252788645e940eada959bdde927426e2531c9Paul Duffin double fpp = bf.expectedFpp(); 1817dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals(0.0, fpp); 1827dd252788645e940eada959bdde927426e2531c9Paul Duffin // usually completed in less than 200 iterations 1837dd252788645e940eada959bdde927426e2531c9Paul Duffin while (fpp != 1.0) { 1847dd252788645e940eada959bdde927426e2531c9Paul Duffin boolean changed = bf.put(new Object()); 1857dd252788645e940eada959bdde927426e2531c9Paul Duffin double newFpp = bf.expectedFpp(); 1867dd252788645e940eada959bdde927426e2531c9Paul Duffin // if changed, the new fpp is strictly higher, otherwise it is the same 1877dd252788645e940eada959bdde927426e2531c9Paul Duffin assertTrue(changed ? newFpp > fpp : newFpp == fpp); 1887dd252788645e940eada959bdde927426e2531c9Paul Duffin fpp = newFpp; 1897dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1907dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1917dd252788645e940eada959bdde927426e2531c9Paul Duffin 1927dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testEquals_empty() { 1937dd252788645e940eada959bdde927426e2531c9Paul Duffin new EqualsTester() 1947dd252788645e940eada959bdde927426e2531c9Paul Duffin .addEqualityGroup(BloomFilter.create(Funnels.byteArrayFunnel(), 100, 0.01)) 1957dd252788645e940eada959bdde927426e2531c9Paul Duffin .addEqualityGroup(BloomFilter.create(Funnels.byteArrayFunnel(), 100, 0.02)) 1967dd252788645e940eada959bdde927426e2531c9Paul Duffin .addEqualityGroup(BloomFilter.create(Funnels.byteArrayFunnel(), 200, 0.01)) 1977dd252788645e940eada959bdde927426e2531c9Paul Duffin .addEqualityGroup(BloomFilter.create(Funnels.byteArrayFunnel(), 200, 0.02)) 1987dd252788645e940eada959bdde927426e2531c9Paul Duffin .addEqualityGroup(BloomFilter.create(Funnels.stringFunnel(), 100, 0.01)) 1997dd252788645e940eada959bdde927426e2531c9Paul Duffin .addEqualityGroup(BloomFilter.create(Funnels.stringFunnel(), 100, 0.02)) 2007dd252788645e940eada959bdde927426e2531c9Paul Duffin .addEqualityGroup(BloomFilter.create(Funnels.stringFunnel(), 200, 0.01)) 2017dd252788645e940eada959bdde927426e2531c9Paul Duffin .addEqualityGroup(BloomFilter.create(Funnels.stringFunnel(), 200, 0.02)) 2027dd252788645e940eada959bdde927426e2531c9Paul Duffin .testEquals(); 2037dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2047dd252788645e940eada959bdde927426e2531c9Paul Duffin 2057dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testEquals() { 2067dd252788645e940eada959bdde927426e2531c9Paul Duffin BloomFilter<CharSequence> bf1 = BloomFilter.create(Funnels.stringFunnel(), 100); 2077dd252788645e940eada959bdde927426e2531c9Paul Duffin bf1.put("1"); 2087dd252788645e940eada959bdde927426e2531c9Paul Duffin bf1.put("2"); 2097dd252788645e940eada959bdde927426e2531c9Paul Duffin 2107dd252788645e940eada959bdde927426e2531c9Paul Duffin BloomFilter<CharSequence> bf2 = BloomFilter.create(Funnels.stringFunnel(), 100); 2117dd252788645e940eada959bdde927426e2531c9Paul Duffin bf2.put("1"); 2127dd252788645e940eada959bdde927426e2531c9Paul Duffin bf2.put("2"); 2137dd252788645e940eada959bdde927426e2531c9Paul Duffin 2147dd252788645e940eada959bdde927426e2531c9Paul Duffin new EqualsTester() 2157dd252788645e940eada959bdde927426e2531c9Paul Duffin .addEqualityGroup(bf1, bf2) 2167dd252788645e940eada959bdde927426e2531c9Paul Duffin .testEquals(); 2177dd252788645e940eada959bdde927426e2531c9Paul Duffin 2187dd252788645e940eada959bdde927426e2531c9Paul Duffin bf2.put("3"); 2197dd252788645e940eada959bdde927426e2531c9Paul Duffin 2207dd252788645e940eada959bdde927426e2531c9Paul Duffin new EqualsTester() 2217dd252788645e940eada959bdde927426e2531c9Paul Duffin .addEqualityGroup(bf1) 2227dd252788645e940eada959bdde927426e2531c9Paul Duffin .addEqualityGroup(bf2) 2237dd252788645e940eada959bdde927426e2531c9Paul Duffin .testEquals(); 2247dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2257dd252788645e940eada959bdde927426e2531c9Paul Duffin 2267dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testEqualsWithCustomFunnel() { 2277dd252788645e940eada959bdde927426e2531c9Paul Duffin BloomFilter<Long> bf1 = BloomFilter.create(new CustomFunnel(), 100); 2287dd252788645e940eada959bdde927426e2531c9Paul Duffin BloomFilter<Long> bf2 = BloomFilter.create(new CustomFunnel(), 100); 2297dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals(bf1, bf2); 2307dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2317dd252788645e940eada959bdde927426e2531c9Paul Duffin 2327dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testSerializationWithCustomFunnel() { 2337dd252788645e940eada959bdde927426e2531c9Paul Duffin SerializableTester.reserializeAndAssert(BloomFilter.create(new CustomFunnel(), 100)); 2347dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2357dd252788645e940eada959bdde927426e2531c9Paul Duffin 2367dd252788645e940eada959bdde927426e2531c9Paul Duffin private static final class CustomFunnel implements Funnel<Long> { 2377dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 2387dd252788645e940eada959bdde927426e2531c9Paul Duffin public void funnel(Long value, PrimitiveSink into) { 2397dd252788645e940eada959bdde927426e2531c9Paul Duffin into.putLong(value); 2407dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2417dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 2427dd252788645e940eada959bdde927426e2531c9Paul Duffin public boolean equals(@Nullable Object object) { 2437dd252788645e940eada959bdde927426e2531c9Paul Duffin return (object instanceof CustomFunnel); 2447dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2457dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 2467dd252788645e940eada959bdde927426e2531c9Paul Duffin public int hashCode() { 2477dd252788645e940eada959bdde927426e2531c9Paul Duffin return 42; 2487dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2497dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2507dd252788645e940eada959bdde927426e2531c9Paul Duffin 2517dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testPutReturnValue() { 2527dd252788645e940eada959bdde927426e2531c9Paul Duffin for (int i = 0; i < 10; i++) { 2537dd252788645e940eada959bdde927426e2531c9Paul Duffin BloomFilter<CharSequence> bf = BloomFilter.create(Funnels.stringFunnel(), 100); 2547dd252788645e940eada959bdde927426e2531c9Paul Duffin for (int j = 0; j < 10; j++) { 2557dd252788645e940eada959bdde927426e2531c9Paul Duffin String value = new Object().toString(); 2567dd252788645e940eada959bdde927426e2531c9Paul Duffin boolean mightContain = bf.mightContain(value); 2577dd252788645e940eada959bdde927426e2531c9Paul Duffin boolean put = bf.put(value); 2587dd252788645e940eada959bdde927426e2531c9Paul Duffin assertTrue(mightContain != put); 2597dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2607dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2617dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2627dd252788645e940eada959bdde927426e2531c9Paul Duffin 2637dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testJavaSerialization() { 2641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert BloomFilter<byte[]> bf = BloomFilter.create(Funnels.byteArrayFunnel(), 100); 2651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < 10; i++) { 2661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert bf.put(Ints.toByteArray(i)); 2671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2687dd252788645e940eada959bdde927426e2531c9Paul Duffin 2697dd252788645e940eada959bdde927426e2531c9Paul Duffin BloomFilter<byte[]> copy = SerializableTester.reserialize(bf); 2701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < 10; i++) { 2717dd252788645e940eada959bdde927426e2531c9Paul Duffin assertTrue(copy.mightContain(Ints.toByteArray(i))); 2721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2737dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals(bf.expectedFpp(), copy.expectedFpp()); 2747dd252788645e940eada959bdde927426e2531c9Paul Duffin 2757dd252788645e940eada959bdde927426e2531c9Paul Duffin SerializableTester.reserializeAndAssert(bf); 2767dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2777dd252788645e940eada959bdde927426e2531c9Paul Duffin 2787dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 2797dd252788645e940eada959bdde927426e2531c9Paul Duffin * This test will fail whenever someone updates/reorders the BloomFilterStrategies constants. 2807dd252788645e940eada959bdde927426e2531c9Paul Duffin * Only appending a new constant is allowed. 2817dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 2827dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testBloomFilterStrategies() { 2837dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals(1, BloomFilterStrategies.values().length); 2847dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals(BloomFilterStrategies.MURMUR128_MITZ_32, BloomFilterStrategies.values()[0]); 2851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 287