Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * Copyright (C) 2011 The Guava Authors
   *
   * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
   * in compliance with the License. You may obtain a copy of the License at
   *
   * http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software distributed under the License
  * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
  * or implied. See the License for the specific language governing permissions and limitations under
  * the License.
  */
 
 package com.google.common.hash;
 
 import static com.google.common.base.Preconditions.checkArgument;
 
 
 
 import  javax.annotation.Nullable;

Static methods to obtain HashFunction instances, and other static hashing-related utilities.

A comparison of the various hash functions can be found here.

Author(s):
Kevin Bourrillion
Dimitris Andreou
Kurt Alfred Kluever
Since:
11.0
 
 public final class Hashing {
  
Returns a general-purpose, temporary-use, non-cryptographic hash function. The algorithm the returned function implements is unspecified and subject to change without notice.

Warning: a new random seed for these functions is chosen each time the Hashing class is loaded. Do not use this method if hash codes may escape the current process in any way, for example being sent over RPC, or saved to disk.

Repeated calls to this method on the same loaded Hashing class, using the same value for minimumBits, will return identically-behaving HashFunction instances.

Parameters:
minimumBits a positive integer (can be arbitrarily large)
Returns:
a hash function, described above, that produces hash codes of length minimumBits or greater
 
   public static HashFunction goodFastHash(int minimumBits) {
     int bits = checkPositiveAndMakeMultipleOf32(minimumBits);
 
     if (bits == 32) {
       return ;
     }
     if (bits <= 128) {
       return ;
     }
 
     // Otherwise, join together some 128-bit murmur3s
     int hashFunctionsNeeded = (bits + 127) / 128;
     HashFunction[] hashFunctions = new HashFunction[hashFunctionsNeeded];
     hashFunctions[0] = ;
     int seed = ;
     for (int i = 1; i < hashFunctionsNeededi++) {
       seed += 1500450271; // a prime; shouldn't matter
       hashFunctions[i] = murmur3_128(seed);
     }
     return new ConcatenatedHashFunction(hashFunctions);
   }

  
Used to randomize goodFastHash instances, so that programs which persist anything dependent on the hash codes they produce will fail sooner.
 
   private static final int GOOD_FAST_HASH_SEED = (int) System.currentTimeMillis();

  
Returned by goodFastHash when minimumBits <= 32.
 
Returned by goodFastHash when 32 < minimumBits <= 128.
 
Returns a hash function implementing the 32-bit murmur3 algorithm, x86 variant (little-endian variant), using the given seed value.

The exact C++ equivalent is the MurmurHash3_x86_32 function (Murmur3A).

  public static HashFunction murmur3_32(int seed) {
    return new Murmur3_32HashFunction(seed);
  }

  
Returns a hash function implementing the 32-bit murmur3 algorithm, x86 variant (little-endian variant), using a seed value of zero.

The exact C++ equivalent is the MurmurHash3_x86_32 function (Murmur3A).

  public static HashFunction murmur3_32() {
    return ;
  }
  private static final HashFunction MURMUR3_32 = new Murmur3_32HashFunction(0);

  
Returns a hash function implementing the 128-bit murmur3 algorithm, x64 variant (little-endian variant), using the given seed value.

The exact C++ equivalent is the MurmurHash3_x64_128 function (Murmur3F).

  public static HashFunction murmur3_128(int seed) {
    return new Murmur3_128HashFunction(seed);
  }

  
Returns a hash function implementing the 128-bit murmur3 algorithm, x64 variant (little-endian variant), using a seed value of zero.

The exact C++ equivalent is the MurmurHash3_x64_128 function (Murmur3F).

  public static HashFunction murmur3_128() {
    return ;
  }
  private static final HashFunction MURMUR3_128 = new Murmur3_128HashFunction(0);

  
Returns a hash function implementing the 64-bit SipHash-2-4 algorithm using a seed value of k = 00 01 02 ....

Since:
15.0
  public static HashFunction sipHash24() {
    return ;
  }
  private static final HashFunction SIP_HASH_24 =
      new SipHashFunction(2, 4, 0x0706050403020100L, 0x0f0e0d0c0b0a0908L);

  
Returns a hash function implementing the 64-bit SipHash-2-4 algorithm using the given seed.

Since:
15.0
  public static HashFunction sipHash24(long k0long k1) {
    return new SipHashFunction(2, 4, k0k1);
  }

  
Returns a hash function implementing the MD5 hash algorithm (128 hash bits) by delegating to the MD5 MessageDigest.
  public static HashFunction md5() {
    return ;
  }
  private static final HashFunction MD5 = new MessageDigestHashFunction("MD5""Hashing.md5()");

  
Returns a hash function implementing the SHA-1 algorithm (160 hash bits) by delegating to the SHA-1 MessageDigest.
  public static HashFunction sha1() {
    return ;
  }
  private static final HashFunction SHA_1 =
      new MessageDigestHashFunction("SHA-1""Hashing.sha1()");

  
Returns a hash function implementing the SHA-256 algorithm (256 hash bits) by delegating to the SHA-256 MessageDigest.
  public static HashFunction sha256() {
    return ;
  }
  private static final HashFunction SHA_256 =
      new MessageDigestHashFunction("SHA-256""Hashing.sha256()");

  
Returns a hash function implementing the SHA-512 algorithm (512 hash bits) by delegating to the SHA-512 MessageDigest.
  public static HashFunction sha512() {
    return ;
  }
  private static final HashFunction SHA_512 =
      new MessageDigestHashFunction("SHA-512""Hashing.sha512()");

  
Returns a hash function implementing the CRC-32 checksum algorithm (32 hash bits) by delegating to the CRC32 Checksum.

To get the long value equivalent to Checksum.getValue() for a HashCode produced by this function, use HashCode.padToLong().

Since:
14.0
  public static HashFunction crc32() {
    return ;
  }
  private static final HashFunction CRC_32 =
      checksumHashFunction(."Hashing.crc32()");

  
Returns a hash function implementing the Adler-32 checksum algorithm (32 hash bits) by delegating to the Adler32 Checksum.

To get the long value equivalent to Checksum.getValue() for a HashCode produced by this function, use HashCode.padToLong().

Since:
14.0
  public static HashFunction adler32() {
    return ;
  }
  private static final HashFunction ADLER_32 =
      checksumHashFunction(."Hashing.adler32()");
  private static HashFunction checksumHashFunction(ChecksumType typeString toString) {
    return new ChecksumHashFunction(typetype.bitstoString);
  }
  enum ChecksumType implements Supplier<Checksum> {
    CRC_32(32) {
      @Override
      public Checksum get() {
        return new CRC32();
      }
    },
    ADLER_32(32) {
      @Override
      public Checksum get() {
        return new Adler32();
      }
    };
    private final int bits;
    ChecksumType(int bits) {
      this. = bits;
    }
    @Override
    public abstract Checksum get();
  }
  // Lazy initialization holder class idiom.
  // TODO(user): Investigate whether we need to still use this idiom now that we have a fallback
  // option for our use of Unsafe.

  
Assigns to hashCode a "bucket" in the range [0, buckets), in a uniform manner that minimizes the need for remapping as buckets grows. That is, consistentHash(h, n) equals:
  • n - 1, with approximate probability 1/n
  • consistentHash(h, n - 1), otherwise (probability 1 - 1/n)

See the wikipedia article on consistent hashing for more information.

  public static int consistentHash(HashCode hashCodeint buckets) {
    return consistentHash(hashCode.padToLong(), buckets);
  }

  
Assigns to input a "bucket" in the range [0, buckets), in a uniform manner that minimizes the need for remapping as buckets grows. That is, consistentHash(h, n) equals:
  • n - 1, with approximate probability 1/n
  • consistentHash(h, n - 1), otherwise (probability 1 - 1/n)

See the wikipedia article on consistent hashing for more information.

  public static int consistentHash(long inputint buckets) {
    checkArgument(buckets > 0, "buckets must be positive: %s"buckets);
    int candidate = 0;
    int next;
    // Jump from bucket to bucket until we go out of range
    while (true) {
      next = (int) ((candidate + 1) / generator.nextDouble());
      if (next >= 0 && next < buckets) {
        candidate = next;
      } else {
        return candidate;
      }
    }
  }

  
Returns a hash code, having the same bit length as each of the input hash codes, that combines the information of these hash codes in an ordered fashion. That is, whenever two equal hash codes are produced by two calls to this method, it is as likely as possible that each was computed from the same input hash codes in the same order.

Throws:
IllegalArgumentException if hashCodes is empty, or the hash codes do not all have the same bit length
  public static HashCode combineOrdered(Iterable<HashCodehashCodes) {
    Iterator<HashCodeiterator = hashCodes.iterator();
    checkArgument(iterator.hasNext(), "Must be at least 1 hash code to combine.");
    int bits = iterator.next().bits();
    byte[] resultBytes = new byte[bits / 8];
    for (HashCode hashCode : hashCodes) {
      byte[] nextBytes = hashCode.asBytes();
      checkArgument(nextBytes.length == resultBytes.length,
          "All hashcodes must have the same bit length.");
      for (int i = 0; i < nextBytes.lengthi++) {
        resultBytes[i] = (byte) (resultBytes[i] * 37 ^ nextBytes[i]);
      }
    }
    return HashCode.fromBytesNoCopy(resultBytes);
  }

  
Returns a hash code, having the same bit length as each of the input hash codes, that combines the information of these hash codes in an unordered fashion. That is, whenever two equal hash codes are produced by two calls to this method, it is as likely as possible that each was computed from the same input hash codes in some order.

Throws:
IllegalArgumentException if hashCodes is empty, or the hash codes do not all have the same bit length
  public static HashCode combineUnordered(Iterable<HashCodehashCodes) {
    Iterator<HashCodeiterator = hashCodes.iterator();
    checkArgument(iterator.hasNext(), "Must be at least 1 hash code to combine.");
    byte[] resultBytes = new byte[iterator.next().bits() / 8];
    for (HashCode hashCode : hashCodes) {
      byte[] nextBytes = hashCode.asBytes();
      checkArgument(nextBytes.length == resultBytes.length,
          "All hashcodes must have the same bit length.");
      for (int i = 0; i < nextBytes.lengthi++) {
        resultBytes[i] += nextBytes[i];
      }
    }
    return HashCode.fromBytesNoCopy(resultBytes);
  }

  
Checks that the passed argument is positive, and ceils it to a multiple of 32.
  static int checkPositiveAndMakeMultipleOf32(int bits) {
    checkArgument(bits > 0, "Number of bits must be positive");
    return (bits + 31) & ~31;
  }
  // TODO(kevinb): Maybe expose this class via a static Hashing method?
  static final class ConcatenatedHashFunction extends AbstractCompositeHashFunction {
    private final int bits;
    ConcatenatedHashFunction(HashFunction... functions) {
      super(functions);
      int bitSum = 0;
      for (HashFunction function : functions) {
        bitSum += function.bits();
      }
      this. = bitSum;
    }
    @Override
    HashCode makeHash(Hasher[] hashers) {
      // TODO(user): Get rid of the ByteBuffer here?
      byte[] bytes = new byte[ / 8];
      ByteBuffer buffer = ByteBuffer.wrap(bytes);
      for (Hasher hasher : hashers) {
        buffer.put(hasher.hash().asBytes());
      }
      return HashCode.fromBytesNoCopy(bytes);
    }
    @Override
    public int bits() {
      return ;
    }
    @Override
    public boolean equals(@Nullable Object object) {
      if (object instanceof ConcatenatedHashFunction) {
        ConcatenatedHashFunction other = (ConcatenatedHashFunctionobject;
        if ( != other.bits || . != other.functions.length) {
          return false;
        }
        for (int i = 0; i < .i++) {
          if (![i].equals(other.functions[i])) {
            return false;
          }
        }
        return true;
      }
      return false;
    }
    @Override
    public int hashCode() {
      int hash = ;
      for (HashFunction function : ) {
        hash ^= function.hashCode();
      }
      return hash;
    }
  }

  
Linear CongruentialGenerator to use for consistent hashing. See http://en.wikipedia.org/wiki/Linear_congruential_generator
  private static final class LinearCongruentialGenerator {
    private long state;
    public LinearCongruentialGenerator(long seed) {
      this. = seed;
    }
    public double nextDouble() {
       = 2862933555777941757L *  + 1;
      return ((double) ((int) ( >>> 33) + 1)) / (0x1.0p31);
    }
  }
  private Hashing() {}
New to GrepCode? Check out our FAQ X