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