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