1 /*
2 * Copyright (C) 2011 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5 * in compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the License
10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11 * or implied. See the License for the specific language governing permissions and limitations under
12 * the License.
13 */
14
15 package com.google.common.hash;
16
17 import static com.google.common.base.Preconditions.checkArgument;
18 import static com.google.common.base.Preconditions.checkNotNull;
19
20 import com.google.common.annotations.Beta;
21 import com.google.errorprone.annotations.Immutable;
22 import java.security.Key;
23 import java.util.ArrayList;
24 import java.util.Arrays;
25 import java.util.Iterator;
26 import java.util.List;
27 import java.util.zip.Adler32;
28 import java.util.zip.CRC32;
29 import java.util.zip.Checksum;
30 import javax.annotation.CheckForNull;
31 import javax.crypto.spec.SecretKeySpec;
32
33 /**
34 * Static methods to obtain {@link HashFunction} instances, and other static hashing-related
35 * utilities.
36 *
37 * <p>A comparison of the various hash functions can be found <a
38 * href="http://goo.gl/jS7HH">here</a>.
39 *
40 * @author Kevin Bourrillion
41 * @author Dimitris Andreou
42 * @author Kurt Alfred Kluever
43 * @since 11.0
44 */
45 @Beta
46 @ElementTypesAreNonnullByDefault
47 public final class Hashing {
48 /**
49 * Returns a general-purpose, <b>temporary-use</b>, non-cryptographic hash function. The algorithm
50 * the returned function implements is unspecified and subject to change without notice.
51 *
52 * <p><b>Warning:</b> a new random seed for these functions is chosen each time the {@code
53 * Hashing} class is loaded. <b>Do not use this method</b> if hash codes may escape the current
54 * process in any way, for example being sent over RPC, or saved to disk. For a general-purpose,
55 * non-cryptographic hash function that will never change behavior, we suggest {@link
56 * #murmur3_128}.
57 *
58 * <p>Repeated calls to this method on the same loaded {@code Hashing} class, using the same value
59 * for {@code minimumBits}, will return identically-behaving {@link HashFunction} instances.
60 *
61 * @param minimumBits a positive integer (can be arbitrarily large)
62 * @return a hash function, described above, that produces hash codes of length {@code
63 * minimumBits} or greater
64 */
65 public static HashFunction goodFastHash(int minimumBits) {
66 int bits = checkPositiveAndMakeMultipleOf32(minimumBits);
67
68 if (bits == 32) {
69 return Murmur3_32HashFunction.GOOD_FAST_HASH_32;
70 }
71 if (bits <= 128) {
72 return Murmur3_128HashFunction.GOOD_FAST_HASH_128;
73 }
74
75 // Otherwise, join together some 128-bit murmur3s
76 int hashFunctionsNeeded = (bits + 127) / 128;
77 HashFunction[] hashFunctions = new HashFunction[hashFunctionsNeeded];
78 hashFunctions[0] = Murmur3_128HashFunction.GOOD_FAST_HASH_128;
79 int seed = GOOD_FAST_HASH_SEED;
80 for (int i = 1; i < hashFunctionsNeeded; i++) {
81 seed += 1500450271; // a prime; shouldn't matter
82 hashFunctions[i] = murmur3_128(seed);
83 }
84 return new ConcatenatedHashFunction(hashFunctions);
85 }
86
87 /**
88 * Used to randomize {@link #goodFastHash} instances, so that programs which persist anything
89 * dependent on the hash codes they produce will fail sooner.
90 */
91 @SuppressWarnings("GoodTime") // reading system time without TimeSource
92 static final int GOOD_FAST_HASH_SEED = (int) System.currentTimeMillis();
93
94 /**
95 * Returns a hash function implementing the <a
96 * href="https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp">32-bit murmur3
97 * algorithm, x86 variant</a> (little-endian variant), using the given seed value.
98 *
99 * <p>The exact C++ equivalent is the MurmurHash3_x86_32 function (Murmur3A).
100 */
101 public static HashFunction murmur3_32(int seed) {
102 return new Murmur3_32HashFunction(seed);
103 }
104
105 /**
106 * Returns a hash function implementing the <a
107 * href="https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp">32-bit murmur3
108 * algorithm, x86 variant</a> (little-endian variant), using a seed value of zero.
109 *
110 * <p>The exact C++ equivalent is the MurmurHash3_x86_32 function (Murmur3A).
111 */
112 public static HashFunction murmur3_32() {
113 return Murmur3_32HashFunction.MURMUR3_32;
114 }
115
116 /**
117 * Returns a hash function implementing the <a
118 * href="https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp">128-bit murmur3
119 * algorithm, x64 variant</a> (little-endian variant), using the given seed value.
120 *
121 * <p>The exact C++ equivalent is the MurmurHash3_x64_128 function (Murmur3F).
122 */
123 public static HashFunction murmur3_128(int seed) {
124 return new Murmur3_128HashFunction(seed);
125 }
126
127 /**
128 * Returns a hash function implementing the <a
129 * href="https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp">128-bit murmur3
130 * algorithm, x64 variant</a> (little-endian variant), using a seed value of zero.
131 *
132 * <p>The exact C++ equivalent is the MurmurHash3_x64_128 function (Murmur3F).
133 */
134 public static HashFunction murmur3_128() {
135 return Murmur3_128HashFunction.MURMUR3_128;
136 }
137
138 /**
139 * Returns a hash function implementing the <a href="https://131002.net/siphash/">64-bit
140 * SipHash-2-4 algorithm</a> using a seed value of {@code k = 00 01 02 ...}.
141 *
142 * @since 15.0
143 */
144 public static HashFunction sipHash24() {
145 return SipHashFunction.SIP_HASH_24;
146 }
147
148 /**
149 * Returns a hash function implementing the <a href="https://131002.net/siphash/">64-bit
150 * SipHash-2-4 algorithm</a> using the given seed.
151 *
152 * @since 15.0
153 */
154 public static HashFunction sipHash24(long k0, long k1) {
155 return new SipHashFunction(2, 4, k0, k1);
156 }
157
158 /**
159 * Returns a hash function implementing the MD5 hash algorithm (128 hash bits).
160 *
161 * @deprecated If you must interoperate with a system that requires MD5, then use this method,
162 * despite its deprecation. But if you can choose your hash function, avoid MD5, which is
163 * neither fast nor secure. As of January 2017, we suggest:
164 * <ul>
165 * <li>For security:
166 * {@link Hashing#sha256} or a higher-level API.
167 * <li>For speed: {@link Hashing#goodFastHash}, though see its docs for caveats.
168 * </ul>
169 */
170 @Deprecated
171 public static HashFunction md5() {
172 return Md5Holder.MD5;
173 }
174
175 private static class Md5Holder {
176 static final HashFunction MD5 = new MessageDigestHashFunction("MD5", "Hashing.md5()");
177 }
178
179 /**
180 * Returns a hash function implementing the SHA-1 algorithm (160 hash bits).
181 *
182 * @deprecated If you must interoperate with a system that requires SHA-1, then use this method,
183 * despite its deprecation. But if you can choose your hash function, avoid SHA-1, which is
184 * neither fast nor secure. As of January 2017, we suggest:
185 * <ul>
186 * <li>For security:
187 * {@link Hashing#sha256} or a higher-level API.
188 * <li>For speed: {@link Hashing#goodFastHash}, though see its docs for caveats.
189 * </ul>
190 */
191 @Deprecated
192 public static HashFunction sha1() {
193 return Sha1Holder.SHA_1;
194 }
195
196 private static class Sha1Holder {
197 static final HashFunction SHA_1 = new MessageDigestHashFunction("SHA-1", "Hashing.sha1()");
198 }
199
200 /** Returns a hash function implementing the SHA-256 algorithm (256 hash bits). */
201 public static HashFunction sha256() {
202 return Sha256Holder.SHA_256;
203 }
204
205 private static class Sha256Holder {
206 static final HashFunction SHA_256 =
207 new MessageDigestHashFunction("SHA-256", "Hashing.sha256()");
208 }
209
210 /**
211 * Returns a hash function implementing the SHA-384 algorithm (384 hash bits).
212 *
213 * @since 19.0
214 */
215 public static HashFunction sha384() {
216 return Sha384Holder.SHA_384;
217 }
218
219 private static class Sha384Holder {
220 static final HashFunction SHA_384 =
221 new MessageDigestHashFunction("SHA-384", "Hashing.sha384()");
222 }
223
224 /** Returns a hash function implementing the SHA-512 algorithm (512 hash bits). */
225 public static HashFunction sha512() {
226 return Sha512Holder.SHA_512;
227 }
228
229 private static class Sha512Holder {
230 static final HashFunction SHA_512 =
231 new MessageDigestHashFunction("SHA-512", "Hashing.sha512()");
232 }
233
234 /**
235 * Returns a hash function implementing the Message Authentication Code (MAC) algorithm, using the
236 * MD5 (128 hash bits) hash function and the given secret key.
237 *
238 * @param key the secret key
239 * @throws IllegalArgumentException if the given key is inappropriate for initializing this MAC
240 * @since 20.0
241 */
242 public static HashFunction hmacMd5(Key key) {
243 return new MacHashFunction("HmacMD5", key, hmacToString("hmacMd5", key));
244 }
245
246 /**
247 * Returns a hash function implementing the Message Authentication Code (MAC) algorithm, using the
248 * MD5 (128 hash bits) hash function and a {@link SecretKeySpec} created from the given byte array
249 * and the MD5 algorithm.
250 *
251 * @param key the key material of the secret key
252 * @since 20.0
253 */
254 public static HashFunction hmacMd5(byte[] key) {
255 return hmacMd5(new SecretKeySpec(checkNotNull(key), "HmacMD5"));
256 }
257
258 /**
259 * Returns a hash function implementing the Message Authentication Code (MAC) algorithm, using the
260 * SHA-1 (160 hash bits) hash function and the given secret key.
261 *
262 * @param key the secret key
263 * @throws IllegalArgumentException if the given key is inappropriate for initializing this MAC
264 * @since 20.0
265 */
266 public static HashFunction hmacSha1(Key key) {
267 return new MacHashFunction("HmacSHA1", key, hmacToString("hmacSha1", key));
268 }
269
270 /**
271 * Returns a hash function implementing the Message Authentication Code (MAC) algorithm, using the
272 * SHA-1 (160 hash bits) hash function and a {@link SecretKeySpec} created from the given byte
273 * array and the SHA-1 algorithm.
274 *
275 * @param key the key material of the secret key
276 * @since 20.0
277 */
278 public static HashFunction hmacSha1(byte[] key) {
279 return hmacSha1(new SecretKeySpec(checkNotNull(key), "HmacSHA1"));
280 }
281
282 /**
283 * Returns a hash function implementing the Message Authentication Code (MAC) algorithm, using the
284 * SHA-256 (256 hash bits) hash function and the given secret key.
285 *
286 * @param key the secret key
287 * @throws IllegalArgumentException if the given key is inappropriate for initializing this MAC
288 * @since 20.0
289 */
290 public static HashFunction hmacSha256(Key key) {
291 return new MacHashFunction("HmacSHA256", key, hmacToString("hmacSha256", key));
292 }
293
294 /**
295 * Returns a hash function implementing the Message Authentication Code (MAC) algorithm, using the
296 * SHA-256 (256 hash bits) hash function and a {@link SecretKeySpec} created from the given byte
297 * array and the SHA-256 algorithm.
298 *
299 * @param key the key material of the secret key
300 * @since 20.0
301 */
302 public static HashFunction hmacSha256(byte[] key) {
303 return hmacSha256(new SecretKeySpec(checkNotNull(key), "HmacSHA256"));
304 }
305
306 /**
307 * Returns a hash function implementing the Message Authentication Code (MAC) algorithm, using the
308 * SHA-512 (512 hash bits) hash function and the given secret key.
309 *
310 * @param key the secret key
311 * @throws IllegalArgumentException if the given key is inappropriate for initializing this MAC
312 * @since 20.0
313 */
314 public static HashFunction hmacSha512(Key key) {
315 return new MacHashFunction("HmacSHA512", key, hmacToString("hmacSha512", key));
316 }
317
318 /**
319 * Returns a hash function implementing the Message Authentication Code (MAC) algorithm, using the
320 * SHA-512 (512 hash bits) hash function and a {@link SecretKeySpec} created from the given byte
321 * array and the SHA-512 algorithm.
322 *
323 * @param key the key material of the secret key
324 * @since 20.0
325 */
326 public static HashFunction hmacSha512(byte[] key) {
327 return hmacSha512(new SecretKeySpec(checkNotNull(key), "HmacSHA512"));
328 }
329
330 private static String hmacToString(String methodName, Key key) {
331 return String.format(
332 "Hashing.%s(Key[algorithm=%s, format=%s])",
333 methodName, key.getAlgorithm(), key.getFormat());
334 }
335
336 /**
337 * Returns a hash function implementing the CRC32C checksum algorithm (32 hash bits) as described
338 * by RFC 3720, Section 12.1.
339 *
340 * <p>This function is best understood as a <a
341 * href="https://en.wikipedia.org/wiki/Checksum">checksum</a> rather than a true <a
342 * href="https://en.wikipedia.org/wiki/Hash_function">hash function</a>.
343 *
344 * @since 18.0
345 */
346 public static HashFunction crc32c() {
347 return Crc32cHashFunction.CRC_32_C;
348 }
349
350 /**
351 * Returns a hash function implementing the CRC-32 checksum algorithm (32 hash bits).
352 *
353 * <p>To get the {@code long} value equivalent to {@link Checksum#getValue()} for a {@code
354 * HashCode} produced by this function, use {@link HashCode#padToLong()}.
355 *
356 * <p>This function is best understood as a <a
357 * href="https://en.wikipedia.org/wiki/Checksum">checksum</a> rather than a true <a
358 * href="https://en.wikipedia.org/wiki/Hash_function">hash function</a>.
359 *
360 * @since 14.0
361 */
362 public static HashFunction crc32() {
363 return ChecksumType.CRC_32.hashFunction;
364 }
365
366 /**
367 * Returns a hash function implementing the Adler-32 checksum algorithm (32 hash bits).
368 *
369 * <p>To get the {@code long} value equivalent to {@link Checksum#getValue()} for a {@code
370 * HashCode} produced by this function, use {@link HashCode#padToLong()}.
371 *
372 * <p>This function is best understood as a <a
373 * href="https://en.wikipedia.org/wiki/Checksum">checksum</a> rather than a true <a
374 * href="https://en.wikipedia.org/wiki/Hash_function">hash function</a>.
375 *
376 * @since 14.0
377 */
378 public static HashFunction adler32() {
379 return ChecksumType.ADLER_32.hashFunction;
380 }
381
382 @Immutable
383 enum ChecksumType implements ImmutableSupplier<Checksum> {
384 CRC_32("Hashing.crc32()") {
385 @Override
386 public Checksum get() {
387 return new CRC32();
388 }
389 },
390 ADLER_32("Hashing.adler32()") {
391 @Override
392 public Checksum get() {
393 return new Adler32();
394 }
395 };
396
397 public final HashFunction hashFunction;
398
399 ChecksumType(String toString) {
400 this.hashFunction = new ChecksumHashFunction(this, 32, toString);
401 }
402 }
403
404 /**
405 * Returns a hash function implementing FarmHash's Fingerprint64, an open-source algorithm.
406 *
407 * <p>This is designed for generating persistent fingerprints of strings. It isn't
408 * cryptographically secure, but it produces a high-quality hash with fewer collisions than some
409 * alternatives we've used in the past.
410 *
411 * <p>FarmHash fingerprints are encoded by {@link HashCode#asBytes} in little-endian order. This
412 * means {@link HashCode#asLong} is guaranteed to return the same value that
413 * farmhash::Fingerprint64() would for the same input (when compared using {@link
414 * com.google.common.primitives.UnsignedLongs}'s encoding of 64-bit unsigned numbers).
415 *
416 * <p>This function is best understood as a <a
417 * href="https://en.wikipedia.org/wiki/Fingerprint_(computing)">fingerprint</a> rather than a true
418 * <a href="https://en.wikipedia.org/wiki/Hash_function">hash function</a>.
419 *
420 * @since 20.0
421 */
422 public static HashFunction farmHashFingerprint64() {
423 return FarmHashFingerprint64.FARMHASH_FINGERPRINT_64;
424 }
425
426 /**
427 * Assigns to {@code hashCode} a "bucket" in the range {@code [0, buckets)}, in a uniform manner
428 * that minimizes the need for remapping as {@code buckets} grows. That is, {@code
429 * consistentHash(h, n)} equals:
430 *
431 * <ul>
432 * <li>{@code n - 1}, with approximate probability {@code 1/n}
433 * <li>{@code consistentHash(h, n - 1)}, otherwise (probability {@code 1 - 1/n})
434 * </ul>
435 *
436 * <p>This method is suitable for the common use case of dividing work among buckets that meet the
437 * following conditions:
438 *
439 * <ul>
440 * <li>You want to assign the same fraction of inputs to each bucket.
441 * <li>When you reduce the number of buckets, you can accept that the most recently added
442 * buckets will be removed first. More concretely, if you are dividing traffic among tasks,
443 * you can decrease the number of tasks from 15 and 10, killing off the final 5 tasks, and
444 * {@code consistentHash} will handle it. If, however, you are dividing traffic among
445 * servers {@code alpha}, {@code bravo}, and {@code charlie} and you occasionally need to
446 * take each of the servers offline, {@code consistentHash} will be a poor fit: It provides
447 * no way for you to specify which of the three buckets is disappearing. Thus, if your
448 * buckets change from {@code [alpha, bravo, charlie]} to {@code [bravo, charlie]}, it will
449 * assign all the old {@code alpha} traffic to {@code bravo} and all the old {@code bravo}
450 * traffic to {@code charlie}, rather than letting {@code bravo} keep its traffic.
451 * </ul>
452 *
453 * <p>See the <a href="http://en.wikipedia.org/wiki/Consistent_hashing">Wikipedia article on
454 * consistent hashing</a> for more information.
455 */
456 public static int consistentHash(HashCode hashCode, int buckets) {
457 return consistentHash(hashCode.padToLong(), buckets);
458 }
459
460 /**
461 * Assigns to {@code input} a "bucket" in the range {@code [0, buckets)}, in a uniform manner that
462 * minimizes the need for remapping as {@code buckets} grows. That is, {@code consistentHash(h,
463 * n)} equals:
464 *
465 * <ul>
466 * <li>{@code n - 1}, with approximate probability {@code 1/n}
467 * <li>{@code consistentHash(h, n - 1)}, otherwise (probability {@code 1 - 1/n})
468 * </ul>
469 *
470 * <p>This method is suitable for the common use case of dividing work among buckets that meet the
471 * following conditions:
472 *
473 * <ul>
474 * <li>You want to assign the same fraction of inputs to each bucket.
475 * <li>When you reduce the number of buckets, you can accept that the most recently added
476 * buckets will be removed first. More concretely, if you are dividing traffic among tasks,
477 * you can decrease the number of tasks from 15 and 10, killing off the final 5 tasks, and
478 * {@code consistentHash} will handle it. If, however, you are dividing traffic among
479 * servers {@code alpha}, {@code bravo}, and {@code charlie} and you occasionally need to
480 * take each of the servers offline, {@code consistentHash} will be a poor fit: It provides
481 * no way for you to specify which of the three buckets is disappearing. Thus, if your
482 * buckets change from {@code [alpha, bravo, charlie]} to {@code [bravo, charlie]}, it will
483 * assign all the old {@code alpha} traffic to {@code bravo} and all the old {@code bravo}
484 * traffic to {@code charlie}, rather than letting {@code bravo} keep its traffic.
485 * </ul>
486 *
487 * <p>See the <a href="http://en.wikipedia.org/wiki/Consistent_hashing">Wikipedia article on
488 * consistent hashing</a> for more information.
489 */
490 public static int consistentHash(long input, int buckets) {
491 checkArgument(buckets > 0, "buckets must be positive: %s", buckets);
492 LinearCongruentialGenerator generator = new LinearCongruentialGenerator(input);
493 int candidate = 0;
494 int next;
495
496 // Jump from bucket to bucket until we go out of range
497 while (true) {
498 next = (int) ((candidate + 1) / generator.nextDouble());
499 if (next >= 0 && next < buckets) {
500 candidate = next;
501 } else {
502 return candidate;
503 }
504 }
505 }
506
507 /**
508 * Returns a hash code, having the same bit length as each of the input hash codes, that combines
509 * the information of these hash codes in an ordered fashion. That is, whenever two equal hash
510 * codes are produced by two calls to this method, it is <i>as likely as possible</i> that each
511 * was computed from the <i>same</i> input hash codes in the <i>same</i> order.
512 *
513 * @throws IllegalArgumentException if {@code hashCodes} is empty, or the hash codes do not all
514 * have the same bit length
515 */
516 public static HashCode combineOrdered(Iterable<HashCode> hashCodes) {
517 Iterator<HashCode> iterator = hashCodes.iterator();
518 checkArgument(iterator.hasNext(), "Must be at least 1 hash code to combine.");
519 int bits = iterator.next().bits();
520 byte[] resultBytes = new byte[bits / 8];
521 for (HashCode hashCode : hashCodes) {
522 byte[] nextBytes = hashCode.asBytes();
523 checkArgument(
524 nextBytes.length == resultBytes.length, "All hashcodes must have the same bit length.");
525 for (int i = 0; i < nextBytes.length; i++) {
526 resultBytes[i] = (byte) (resultBytes[i] * 37 ^ nextBytes[i]);
527 }
528 }
529 return HashCode.fromBytesNoCopy(resultBytes);
530 }
531
532 /**
533 * Returns a hash code, having the same bit length as each of the input hash codes, that combines
534 * the information of these hash codes in an unordered fashion. That is, whenever two equal hash
535 * codes are produced by two calls to this method, it is <i>as likely as possible</i> that each
536 * was computed from the <i>same</i> input hash codes in <i>some</i> order.
537 *
538 * @throws IllegalArgumentException if {@code hashCodes} is empty, or the hash codes do not all
539 * have the same bit length
540 */
541 public static HashCode combineUnordered(Iterable<HashCode> hashCodes) {
542 Iterator<HashCode> iterator = hashCodes.iterator();
543 checkArgument(iterator.hasNext(), "Must be at least 1 hash code to combine.");
544 byte[] resultBytes = new byte[iterator.next().bits() / 8];
545 for (HashCode hashCode : hashCodes) {
546 byte[] nextBytes = hashCode.asBytes();
547 checkArgument(
548 nextBytes.length == resultBytes.length, "All hashcodes must have the same bit length.");
549 for (int i = 0; i < nextBytes.length; i++) {
550 resultBytes[i] += nextBytes[i];
551 }
552 }
553 return HashCode.fromBytesNoCopy(resultBytes);
554 }
555
556 /** Checks that the passed argument is positive, and ceils it to a multiple of 32. */
557 static int checkPositiveAndMakeMultipleOf32(int bits) {
558 checkArgument(bits > 0, "Number of bits must be positive");
559 return (bits + 31) & ~31;
560 }
561
562 /**
563 * Returns a hash function which computes its hash code by concatenating the hash codes of the
564 * underlying hash functions together. This can be useful if you need to generate hash codes of a
565 * specific length.
566 *
567 * <p>For example, if you need 1024-bit hash codes, you could join two {@link Hashing#sha512} hash
568 * functions together: {@code Hashing.concatenating(Hashing.sha512(), Hashing.sha512())}.
569 *
570 * @since 19.0
571 */
572 public static HashFunction concatenating(
573 HashFunction first, HashFunction second, HashFunction... rest) {
574 // We can't use Lists.asList() here because there's no hash->collect dependency
575 List<HashFunction> list = new ArrayList<>();
576 list.add(first);
577 list.add(second);
578 list.addAll(Arrays.asList(rest));
579 return new ConcatenatedHashFunction(list.toArray(new HashFunction[0]));
580 }
581
582 /**
583 * Returns a hash function which computes its hash code by concatenating the hash codes of the
584 * underlying hash functions together. This can be useful if you need to generate hash codes of a
585 * specific length.
586 *
587 * <p>For example, if you need 1024-bit hash codes, you could join two {@link Hashing#sha512} hash
588 * functions together: {@code Hashing.concatenating(Hashing.sha512(), Hashing.sha512())}.
589 *
590 * @since 19.0
591 */
592 public static HashFunction concatenating(Iterable<HashFunction> hashFunctions) {
593 checkNotNull(hashFunctions);
594 // We can't use Iterables.toArray() here because there's no hash->collect dependency
595 List<HashFunction> list = new ArrayList<>();
596 for (HashFunction hashFunction : hashFunctions) {
597 list.add(hashFunction);
598 }
599 checkArgument(list.size() > 0, "number of hash functions (%s) must be > 0", list.size());
600 return new ConcatenatedHashFunction(list.toArray(new HashFunction[0]));
601 }
602
603 private static final class ConcatenatedHashFunction extends AbstractCompositeHashFunction {
604
605 private ConcatenatedHashFunction(HashFunction... functions) {
606 super(functions);
607 for (HashFunction function : functions) {
608 checkArgument(
609 function.bits() % 8 == 0,
610 "the number of bits (%s) in hashFunction (%s) must be divisible by 8",
611 function.bits(),
612 function);
613 }
614 }
615
616 @Override
617 HashCode makeHash(Hasher[] hashers) {
618 byte[] bytes = new byte[bits() / 8];
619 int i = 0;
620 for (Hasher hasher : hashers) {
621 HashCode newHash = hasher.hash();
622 i += newHash.writeBytesTo(bytes, i, newHash.bits() / 8);
623 }
624 return HashCode.fromBytesNoCopy(bytes);
625 }
626
627 @Override
628 public int bits() {
629 int bitSum = 0;
630 for (HashFunction function : functions) {
631 bitSum += function.bits();
632 }
633 return bitSum;
634 }
635
636 @Override
637 public boolean equals(@CheckForNull Object object) {
638 if (object instanceof ConcatenatedHashFunction) {
639 ConcatenatedHashFunction other = (ConcatenatedHashFunction) object;
640 return Arrays.equals(functions, other.functions);
641 }
642 return false;
643 }
644
645 @Override
646 public int hashCode() {
647 return Arrays.hashCode(functions);
648 }
649 }
650
651 /**
652 * Linear CongruentialGenerator to use for consistent hashing. See
653 * http://en.wikipedia.org/wiki/Linear_congruential_generator
654 */
655 private static final class LinearCongruentialGenerator {
656 private long state;
657
658 public LinearCongruentialGenerator(long seed) {
659 this.state = seed;
660 }
661
662 public double nextDouble() {
663 state = 2862933555777941757L * state + 1;
664 return ((double) ((int) (state >>> 33) + 1)) / 0x1.0p31;
665 }
666 }
667
668 private Hashing() {}
669 }