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.errorprone.annotations.Immutable; 021import java.security.Key; 022import java.util.ArrayList; 023import java.util.Arrays; 024import java.util.Collections; 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@ElementTypesAreNonnullByDefault 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. This can be arbitrarily large. The returned {@link 061 * HashFunction} instance may use memory proportional to this integer. 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 "Hashing." 378 + methodName 379 + "(Key[algorithm=" 380 + key.getAlgorithm() 381 + ", format=" 382 + key.getFormat() 383 + "])"; 384 } 385 386 /** 387 * Returns a hash function implementing the CRC32C checksum algorithm (32 hash bits) as described 388 * by RFC 3720, Section 12.1. 389 * 390 * <p>This function is best understood as a <a 391 * href="https://en.wikipedia.org/wiki/Checksum">checksum</a> rather than a true <a 392 * href="https://en.wikipedia.org/wiki/Hash_function">hash function</a>. 393 * 394 * @since 18.0 395 */ 396 public static HashFunction crc32c() { 397 return Crc32CSupplier.HASH_FUNCTION; 398 } 399 400 @Immutable 401 private enum Crc32CSupplier implements ImmutableSupplier<HashFunction> { 402 ABSTRACT_HASH_FUNCTION { 403 @Override 404 public HashFunction get() { 405 return Crc32cHashFunction.CRC_32_C; 406 } 407 }; 408 409 static final HashFunction HASH_FUNCTION = values()[0].get(); 410 } 411 412 /** 413 * Returns a hash function implementing the CRC-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 crc32() { 425 return ChecksumType.CRC_32.hashFunction; 426 } 427 428 /** 429 * Returns a hash function implementing the Adler-32 checksum algorithm (32 hash bits). 430 * 431 * <p>To get the {@code long} value equivalent to {@link Checksum#getValue()} for a {@code 432 * HashCode} produced by this function, use {@link HashCode#padToLong()}. 433 * 434 * <p>This function is best understood as a <a 435 * href="https://en.wikipedia.org/wiki/Checksum">checksum</a> rather than a true <a 436 * href="https://en.wikipedia.org/wiki/Hash_function">hash function</a>. 437 * 438 * @since 14.0 439 */ 440 public static HashFunction adler32() { 441 return ChecksumType.ADLER_32.hashFunction; 442 } 443 444 @Immutable 445 enum ChecksumType implements ImmutableSupplier<Checksum> { 446 CRC_32("Hashing.crc32()") { 447 @Override 448 public Checksum get() { 449 return new CRC32(); 450 } 451 }, 452 ADLER_32("Hashing.adler32()") { 453 @Override 454 public Checksum get() { 455 return new Adler32(); 456 } 457 }; 458 459 public final HashFunction hashFunction; 460 461 ChecksumType(String toString) { 462 this.hashFunction = new ChecksumHashFunction(this, 32, toString); 463 } 464 } 465 466 /** 467 * Returns a hash function implementing FarmHash's Fingerprint64, an open-source algorithm. 468 * 469 * <p>This is designed for generating persistent fingerprints of strings. It isn't 470 * cryptographically secure, but it produces a high-quality hash with fewer collisions than some 471 * alternatives we've used in the past. 472 * 473 * <p>FarmHash fingerprints are encoded by {@link HashCode#asBytes} in little-endian order. This 474 * means {@link HashCode#asLong} is guaranteed to return the same value that 475 * farmhash::Fingerprint64() would for the same input (when compared using {@link 476 * com.google.common.primitives.UnsignedLongs}'s encoding of 64-bit unsigned numbers). 477 * 478 * <p>This function is best understood as a <a 479 * href="https://en.wikipedia.org/wiki/Fingerprint_(computing)">fingerprint</a> rather than a true 480 * <a href="https://en.wikipedia.org/wiki/Hash_function">hash function</a>. 481 * 482 * @since 20.0 483 */ 484 public static HashFunction farmHashFingerprint64() { 485 return FarmHashFingerprint64.FARMHASH_FINGERPRINT_64; 486 } 487 488 /** 489 * Returns a hash function implementing the Fingerprint2011 hashing function (64 hash bits). 490 * 491 * <p>This is designed for generating persistent fingerprints of strings. It isn't 492 * cryptographically secure, but it produces a high-quality hash with few collisions. Fingerprints 493 * generated using this are byte-wise identical to those created using the C++ version, but note 494 * that this uses unsigned integers (see {@link com.google.common.primitives.UnsignedInts}). 495 * Comparisons between the two should take this into account. 496 * 497 * <p>Fingerprint2011() is a form of Murmur2 on strings up to 32 bytes and a form of CityHash for 498 * longer strings. It could have been one or the other throughout. The main advantage of the 499 * combination is that CityHash has a bunch of special cases for short strings that don't need to 500 * be replicated here. The result will never be 0 or 1. 501 * 502 * <p>This function is best understood as a <a 503 * href="https://en.wikipedia.org/wiki/Fingerprint_(computing)">fingerprint</a> rather than a true 504 * <a href="https://en.wikipedia.org/wiki/Hash_function">hash function</a>. 505 * 506 * @since 31.1 507 */ 508 public static HashFunction fingerprint2011() { 509 return Fingerprint2011.FINGERPRINT_2011; 510 } 511 512 /** 513 * Assigns to {@code hashCode} a "bucket" in the range {@code [0, buckets)}, in a uniform manner 514 * that minimizes the need for remapping as {@code buckets} grows. That is, {@code 515 * consistentHash(h, n)} equals: 516 * 517 * <ul> 518 * <li>{@code n - 1}, with approximate probability {@code 1/n} 519 * <li>{@code consistentHash(h, n - 1)}, otherwise (probability {@code 1 - 1/n}) 520 * </ul> 521 * 522 * <p>This method is suitable for the common use case of dividing work among buckets that meet the 523 * following conditions: 524 * 525 * <ul> 526 * <li>You want to assign the same fraction of inputs to each bucket. 527 * <li>When you reduce the number of buckets, you can accept that the most recently added 528 * buckets will be removed first. More concretely, if you are dividing traffic among tasks, 529 * you can decrease the number of tasks from 15 and 10, killing off the final 5 tasks, and 530 * {@code consistentHash} will handle it. If, however, you are dividing traffic among 531 * servers {@code alpha}, {@code bravo}, and {@code charlie} and you occasionally need to 532 * take each of the servers offline, {@code consistentHash} will be a poor fit: It provides 533 * no way for you to specify which of the three buckets is disappearing. Thus, if your 534 * buckets change from {@code [alpha, bravo, charlie]} to {@code [bravo, charlie]}, it will 535 * assign all the old {@code alpha} traffic to {@code bravo} and all the old {@code bravo} 536 * traffic to {@code charlie}, rather than letting {@code bravo} keep its traffic. 537 * </ul> 538 * 539 * <p>See the <a href="http://en.wikipedia.org/wiki/Consistent_hashing">Wikipedia article on 540 * consistent hashing</a> for more information. 541 */ 542 public static int consistentHash(HashCode hashCode, int buckets) { 543 return consistentHash(hashCode.padToLong(), buckets); 544 } 545 546 /** 547 * Assigns to {@code input} a "bucket" in the range {@code [0, buckets)}, in a uniform manner that 548 * minimizes the need for remapping as {@code buckets} grows. That is, {@code consistentHash(h, 549 * n)} equals: 550 * 551 * <ul> 552 * <li>{@code n - 1}, with approximate probability {@code 1/n} 553 * <li>{@code consistentHash(h, n - 1)}, otherwise (probability {@code 1 - 1/n}) 554 * </ul> 555 * 556 * <p>This method is suitable for the common use case of dividing work among buckets that meet the 557 * following conditions: 558 * 559 * <ul> 560 * <li>You want to assign the same fraction of inputs to each bucket. 561 * <li>When you reduce the number of buckets, you can accept that the most recently added 562 * buckets will be removed first. More concretely, if you are dividing traffic among tasks, 563 * you can decrease the number of tasks from 15 and 10, killing off the final 5 tasks, and 564 * {@code consistentHash} will handle it. If, however, you are dividing traffic among 565 * servers {@code alpha}, {@code bravo}, and {@code charlie} and you occasionally need to 566 * take each of the servers offline, {@code consistentHash} will be a poor fit: It provides 567 * no way for you to specify which of the three buckets is disappearing. Thus, if your 568 * buckets change from {@code [alpha, bravo, charlie]} to {@code [bravo, charlie]}, it will 569 * assign all the old {@code alpha} traffic to {@code bravo} and all the old {@code bravo} 570 * traffic to {@code charlie}, rather than letting {@code bravo} keep its traffic. 571 * </ul> 572 * 573 * <p>See the <a href="http://en.wikipedia.org/wiki/Consistent_hashing">Wikipedia article on 574 * consistent hashing</a> for more information. 575 */ 576 public static int consistentHash(long input, int buckets) { 577 checkArgument(buckets > 0, "buckets must be positive: %s", buckets); 578 LinearCongruentialGenerator generator = new LinearCongruentialGenerator(input); 579 int candidate = 0; 580 int next; 581 582 // Jump from bucket to bucket until we go out of range 583 while (true) { 584 next = (int) ((candidate + 1) / generator.nextDouble()); 585 if (next >= 0 && next < buckets) { 586 candidate = next; 587 } else { 588 return candidate; 589 } 590 } 591 } 592 593 /** 594 * Returns a hash code, having the same bit length as each of the input hash codes, that combines 595 * the information of these hash codes in an ordered fashion. That is, whenever two equal hash 596 * codes are produced by two calls to this method, it is <i>as likely as possible</i> that each 597 * was computed from the <i>same</i> input hash codes in the <i>same</i> order. 598 * 599 * @throws IllegalArgumentException if {@code hashCodes} is empty, or the hash codes do not all 600 * have the same bit length 601 */ 602 public static HashCode combineOrdered(Iterable<HashCode> hashCodes) { 603 Iterator<HashCode> iterator = hashCodes.iterator(); 604 checkArgument(iterator.hasNext(), "Must be at least 1 hash code to combine."); 605 int bits = iterator.next().bits(); 606 byte[] resultBytes = new byte[bits / 8]; 607 for (HashCode hashCode : hashCodes) { 608 byte[] nextBytes = hashCode.asBytes(); 609 checkArgument( 610 nextBytes.length == resultBytes.length, "All hashcodes must have the same bit length."); 611 for (int i = 0; i < nextBytes.length; i++) { 612 resultBytes[i] = (byte) (resultBytes[i] * 37 ^ nextBytes[i]); 613 } 614 } 615 return HashCode.fromBytesNoCopy(resultBytes); 616 } 617 618 /** 619 * Returns a hash code, having the same bit length as each of the input hash codes, that combines 620 * the information of these hash codes in an unordered fashion. That is, whenever two equal hash 621 * codes are produced by two calls to this method, it is <i>as likely as possible</i> that each 622 * was computed from the <i>same</i> input hash codes in <i>some</i> order. 623 * 624 * @throws IllegalArgumentException if {@code hashCodes} is empty, or the hash codes do not all 625 * have the same bit length 626 */ 627 public static HashCode combineUnordered(Iterable<HashCode> hashCodes) { 628 Iterator<HashCode> iterator = hashCodes.iterator(); 629 checkArgument(iterator.hasNext(), "Must be at least 1 hash code to combine."); 630 byte[] resultBytes = new byte[iterator.next().bits() / 8]; 631 for (HashCode hashCode : hashCodes) { 632 byte[] nextBytes = hashCode.asBytes(); 633 checkArgument( 634 nextBytes.length == resultBytes.length, "All hashcodes must have the same bit length."); 635 for (int i = 0; i < nextBytes.length; i++) { 636 resultBytes[i] += nextBytes[i]; 637 } 638 } 639 return HashCode.fromBytesNoCopy(resultBytes); 640 } 641 642 /** Checks that the passed argument is positive, and ceils it to a multiple of 32. */ 643 static int checkPositiveAndMakeMultipleOf32(int bits) { 644 checkArgument(bits > 0, "Number of bits must be positive"); 645 return (bits + 31) & ~31; 646 } 647 648 /** 649 * Returns a hash function which computes its hash code by concatenating the hash codes of the 650 * underlying hash functions together. This can be useful if you need to generate hash codes of a 651 * specific length. 652 * 653 * <p>For example, if you need 1024-bit hash codes, you could join two {@link Hashing#sha512} hash 654 * functions together: {@code Hashing.concatenating(Hashing.sha512(), Hashing.sha512())}. 655 * 656 * @since 19.0 657 */ 658 public static HashFunction concatenating( 659 HashFunction first, HashFunction second, HashFunction... rest) { 660 // We can't use Lists.asList() here because there's no hash->collect dependency 661 List<HashFunction> list = new ArrayList<>(); 662 list.add(first); 663 list.add(second); 664 Collections.addAll(list, rest); 665 return new ConcatenatedHashFunction(list.toArray(new HashFunction[0])); 666 } 667 668 /** 669 * Returns a hash function which computes its hash code by concatenating the hash codes of the 670 * underlying hash functions together. This can be useful if you need to generate hash codes of a 671 * specific length. 672 * 673 * <p>For example, if you need 1024-bit hash codes, you could join two {@link Hashing#sha512} hash 674 * functions together: {@code Hashing.concatenating(Hashing.sha512(), Hashing.sha512())}. 675 * 676 * @since 19.0 677 */ 678 public static HashFunction concatenating(Iterable<HashFunction> hashFunctions) { 679 checkNotNull(hashFunctions); 680 // We can't use Iterables.toArray() here because there's no hash->collect dependency 681 List<HashFunction> list = new ArrayList<>(); 682 for (HashFunction hashFunction : hashFunctions) { 683 list.add(hashFunction); 684 } 685 checkArgument(!list.isEmpty(), "number of hash functions (%s) must be > 0", list.size()); 686 return new ConcatenatedHashFunction(list.toArray(new HashFunction[0])); 687 } 688 689 private static final class ConcatenatedHashFunction extends AbstractCompositeHashFunction { 690 691 private ConcatenatedHashFunction(HashFunction... functions) { 692 super(functions); 693 for (HashFunction function : functions) { 694 checkArgument( 695 function.bits() % 8 == 0, 696 "the number of bits (%s) in hashFunction (%s) must be divisible by 8", 697 function.bits(), 698 function); 699 } 700 } 701 702 @Override 703 HashCode makeHash(Hasher[] hashers) { 704 byte[] bytes = new byte[bits() / 8]; 705 int i = 0; 706 for (Hasher hasher : hashers) { 707 HashCode newHash = hasher.hash(); 708 i += newHash.writeBytesTo(bytes, i, newHash.bits() / 8); 709 } 710 return HashCode.fromBytesNoCopy(bytes); 711 } 712 713 @Override 714 public int bits() { 715 int bitSum = 0; 716 for (HashFunction function : functions) { 717 bitSum += function.bits(); 718 } 719 return bitSum; 720 } 721 722 @Override 723 public boolean equals(@CheckForNull Object object) { 724 if (object instanceof ConcatenatedHashFunction) { 725 ConcatenatedHashFunction other = (ConcatenatedHashFunction) object; 726 return Arrays.equals(functions, other.functions); 727 } 728 return false; 729 } 730 731 @Override 732 public int hashCode() { 733 return Arrays.hashCode(functions); 734 } 735 } 736 737 /** 738 * Linear CongruentialGenerator to use for consistent hashing. See 739 * http://en.wikipedia.org/wiki/Linear_congruential_generator 740 */ 741 private static final class LinearCongruentialGenerator { 742 private long state; 743 744 public LinearCongruentialGenerator(long seed) { 745 this.state = seed; 746 } 747 748 public double nextDouble() { 749 state = 2862933555777941757L * state + 1; 750 return ((double) ((int) (state >>> 33) + 1)) / 0x1.0p31; 751 } 752 } 753 754 private Hashing() {} 755}