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