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