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