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.base.Supplier;
022import java.security.Key;
023import java.security.MessageDigest;
024import java.util.ArrayList;
025import java.util.Arrays;
026import java.util.Iterator;
027import java.util.List;
028import java.util.zip.Adler32;
029import java.util.zip.CRC32;
030import java.util.zip.Checksum;
031import javax.annotation.Nullable;
032import javax.crypto.spec.SecretKeySpec;
033
034/**
035 * Static methods to obtain {@link HashFunction} instances, and other static hashing-related
036 * utilities.
037 *
038 * <p>A comparison of the various hash functions can be found
039 * <a href="http://goo.gl/jS7HH">here</a>.
040 *
041 * @author Kevin Bourrillion
042 * @author Dimitris Andreou
043 * @author Kurt Alfred Kluever
044 * @since 11.0
045 */
046@Beta
047public final class Hashing {
048  /**
049   * Returns a general-purpose, <b>temporary-use</b>, non-cryptographic hash function. The algorithm
050   * the returned function implements is unspecified and subject to change without notice.
051   *
052   * <p><b>Warning:</b> a new random seed for these functions is chosen each time the {@code
053   * Hashing} class is loaded. <b>Do not use this method</b> if hash codes may escape the current
054   * process in any way, for example being sent over RPC, or saved to disk.
055   *
056   * <p>Repeated calls to this method on the same loaded {@code Hashing} class, using the same value
057   * for {@code minimumBits}, will return identically-behaving {@link HashFunction} instances.
058   *
059   * @param minimumBits a positive integer (can be arbitrarily large)
060   * @return a hash function, described above, that produces hash codes of length {@code
061   *     minimumBits} or greater
062   */
063  public static HashFunction goodFastHash(int minimumBits) {
064    int bits = checkPositiveAndMakeMultipleOf32(minimumBits);
065
066    if (bits == 32) {
067      return Murmur3_32Holder.GOOD_FAST_HASH_FUNCTION_32;
068    }
069    if (bits <= 128) {
070      return Murmur3_128Holder.GOOD_FAST_HASH_FUNCTION_128;
071    }
072
073    // Otherwise, join together some 128-bit murmur3s
074    int hashFunctionsNeeded = (bits + 127) / 128;
075    HashFunction[] hashFunctions = new HashFunction[hashFunctionsNeeded];
076    hashFunctions[0] = Murmur3_128Holder.GOOD_FAST_HASH_FUNCTION_128;
077    int seed = GOOD_FAST_HASH_SEED;
078    for (int i = 1; i < hashFunctionsNeeded; i++) {
079      seed += 1500450271; // a prime; shouldn't matter
080      hashFunctions[i] = murmur3_128(seed);
081    }
082    return new ConcatenatedHashFunction(hashFunctions);
083  }
084
085  /**
086   * Used to randomize {@link #goodFastHash} instances, so that programs which persist anything
087   * dependent on the hash codes they produce will fail sooner.
088   */
089  private static final int GOOD_FAST_HASH_SEED = (int) System.currentTimeMillis();
090
091  /**
092   * Returns a hash function implementing the
093   * <a href="http://smhasher.googlecode.com/svn/trunk/MurmurHash3.cpp">32-bit murmur3 algorithm,
094   * x86 variant</a> (little-endian variant), using the given seed value.
095   *
096   * <p>The exact C++ equivalent is the MurmurHash3_x86_32 function (Murmur3A).
097   */
098  public static HashFunction murmur3_32(int seed) {
099    return new Murmur3_32HashFunction(seed);
100  }
101
102  /**
103   * Returns a hash function implementing the
104   * <a href="http://smhasher.googlecode.com/svn/trunk/MurmurHash3.cpp">32-bit murmur3 algorithm,
105   * x86 variant</a> (little-endian variant), using a seed value of zero.
106   *
107   * <p>The exact C++ equivalent is the MurmurHash3_x86_32 function (Murmur3A).
108   */
109  public static HashFunction murmur3_32() {
110    return Murmur3_32Holder.MURMUR3_32;
111  }
112
113  private static class Murmur3_32Holder {
114    static final HashFunction MURMUR3_32 = new Murmur3_32HashFunction(0);
115
116    /** Returned by {@link #goodFastHash} when {@code minimumBits <= 32}. */
117    static final HashFunction GOOD_FAST_HASH_FUNCTION_32 = murmur3_32(GOOD_FAST_HASH_SEED);
118  }
119
120  /**
121   * Returns a hash function implementing the
122   * <a href="http://smhasher.googlecode.com/svn/trunk/MurmurHash3.cpp">128-bit murmur3 algorithm,
123   * x64 variant</a> (little-endian variant), using the given seed value.
124   *
125   * <p>The exact C++ equivalent is the MurmurHash3_x64_128 function (Murmur3F).
126   */
127  public static HashFunction murmur3_128(int seed) {
128    return new Murmur3_128HashFunction(seed);
129  }
130
131  /**
132   * Returns a hash function implementing the
133   * <a href="http://smhasher.googlecode.com/svn/trunk/MurmurHash3.cpp">128-bit murmur3 algorithm,
134   * x64 variant</a> (little-endian variant), using a seed value of zero.
135   *
136   * <p>The exact C++ equivalent is the MurmurHash3_x64_128 function (Murmur3F).
137   */
138  public static HashFunction murmur3_128() {
139    return Murmur3_128Holder.MURMUR3_128;
140  }
141
142  private static class Murmur3_128Holder {
143    static final HashFunction MURMUR3_128 = new Murmur3_128HashFunction(0);
144
145    /** Returned by {@link #goodFastHash} when {@code 32 < minimumBits <= 128}. */
146    static final HashFunction GOOD_FAST_HASH_FUNCTION_128 = murmur3_128(GOOD_FAST_HASH_SEED);
147  }
148
149  /**
150   * Returns a hash function implementing the <a href="https://131002.net/siphash/">64-bit
151   * SipHash-2-4 algorithm</a> using a seed value of {@code k = 00 01 02 ...}.
152   *
153   * @since 15.0
154   */
155  public static HashFunction sipHash24() {
156    return SipHash24Holder.SIP_HASH_24;
157  }
158
159  private static class SipHash24Holder {
160    static final HashFunction SIP_HASH_24 =
161        new SipHashFunction(2, 4, 0x0706050403020100L, 0x0f0e0d0c0b0a0908L);
162  }
163
164  /**
165   * Returns a hash function implementing the <a href="https://131002.net/siphash/">64-bit
166   * SipHash-2-4 algorithm</a> using the given seed.
167   *
168   * @since 15.0
169   */
170  public static HashFunction sipHash24(long k0, long k1) {
171    return new SipHashFunction(2, 4, k0, k1);
172  }
173
174  /**
175   * Returns a hash function implementing the MD5 hash algorithm (128 hash bits) by delegating to
176   * the MD5 {@link MessageDigest}.
177   *
178   * <p><b>Warning:</b> MD5 is not cryptographically secure or collision-resistant and is not
179   * recommended for use in new code. It should be used for legacy compatibility reasons only.
180   * Please consider using a hash function in the SHA-2 family of functions (e.g., SHA-256).
181   */
182  public static HashFunction md5() {
183    return Md5Holder.MD5;
184  }
185
186  private static class Md5Holder {
187    static final HashFunction MD5 = new MessageDigestHashFunction("MD5", "Hashing.md5()");
188  }
189
190  /**
191   * Returns a hash function implementing the SHA-1 algorithm (160 hash bits) by delegating to the
192   * SHA-1 {@link MessageDigest}.
193   *
194   * <p><b>Warning:</b> SHA1 is not cryptographically secure and is not recommended for use in new
195   * code. It should be used for legacy compatibility reasons only. Please consider using a hash
196   * function in the SHA-2 family of functions (e.g., SHA-256).
197   */
198  public static HashFunction sha1() {
199    return Sha1Holder.SHA_1;
200  }
201
202  private static class Sha1Holder {
203    static final HashFunction SHA_1 = new MessageDigestHashFunction("SHA-1", "Hashing.sha1()");
204  }
205
206  /**
207   * Returns a hash function implementing the SHA-256 algorithm (256 hash bits) by delegating to the
208   * SHA-256 {@link MessageDigest}.
209   */
210  public static HashFunction sha256() {
211    return Sha256Holder.SHA_256;
212  }
213
214  private static class Sha256Holder {
215    static final HashFunction SHA_256 =
216        new MessageDigestHashFunction("SHA-256", "Hashing.sha256()");
217  }
218
219  /**
220   * Returns a hash function implementing the SHA-384 algorithm (384 hash bits) by delegating to the
221   * SHA-384 {@link MessageDigest}.
222   *
223   * @since 19.0
224   */
225  public static HashFunction sha384() {
226    return Sha384Holder.SHA_384;
227  }
228
229  private static class Sha384Holder {
230    static final HashFunction SHA_384 =
231        new MessageDigestHashFunction("SHA-384", "Hashing.sha384()");
232  }
233
234  /**
235   * Returns a hash function implementing the SHA-512 algorithm (512 hash bits) by delegating to the
236   * SHA-512 {@link MessageDigest}.
237   */
238  public static HashFunction sha512() {
239    return Sha512Holder.SHA_512;
240  }
241
242  private static class Sha512Holder {
243    static final HashFunction SHA_512 =
244        new MessageDigestHashFunction("SHA-512", "Hashing.sha512()");
245  }
246
247  /**
248   * Returns a hash function implementing the Message Authentication Code (MAC) algorithm, using the
249   * MD5 (128 hash bits) hash function and the given secret key.
250   *
251   *
252   * @param key the secret key
253   * @throws IllegalArgumentException if the given key is inappropriate for initializing this MAC
254   * @since 20.0
255   */
256  public static HashFunction hmacMd5(Key key) {
257    return new MacHashFunction("HmacMD5", key, hmacToString("hmacMd5", key));
258  }
259
260  /**
261   * Returns a hash function implementing the Message Authentication Code (MAC) algorithm, using the
262   * MD5 (128 hash bits) hash function and a {@link SecretSpecKey} created from the given byte array
263   * and the MD5 algorithm.
264   *
265   *
266   * @param key the key material of the secret key
267   * @since 20.0
268   */
269  public static HashFunction hmacMd5(byte[] key) {
270    return hmacMd5(new SecretKeySpec(checkNotNull(key), "HmacMD5"));
271  }
272
273  /**
274   * Returns a hash function implementing the Message Authentication Code (MAC) algorithm, using the
275   * SHA-1 (160 hash bits) hash function and the given secret key.
276   *
277   *
278   * @param key the secret key
279   * @throws IllegalArgumentException if the given key is inappropriate for initializing this MAC
280   * @since 20.0
281   */
282  public static HashFunction hmacSha1(Key key) {
283    return new MacHashFunction("HmacSHA1", key, hmacToString("hmacSha1", key));
284  }
285
286  /**
287   * Returns a hash function implementing the Message Authentication Code (MAC) algorithm, using the
288   * SHA-1 (160 hash bits) hash function and a {@link SecretSpecKey} created from the given byte
289   * array and the SHA-1 algorithm.
290   *
291   *
292   * @param key the key material of the secret key
293   * @since 20.0
294   */
295  public static HashFunction hmacSha1(byte[] key) {
296    return hmacSha1(new SecretKeySpec(checkNotNull(key), "HmacSHA1"));
297  }
298
299  /**
300   * Returns a hash function implementing the Message Authentication Code (MAC) algorithm, using the
301   * SHA-256 (256 hash bits) hash function and the given secret key.
302   *
303   *
304   * @param key the secret key
305   * @throws IllegalArgumentException if the given key is inappropriate for initializing this MAC
306   * @since 20.0
307   */
308  public static HashFunction hmacSha256(Key key) {
309    return new MacHashFunction("HmacSHA256", key, hmacToString("hmacSha256", key));
310  }
311
312  /**
313   * Returns a hash function implementing the Message Authentication Code (MAC) algorithm, using the
314   * SHA-256 (256 hash bits) hash function and a {@link SecretSpecKey} created from the given byte
315   * array and the SHA-256 algorithm.
316   *
317   *
318   * @param key the key material of the secret key
319   * @since 20.0
320   */
321  public static HashFunction hmacSha256(byte[] key) {
322    return hmacSha256(new SecretKeySpec(checkNotNull(key), "HmacSHA256"));
323  }
324
325  /**
326   * Returns a hash function implementing the Message Authentication Code (MAC) algorithm, using the
327   * SHA-512 (512 hash bits) hash function and the given secret key.
328   *
329   *
330   * @param key the secret key
331   * @throws IllegalArgumentException if the given key is inappropriate for initializing this MAC
332   * @since 20.0
333   */
334  public static HashFunction hmacSha512(Key key) {
335    return new MacHashFunction("HmacSHA512", key, hmacToString("hmacSha512", key));
336  }
337
338  /**
339   * Returns a hash function implementing the Message Authentication Code (MAC) algorithm, using the
340   * SHA-512 (512 hash bits) hash function and a {@link SecretSpecKey} created from the given byte
341   * array and the SHA-512 algorithm.
342   *
343   *
344   * @param key the key material of the secret key
345   * @since 20.0
346   */
347  public static HashFunction hmacSha512(byte[] key) {
348    return hmacSha512(new SecretKeySpec(checkNotNull(key), "HmacSHA512"));
349  }
350
351  private static String hmacToString(String methodName, Key key) {
352    return String.format(
353        "Hashing.%s(Key[algorithm=%s, format=%s])",
354        methodName,
355        key.getAlgorithm(),
356        key.getFormat());
357  }
358
359  /**
360   * Returns a hash function implementing the CRC32C checksum algorithm (32 hash bits) as described
361   * by RFC 3720, Section 12.1.
362   *
363   * @since 18.0
364   */
365  public static HashFunction crc32c() {
366    return Crc32cHolder.CRC_32_C;
367  }
368
369  private static final class Crc32cHolder {
370    static final HashFunction CRC_32_C = new Crc32cHashFunction();
371  }
372
373  /**
374   * Returns a hash function implementing the CRC-32 checksum algorithm (32 hash bits) by delegating
375   * to the {@link CRC32} {@link Checksum}.
376   *
377   * <p>To get the {@code long} value equivalent to {@link Checksum#getValue()} for a
378   * {@code HashCode} produced by this function, use {@link HashCode#padToLong()}.
379   *
380   * @since 14.0
381   */
382  public static HashFunction crc32() {
383    return Crc32Holder.CRC_32;
384  }
385
386  private static class Crc32Holder {
387    static final HashFunction CRC_32 = checksumHashFunction(ChecksumType.CRC_32, "Hashing.crc32()");
388  }
389
390  /**
391   * Returns a hash function implementing the Adler-32 checksum algorithm (32 hash bits) by
392   * delegating to the {@link Adler32} {@link Checksum}.
393   *
394   * <p>To get the {@code long} value equivalent to {@link Checksum#getValue()} for a
395   * {@code HashCode} produced by this function, use {@link HashCode#padToLong()}.
396   *
397   * @since 14.0
398   */
399  public static HashFunction adler32() {
400    return Adler32Holder.ADLER_32;
401  }
402
403  private static class Adler32Holder {
404    static final HashFunction ADLER_32 =
405        checksumHashFunction(ChecksumType.ADLER_32, "Hashing.adler32()");
406  }
407
408  private static HashFunction checksumHashFunction(ChecksumType type, String toString) {
409    return new ChecksumHashFunction(type, type.bits, toString);
410  }
411
412  enum ChecksumType implements Supplier<Checksum> {
413    CRC_32(32) {
414      @Override
415      public Checksum get() {
416        return new CRC32();
417      }
418    },
419    ADLER_32(32) {
420      @Override
421      public Checksum get() {
422        return new Adler32();
423      }
424    };
425
426    private final int bits;
427
428    ChecksumType(int bits) {
429      this.bits = bits;
430    }
431
432    @Override
433    public abstract Checksum get();
434  }
435
436  /**
437   * Returns a hash function implementing FarmHash's Fingerprint64, an open-source algorithm.
438   *
439   * <p>This is designed for generating persistent fingerprints of strings. It isn't
440   * cryptographically secure, but it produces a high-quality hash with fewer collisions than some
441   * alternatives we've used in the past. FarmHashFingerprints generated using this are byte-wise
442   * identical to those created using the C++ version, but note that this uses unsigned integers
443   * (see {@link com.google.common.primitives.UnsignedInts}). Comparisons between the two should
444   * take this into account.
445   *
446   * @since 20.0
447   */
448  public static HashFunction farmHashFingerprint64() {
449    return FarmHashFingerprint64Holder.FARMHASH_FINGERPRINT_64;
450  }
451
452  private static class FarmHashFingerprint64Holder {
453    static final HashFunction FARMHASH_FINGERPRINT_64 = new FarmHashFingerprint64();
454  }
455
456  /**
457   * Assigns to {@code hashCode} a "bucket" in the range {@code [0, buckets)}, in a uniform manner
458   * that minimizes the need for remapping as {@code buckets} grows. That is, {@code
459   * consistentHash(h, n)} equals:
460   *
461   * <ul>
462   * <li>{@code n - 1}, with approximate probability {@code 1/n}
463   * <li>{@code consistentHash(h, n - 1)}, otherwise (probability {@code 1 - 1/n})
464   * </ul>
465   *
466   * <p>This method is suitable for the common use case of dividing work among buckets that meet the
467   * following conditions:
468   *
469   * <ul>
470   * <li>You want to assign the same fraction of inputs to each bucket.
471   * <li>When you reduce the number of buckets, you can accept that the most recently added buckets
472   * will be removed first. More concretely, if you are dividing traffic among tasks, you can
473   * decrease the number of tasks from 15 and 10, killing off the final 5 tasks, and {@code
474   * consistentHash} will handle it. If, however, you are dividing traffic among servers {@code
475   * alpha}, {@code bravo}, and {@code charlie} and you occasionally need to take each of the
476   * servers offline, {@code consistentHash} will be a poor fit: It provides no way for you to
477   * specify which of the three buckets is disappearing. Thus, if your buckets change from {@code
478   * [alpha, bravo, charlie]} to {@code [bravo, charlie]}, it will assign all the old {@code alpha}
479   * traffic to {@code bravo} and all the old {@code bravo} traffic to {@code charlie}, rather than
480   * letting {@code bravo} keep its traffic.
481   * </ul>
482   *
483   *
484   * <p>See the <a href="http://en.wikipedia.org/wiki/Consistent_hashing">Wikipedia article on
485   * consistent hashing</a> for more information.
486   */
487  public static int consistentHash(HashCode hashCode, int buckets) {
488    return consistentHash(hashCode.padToLong(), buckets);
489  }
490
491  /**
492   * Assigns to {@code input} a "bucket" in the range {@code [0, buckets)}, in a uniform manner that
493   * minimizes the need for remapping as {@code buckets} grows. That is, {@code consistentHash(h,
494   * n)} equals:
495   *
496   * <ul>
497   * <li>{@code n - 1}, with approximate probability {@code 1/n}
498   * <li>{@code consistentHash(h, n - 1)}, otherwise (probability {@code 1 - 1/n})
499   * </ul>
500   *
501   * <p>This method is suitable for the common use case of dividing work among buckets that meet the
502   * following conditions:
503   *
504   * <ul>
505   * <li>You want to assign the same fraction of inputs to each bucket.
506   * <li>When you reduce the number of buckets, you can accept that the most recently added buckets
507   * will be removed first. More concretely, if you are dividing traffic among tasks, you can
508   * decrease the number of tasks from 15 and 10, killing off the final 5 tasks, and {@code
509   * consistentHash} will handle it. If, however, you are dividing traffic among servers {@code
510   * alpha}, {@code bravo}, and {@code charlie} and you occasionally need to take each of the
511   * servers offline, {@code consistentHash} will be a poor fit: It provides no way for you to
512   * specify which of the three buckets is disappearing. Thus, if your buckets change from {@code
513   * [alpha, bravo, charlie]} to {@code [bravo, charlie]}, it will assign all the old {@code alpha}
514   * traffic to {@code bravo} and all the old {@code bravo} traffic to {@code charlie}, rather than
515   * letting {@code bravo} keep its traffic.
516   * </ul>
517   *
518   *
519   * <p>See the <a href="http://en.wikipedia.org/wiki/Consistent_hashing">Wikipedia article on
520   * consistent hashing</a> for more information.
521   */
522  public static int consistentHash(long input, int buckets) {
523    checkArgument(buckets > 0, "buckets must be positive: %s", buckets);
524    LinearCongruentialGenerator generator = new LinearCongruentialGenerator(input);
525    int candidate = 0;
526    int next;
527
528    // Jump from bucket to bucket until we go out of range
529    while (true) {
530      next = (int) ((candidate + 1) / generator.nextDouble());
531      if (next >= 0 && next < buckets) {
532        candidate = next;
533      } else {
534        return candidate;
535      }
536    }
537  }
538
539  /**
540   * Returns a hash code, having the same bit length as each of the input hash codes, that combines
541   * the information of these hash codes in an ordered fashion. That is, whenever two equal hash
542   * codes are produced by two calls to this method, it is <i>as likely as possible</i> that each
543   * was computed from the <i>same</i> input hash codes in the <i>same</i> order.
544   *
545   * @throws IllegalArgumentException if {@code hashCodes} is empty, or the hash codes do not all
546   *     have the same bit length
547   */
548  public static HashCode combineOrdered(Iterable<HashCode> hashCodes) {
549    Iterator<HashCode> iterator = hashCodes.iterator();
550    checkArgument(iterator.hasNext(), "Must be at least 1 hash code to combine.");
551    int bits = iterator.next().bits();
552    byte[] resultBytes = new byte[bits / 8];
553    for (HashCode hashCode : hashCodes) {
554      byte[] nextBytes = hashCode.asBytes();
555      checkArgument(
556          nextBytes.length == resultBytes.length, "All hashcodes must have the same bit length.");
557      for (int i = 0; i < nextBytes.length; i++) {
558        resultBytes[i] = (byte) (resultBytes[i] * 37 ^ nextBytes[i]);
559      }
560    }
561    return HashCode.fromBytesNoCopy(resultBytes);
562  }
563
564  /**
565   * Returns a hash code, having the same bit length as each of the input hash codes, that combines
566   * the information of these hash codes in an unordered fashion. That is, whenever two equal hash
567   * codes are produced by two calls to this method, it is <i>as likely as possible</i> that each
568   * was computed from the <i>same</i> input hash codes in <i>some</i> order.
569   *
570   * @throws IllegalArgumentException if {@code hashCodes} is empty, or the hash codes do not all
571   *     have the same bit length
572   */
573  public static HashCode combineUnordered(Iterable<HashCode> hashCodes) {
574    Iterator<HashCode> iterator = hashCodes.iterator();
575    checkArgument(iterator.hasNext(), "Must be at least 1 hash code to combine.");
576    byte[] resultBytes = new byte[iterator.next().bits() / 8];
577    for (HashCode hashCode : hashCodes) {
578      byte[] nextBytes = hashCode.asBytes();
579      checkArgument(
580          nextBytes.length == resultBytes.length, "All hashcodes must have the same bit length.");
581      for (int i = 0; i < nextBytes.length; i++) {
582        resultBytes[i] += nextBytes[i];
583      }
584    }
585    return HashCode.fromBytesNoCopy(resultBytes);
586  }
587
588  /**
589   * Checks that the passed argument is positive, and ceils it to a multiple of 32.
590   */
591  static int checkPositiveAndMakeMultipleOf32(int bits) {
592    checkArgument(bits > 0, "Number of bits must be positive");
593    return (bits + 31) & ~31;
594  }
595
596  /**
597   * Returns a hash function which computes its hash code by concatenating the hash codes of the
598   * underlying hash functions together. This can be useful if you need to generate hash codes of a
599   * specific length.
600   *
601   * <p>For example, if you need 1024-bit hash codes, you could join two {@link Hashing#sha512} hash
602   * functions together: {@code Hashing.concatenating(Hashing.sha512(), Hashing.sha512())}.
603   *
604   * @since 19.0
605   */
606  public static HashFunction concatenating(
607      HashFunction first, HashFunction second, HashFunction... rest) {
608    // We can't use Lists.asList() here because there's no hash->collect dependency
609    List<HashFunction> list = new ArrayList<HashFunction>();
610    list.add(first);
611    list.add(second);
612    for (HashFunction hashFunc : rest) {
613      list.add(hashFunc);
614    }
615    return new ConcatenatedHashFunction(list.toArray(new HashFunction[0]));
616  }
617
618  /**
619   * Returns a hash function which computes its hash code by concatenating the hash codes of the
620   * underlying hash functions together. This can be useful if you need to generate hash codes of a
621   * specific length.
622   *
623   * <p>For example, if you need 1024-bit hash codes, you could join two {@link Hashing#sha512} hash
624   * functions together: {@code Hashing.concatenating(Hashing.sha512(), Hashing.sha512())}.
625   *
626   * @since 19.0
627   */
628  public static HashFunction concatenating(Iterable<HashFunction> hashFunctions) {
629    checkNotNull(hashFunctions);
630    // We can't use Iterables.toArray() here because there's no hash->collect dependency
631    List<HashFunction> list = new ArrayList<HashFunction>();
632    for (HashFunction hashFunction : hashFunctions) {
633      list.add(hashFunction);
634    }
635    checkArgument(list.size() > 0, "number of hash functions (%s) must be > 0", list.size());
636    return new ConcatenatedHashFunction(list.toArray(new HashFunction[0]));
637  }
638
639  private static final class ConcatenatedHashFunction extends AbstractCompositeHashFunction {
640    private final int bits;
641
642    private ConcatenatedHashFunction(HashFunction... functions) {
643      super(functions);
644      int bitSum = 0;
645      for (HashFunction function : functions) {
646        bitSum += function.bits();
647        checkArgument(
648            function.bits() % 8 == 0,
649            "the number of bits (%s) in hashFunction (%s) must be divisible by 8",
650            function.bits(),
651            function);
652      }
653      this.bits = bitSum;
654    }
655
656    @Override
657    HashCode makeHash(Hasher[] hashers) {
658      byte[] bytes = new byte[bits / 8];
659      int i = 0;
660      for (Hasher hasher : hashers) {
661        HashCode newHash = hasher.hash();
662        i += newHash.writeBytesTo(bytes, i, newHash.bits() / 8);
663      }
664      return HashCode.fromBytesNoCopy(bytes);
665    }
666
667    @Override
668    public int bits() {
669      return bits;
670    }
671
672    @Override
673    public boolean equals(@Nullable Object object) {
674      if (object instanceof ConcatenatedHashFunction) {
675        ConcatenatedHashFunction other = (ConcatenatedHashFunction) object;
676        return Arrays.equals(functions, other.functions);
677      }
678      return false;
679    }
680
681    @Override
682    public int hashCode() {
683      return Arrays.hashCode(functions) * 31 + bits;
684    }
685  }
686
687  /**
688   * Linear CongruentialGenerator to use for consistent hashing. See
689   * http://en.wikipedia.org/wiki/Linear_congruential_generator
690   */
691  private static final class LinearCongruentialGenerator {
692    private long state;
693
694    public LinearCongruentialGenerator(long seed) {
695      this.state = seed;
696    }
697
698    public double nextDouble() {
699      state = 2862933555777941757L * state + 1;
700      return ((double) ((int) (state >>> 33) + 1)) / (0x1.0p31);
701    }
702  }
703
704  private Hashing() {}
705}