001/* 002 * Copyright (C) 2011 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 005 * in compliance with the License. You may obtain a copy of the License at 006 * 007 * http://www.apache.org/licenses/LICENSE-2.0 008 * 009 * Unless required by applicable law or agreed to in writing, software distributed under the License 010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 011 * or implied. See the License for the specific language governing permissions and limitations under 012 * the License. 013 */ 014 015package com.google.common.hash; 016 017import static com.google.common.base.Preconditions.checkArgument; 018import static com.google.common.base.Preconditions.checkNotNull; 019 020import com.google.common.annotations.Beta; 021import com.google.common.annotations.VisibleForTesting; 022import com.google.common.base.Objects; 023import com.google.common.base.Predicate; 024import com.google.common.hash.BloomFilterStrategies.BitArray; 025import com.google.common.primitives.SignedBytes; 026import com.google.common.primitives.UnsignedBytes; 027import com.google.errorprone.annotations.CanIgnoreReturnValue; 028import java.io.DataInputStream; 029import java.io.DataOutputStream; 030import java.io.IOException; 031import java.io.InputStream; 032import java.io.OutputStream; 033import java.io.Serializable; 034import javax.annotation.Nullable; 035 036/** 037 * A Bloom filter for instances of {@code T}. A Bloom filter offers an approximate containment test 038 * with one-sided error: if it claims that an element is contained in it, this might be in error, 039 * but if it claims that an element is <i>not</i> contained in it, then this is definitely true. 040 * 041 * <p>If you are unfamiliar with Bloom filters, this nice 042 * <a href="http://llimllib.github.com/bloomfilter-tutorial/">tutorial</a> may help you understand 043 * how they work. 044 * 045 * <p>The false positive probability ({@code FPP}) of a bloom filter is defined as the probability 046 * that {@linkplain #mightContain(Object)} will erroneously return {@code true} for an object that 047 * has not actually been put in the {@code BloomFilter}. 048 * 049 * <p>Bloom filters are serializable. They also support a more compact serial representation via the 050 * {@link #writeTo} and {@link #readFrom} methods. Both serialized forms will continue to be 051 * supported by future versions of this library. However, serial forms generated by newer versions 052 * of the code may not be readable by older versions of the code (e.g., a serialized bloom filter 053 * generated today may <i>not</i> be readable by a binary that was compiled 6 months ago). 054 * 055 * @param <T> the type of instances that the {@code BloomFilter} accepts 056 * @author Dimitris Andreou 057 * @author Kevin Bourrillion 058 * @since 11.0 059 */ 060@Beta 061public final class BloomFilter<T> implements Predicate<T>, Serializable { 062 /** 063 * A strategy to translate T instances, to {@code numHashFunctions} bit indexes. 064 * 065 * <p>Implementations should be collections of pure functions (i.e. stateless). 066 */ 067 interface Strategy extends java.io.Serializable { 068 069 /** 070 * Sets {@code numHashFunctions} bits of the given bit array, by hashing a user element. 071 * 072 * <p>Returns whether any bits changed as a result of this operation. 073 */ 074 <T> boolean put(T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits); 075 076 /** 077 * Queries {@code numHashFunctions} bits of the given bit array, by hashing a user element; 078 * returns {@code true} if and only if all selected bits are set. 079 */ 080 <T> boolean mightContain( 081 T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits); 082 083 /** 084 * Identifier used to encode this strategy, when marshalled as part of a BloomFilter. Only 085 * values in the [-128, 127] range are valid for the compact serial form. Non-negative values 086 * are reserved for enums defined in BloomFilterStrategies; negative values are reserved for any 087 * custom, stateful strategy we may define (e.g. any kind of strategy that would depend on user 088 * input). 089 */ 090 int ordinal(); 091 } 092 093 /** The bit set of the BloomFilter (not necessarily power of 2!) */ 094 private final BitArray bits; 095 096 /** Number of hashes per element */ 097 private final int numHashFunctions; 098 099 /** The funnel to translate Ts to bytes */ 100 private final Funnel<? super T> funnel; 101 102 /** 103 * The strategy we employ to map an element T to {@code numHashFunctions} bit indexes. 104 */ 105 private final Strategy strategy; 106 107 /** 108 * Creates a BloomFilter. 109 */ 110 private BloomFilter( 111 BitArray bits, int numHashFunctions, Funnel<? super T> funnel, Strategy strategy) { 112 checkArgument(numHashFunctions > 0, "numHashFunctions (%s) must be > 0", numHashFunctions); 113 checkArgument( 114 numHashFunctions <= 255, "numHashFunctions (%s) must be <= 255", numHashFunctions); 115 this.bits = checkNotNull(bits); 116 this.numHashFunctions = numHashFunctions; 117 this.funnel = checkNotNull(funnel); 118 this.strategy = checkNotNull(strategy); 119 } 120 121 /** 122 * Creates a new {@code BloomFilter} that's a copy of this instance. The new instance is equal to 123 * this instance but shares no mutable state. 124 * 125 * @since 12.0 126 */ 127 public BloomFilter<T> copy() { 128 return new BloomFilter<T>(bits.copy(), numHashFunctions, funnel, strategy); 129 } 130 131 /** 132 * Returns {@code true} if the element <i>might</i> have been put in this Bloom filter, 133 * {@code false} if this is <i>definitely</i> not the case. 134 */ 135 public boolean mightContain(T object) { 136 return strategy.mightContain(object, funnel, numHashFunctions, bits); 137 } 138 139 /** 140 * @deprecated Provided only to satisfy the {@link Predicate} interface; use {@link #mightContain} 141 * instead. 142 */ 143 @Deprecated 144 @Override 145 public boolean apply(T input) { 146 return mightContain(input); 147 } 148 149 /** 150 * Puts an element into this {@code BloomFilter}. Ensures that subsequent invocations of 151 * {@link #mightContain(Object)} with the same element will always return {@code true}. 152 * 153 * @return true if the bloom filter's bits changed as a result of this operation. If the bits 154 * changed, this is <i>definitely</i> the first time {@code object} has been added to the 155 * filter. If the bits haven't changed, this <i>might</i> be the first time {@code object} has 156 * been added to the filter. Note that {@code put(t)} always returns the <i>opposite</i> 157 * result to what {@code mightContain(t)} would have returned at the time it is called." 158 * @since 12.0 (present in 11.0 with {@code void} return type}) 159 */ 160 @CanIgnoreReturnValue 161 public boolean put(T object) { 162 return strategy.put(object, funnel, numHashFunctions, bits); 163 } 164 165 /** 166 * Returns the probability that {@linkplain #mightContain(Object)} will erroneously return 167 * {@code true} for an object that has not actually been put in the {@code BloomFilter}. 168 * 169 * <p>Ideally, this number should be close to the {@code fpp} parameter passed in 170 * {@linkplain #create(Funnel, int, double)}, or smaller. If it is significantly higher, it is 171 * usually the case that too many elements (more than expected) have been put in the 172 * {@code BloomFilter}, degenerating it. 173 * 174 * @since 14.0 (since 11.0 as expectedFalsePositiveProbability()) 175 */ 176 public double expectedFpp() { 177 // You down with FPP? (Yeah you know me!) Who's down with FPP? (Every last homie!) 178 return Math.pow((double) bits.bitCount() / bitSize(), numHashFunctions); 179 } 180 181 /** 182 * Returns the number of bits in the underlying bit array. 183 */ 184 @VisibleForTesting 185 long bitSize() { 186 return bits.bitSize(); 187 } 188 189 /** 190 * Determines whether a given bloom filter is compatible with this bloom filter. For two bloom 191 * filters to be compatible, they must: 192 * 193 * <ul> 194 * <li>not be the same instance 195 * <li>have the same number of hash functions 196 * <li>have the same bit size 197 * <li>have the same strategy 198 * <li>have equal funnels 199 * <ul> 200 * 201 * @param that The bloom filter to check for compatibility. 202 * @since 15.0 203 */ 204 public boolean isCompatible(BloomFilter<T> that) { 205 checkNotNull(that); 206 return (this != that) 207 && (this.numHashFunctions == that.numHashFunctions) 208 && (this.bitSize() == that.bitSize()) 209 && (this.strategy.equals(that.strategy)) 210 && (this.funnel.equals(that.funnel)); 211 } 212 213 /** 214 * Combines this bloom filter with another bloom filter by performing a bitwise OR of the 215 * underlying data. The mutations happen to <b>this</b> instance. Callers must ensure the bloom 216 * filters are appropriately sized to avoid saturating them. 217 * 218 * @param that The bloom filter to combine this bloom filter with. It is not mutated. 219 * @throws IllegalArgumentException if {@code isCompatible(that) == false} 220 * 221 * @since 15.0 222 */ 223 public void putAll(BloomFilter<T> that) { 224 checkNotNull(that); 225 checkArgument(this != that, "Cannot combine a BloomFilter with itself."); 226 checkArgument( 227 this.numHashFunctions == that.numHashFunctions, 228 "BloomFilters must have the same number of hash functions (%s != %s)", 229 this.numHashFunctions, 230 that.numHashFunctions); 231 checkArgument( 232 this.bitSize() == that.bitSize(), 233 "BloomFilters must have the same size underlying bit arrays (%s != %s)", 234 this.bitSize(), 235 that.bitSize()); 236 checkArgument( 237 this.strategy.equals(that.strategy), 238 "BloomFilters must have equal strategies (%s != %s)", 239 this.strategy, 240 that.strategy); 241 checkArgument( 242 this.funnel.equals(that.funnel), 243 "BloomFilters must have equal funnels (%s != %s)", 244 this.funnel, 245 that.funnel); 246 this.bits.putAll(that.bits); 247 } 248 249 @Override 250 public boolean equals(@Nullable Object object) { 251 if (object == this) { 252 return true; 253 } 254 if (object instanceof BloomFilter) { 255 BloomFilter<?> that = (BloomFilter<?>) object; 256 return this.numHashFunctions == that.numHashFunctions 257 && this.funnel.equals(that.funnel) 258 && this.bits.equals(that.bits) 259 && this.strategy.equals(that.strategy); 260 } 261 return false; 262 } 263 264 @Override 265 public int hashCode() { 266 return Objects.hashCode(numHashFunctions, funnel, strategy, bits); 267 } 268 269 /** 270 * Creates a {@link BloomFilter BloomFilter<T>} with the expected number of insertions and 271 * expected false positive probability. 272 * 273 * <p>Note that overflowing a {@code BloomFilter} with significantly more elements than specified, 274 * will result in its saturation, and a sharp deterioration of its false positive probability. 275 * 276 * <p>The constructed {@code BloomFilter<T>} will be serializable if the provided 277 * {@code Funnel<T>} is. 278 * 279 * <p>It is recommended that the funnel be implemented as a Java enum. This has the benefit of 280 * ensuring proper serialization and deserialization, which is important since {@link #equals} 281 * also relies on object identity of funnels. 282 * 283 * @param funnel the funnel of T's that the constructed {@code BloomFilter<T>} will use 284 * @param expectedInsertions the number of expected insertions to the constructed 285 * {@code BloomFilter<T>}; must be positive 286 * @param fpp the desired false positive probability (must be positive and less than 1.0) 287 * @return a {@code BloomFilter} 288 */ 289 public static <T> BloomFilter<T> create( 290 Funnel<? super T> funnel, int expectedInsertions, double fpp) { 291 return create(funnel, (long) expectedInsertions, fpp); 292 } 293 294 /** 295 * Creates a {@link BloomFilter BloomFilter<T>} with the expected number of insertions and 296 * expected false positive probability. 297 * 298 * <p>Note that overflowing a {@code BloomFilter} with significantly more elements than specified, 299 * will result in its saturation, and a sharp deterioration of its false positive probability. 300 * 301 * <p>The constructed {@code BloomFilter<T>} will be serializable if the provided 302 * {@code Funnel<T>} is. 303 * 304 * <p>It is recommended that the funnel be implemented as a Java enum. This has the benefit of 305 * ensuring proper serialization and deserialization, which is important since {@link #equals} 306 * also relies on object identity of funnels. 307 * 308 * @param funnel the funnel of T's that the constructed {@code BloomFilter<T>} will use 309 * @param expectedInsertions the number of expected insertions to the constructed 310 * {@code BloomFilter<T>}; must be positive 311 * @param fpp the desired false positive probability (must be positive and less than 1.0) 312 * @return a {@code BloomFilter} 313 * @since 19.0 314 */ 315 public static <T> BloomFilter<T> create( 316 Funnel<? super T> funnel, long expectedInsertions, double fpp) { 317 return create(funnel, expectedInsertions, fpp, BloomFilterStrategies.MURMUR128_MITZ_64); 318 } 319 320 @VisibleForTesting 321 static <T> BloomFilter<T> create( 322 Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) { 323 checkNotNull(funnel); 324 checkArgument( 325 expectedInsertions >= 0, "Expected insertions (%s) must be >= 0", expectedInsertions); 326 checkArgument(fpp > 0.0, "False positive probability (%s) must be > 0.0", fpp); 327 checkArgument(fpp < 1.0, "False positive probability (%s) must be < 1.0", fpp); 328 checkNotNull(strategy); 329 330 if (expectedInsertions == 0) { 331 expectedInsertions = 1; 332 } 333 /* 334 * TODO(user): Put a warning in the javadoc about tiny fpp values, since the resulting size 335 * is proportional to -log(p), but there is not much of a point after all, e.g. 336 * optimalM(1000, 0.0000000000000001) = 76680 which is less than 10kb. Who cares! 337 */ 338 long numBits = optimalNumOfBits(expectedInsertions, fpp); 339 int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits); 340 try { 341 return new BloomFilter<T>(new BitArray(numBits), numHashFunctions, funnel, strategy); 342 } catch (IllegalArgumentException e) { 343 throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e); 344 } 345 } 346 347 /** 348 * Creates a {@link BloomFilter BloomFilter<T>} with the expected number of insertions and a 349 * default expected false positive probability of 3%. 350 * 351 * <p>Note that overflowing a {@code BloomFilter} with significantly more elements than specified, 352 * will result in its saturation, and a sharp deterioration of its false positive probability. 353 * 354 * <p>The constructed {@code BloomFilter<T>} will be serializable if the provided 355 * {@code Funnel<T>} is. 356 * 357 * <p>It is recommended that the funnel be implemented as a Java enum. This has the benefit of 358 * ensuring proper serialization and deserialization, which is important since {@link #equals} 359 * also relies on object identity of funnels. 360 * 361 * @param funnel the funnel of T's that the constructed {@code BloomFilter<T>} will use 362 * @param expectedInsertions the number of expected insertions to the constructed 363 * {@code BloomFilter<T>}; must be positive 364 * @return a {@code BloomFilter} 365 */ 366 public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions) { 367 return create(funnel, (long) expectedInsertions); 368 } 369 370 /** 371 * Creates a {@link BloomFilter BloomFilter<T>} with the expected number of insertions and a 372 * default expected false positive probability of 3%. 373 * 374 * <p>Note that overflowing a {@code BloomFilter} with significantly more elements than specified, 375 * will result in its saturation, and a sharp deterioration of its false positive probability. 376 * 377 * <p>The constructed {@code BloomFilter<T>} will be serializable if the provided 378 * {@code Funnel<T>} is. 379 * 380 * <p>It is recommended that the funnel be implemented as a Java enum. This has the benefit of 381 * ensuring proper serialization and deserialization, which is important since {@link #equals} 382 * also relies on object identity of funnels. 383 * 384 * @param funnel the funnel of T's that the constructed {@code BloomFilter<T>} will use 385 * @param expectedInsertions the number of expected insertions to the constructed 386 * {@code BloomFilter<T>}; must be positive 387 * @return a {@code BloomFilter} 388 * @since 19.0 389 */ 390 public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) { 391 return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions 392 } 393 394 // Cheat sheet: 395 // 396 // m: total bits 397 // n: expected insertions 398 // b: m/n, bits per insertion 399 // p: expected false positive probability 400 // 401 // 1) Optimal k = b * ln2 402 // 2) p = (1 - e ^ (-kn/m))^k 403 // 3) For optimal k: p = 2 ^ (-k) ~= 0.6185^b 404 // 4) For optimal k: m = -nlnp / ((ln2) ^ 2) 405 406 /** 407 * Computes the optimal k (number of hashes per element inserted in Bloom filter), given the 408 * expected insertions and total number of bits in the Bloom filter. 409 * 410 * See http://en.wikipedia.org/wiki/File:Bloom_filter_fp_probability.svg for the formula. 411 * 412 * @param n expected insertions (must be positive) 413 * @param m total number of bits in Bloom filter (must be positive) 414 */ 415 @VisibleForTesting 416 static int optimalNumOfHashFunctions(long n, long m) { 417 // (m / n) * log(2), but avoid truncation due to division! 418 return Math.max(1, (int) Math.round((double) m / n * Math.log(2))); 419 } 420 421 /** 422 * Computes m (total bits of Bloom filter) which is expected to achieve, for the specified 423 * expected insertions, the required false positive probability. 424 * 425 * See http://en.wikipedia.org/wiki/Bloom_filter#Probability_of_false_positives for the formula. 426 * 427 * @param n expected insertions (must be positive) 428 * @param p false positive rate (must be 0 < p < 1) 429 */ 430 @VisibleForTesting 431 static long optimalNumOfBits(long n, double p) { 432 if (p == 0) { 433 p = Double.MIN_VALUE; 434 } 435 return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2))); 436 } 437 438 private Object writeReplace() { 439 return new SerialForm<T>(this); 440 } 441 442 private static class SerialForm<T> implements Serializable { 443 final long[] data; 444 final int numHashFunctions; 445 final Funnel<? super T> funnel; 446 final Strategy strategy; 447 448 SerialForm(BloomFilter<T> bf) { 449 this.data = bf.bits.data; 450 this.numHashFunctions = bf.numHashFunctions; 451 this.funnel = bf.funnel; 452 this.strategy = bf.strategy; 453 } 454 455 Object readResolve() { 456 return new BloomFilter<T>(new BitArray(data), numHashFunctions, funnel, strategy); 457 } 458 459 private static final long serialVersionUID = 1; 460 } 461 462 /** 463 * Writes this {@code BloomFilter} to an output stream, with a custom format (not Java 464 * serialization). This has been measured to save at least 400 bytes compared to regular 465 * serialization. 466 * 467 * <p>Use {@linkplain #readFrom(InputStream, Funnel)} to reconstruct the written BloomFilter. 468 */ 469 public void writeTo(OutputStream out) throws IOException { 470 // Serial form: 471 // 1 signed byte for the strategy 472 // 1 unsigned byte for the number of hash functions 473 // 1 big endian int, the number of longs in our bitset 474 // N big endian longs of our bitset 475 DataOutputStream dout = new DataOutputStream(out); 476 dout.writeByte(SignedBytes.checkedCast(strategy.ordinal())); 477 dout.writeByte(UnsignedBytes.checkedCast(numHashFunctions)); // note: checked at the c'tor 478 dout.writeInt(bits.data.length); 479 for (long value : bits.data) { 480 dout.writeLong(value); 481 } 482 } 483 484 /** 485 * Reads a byte stream, which was written by {@linkplain #writeTo(OutputStream)}, into a 486 * {@code BloomFilter<T>}. 487 * 488 * The {@code Funnel} to be used is not encoded in the stream, so it must be provided here. 489 * <b>Warning:</b> the funnel provided <b>must</b> behave identically to the one used to populate 490 * the original Bloom filter! 491 * 492 * @throws IOException if the InputStream throws an {@code IOException}, or if its data does not 493 * appear to be a BloomFilter serialized using the {@linkplain #writeTo(OutputStream)} method. 494 */ 495 public static <T> BloomFilter<T> readFrom(InputStream in, Funnel<T> funnel) throws IOException { 496 checkNotNull(in, "InputStream"); 497 checkNotNull(funnel, "Funnel"); 498 int strategyOrdinal = -1; 499 int numHashFunctions = -1; 500 int dataLength = -1; 501 try { 502 DataInputStream din = new DataInputStream(in); 503 // currently this assumes there is no negative ordinal; will have to be updated if we 504 // add non-stateless strategies (for which we've reserved negative ordinals; see 505 // Strategy.ordinal()). 506 strategyOrdinal = din.readByte(); 507 numHashFunctions = UnsignedBytes.toInt(din.readByte()); 508 dataLength = din.readInt(); 509 510 Strategy strategy = BloomFilterStrategies.values()[strategyOrdinal]; 511 long[] data = new long[dataLength]; 512 for (int i = 0; i < data.length; i++) { 513 data[i] = din.readLong(); 514 } 515 return new BloomFilter<T>(new BitArray(data), numHashFunctions, funnel, strategy); 516 } catch (RuntimeException e) { 517 String message = 518 "Unable to deserialize BloomFilter from InputStream." 519 + " strategyOrdinal: " 520 + strategyOrdinal 521 + " numHashFunctions: " 522 + numHashFunctions 523 + " dataLength: " 524 + dataLength; 525 throw new IOException(message, e); 526 } 527 } 528}