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