/** * 简单的写一个hash算法 */ publicinthash(String value){ int result = 0; int len = value.length(); for (int i = 0; i < len; i++) { result = seed * result + value.charAt(i) + value.hashCode(); } // 把值的范围控制在cap内 return (cap - 1) & result; } } }
/** * Sets {@code numHashFunctions} bits of the given bit array, by hashing a user element. * * <p>Returns whether any bits changed as a result of this operation. */ <T> booleanput(T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits);
/** * Queries {@code numHashFunctions} bits of the given bit array, by hashing a user element; * returns {@code true} if and only if all selected bits are set. */ <T> booleanmightContain( T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits);
/** * Identifier used to encode this strategy, when marshalled as part of a BloomFilter. Only * values in the [-128, 127] range are valid for the compact serial form. Non-negative values * are reserved for enums defined in BloomFilterStrategies; negative values are reserved for any * custom, stateful strategy we may define (e.g. any kind of strategy that would depend on user * input). */ intordinal(); }
MURMUR128_MITZ_32() { @Override public <T> booleanput( T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits){ long bitSize = bits.bitSize(); long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong(); int hash1 = (int) hash64; int hash2 = (int) (hash64 >>> 32);
boolean bitsChanged = false; for (int i = 1; i <= numHashFunctions; i++) { int combinedHash = hash1 + (i * hash2); // Flip all the bits if it's negative (guaranteed positive number) if (combinedHash < 0) { combinedHash = ~combinedHash; } bitsChanged |= bits.set(combinedHash % bitSize); } return bitsChanged; }
@Override public <T> booleanmightContain( T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits){ long bitSize = bits.bitSize(); long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong(); int hash1 = (int) hash64; int hash2 = (int) (hash64 >>> 32);
for (int i = 1; i <= numHashFunctions; i++) { int combinedHash = hash1 + (i * hash2); // Flip all the bits if it's negative (guaranteed positive number) if (combinedHash < 0) { combinedHash = ~combinedHash; } if (!bits.get(combinedHash % bitSize)) { returnfalse; } } returntrue; } }, /** * This strategy uses all 128 bits of {@link Hashing#murmur3_128} when hashing. It looks different * than the implementation in MURMUR128_MITZ_32 because we're avoiding the multiplication in the * loop and doing a (much simpler) += hash2. We're also changing the index to a positive number by * AND'ing with Long.MAX_VALUE instead of flipping the bits. */ MURMUR128_MITZ_64() { @Override public <T> booleanput( T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits){ long bitSize = bits.bitSize(); byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal(); long hash1 = lowerEight(bytes); long hash2 = upperEight(bytes);
boolean bitsChanged = false; long combinedHash = hash1; for (int i = 0; i < numHashFunctions; i++) { // Make the combined hash positive and indexable bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize); combinedHash += hash2; } return bitsChanged; }
@Override public <T> booleanmightContain( T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits){ long bitSize = bits.bitSize(); byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal(); long hash1 = lowerEight(bytes); long hash2 = upperEight(bytes);
long combinedHash = hash1; for (int i = 0; i < numHashFunctions; i++) { // Make the combined hash positive and indexable if (!bits.get((combinedHash & Long.MAX_VALUE) % bitSize)) { returnfalse; } combinedHash += hash2; } returntrue; }