11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2011 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * you may not use this file except in compliance with the License. 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * You may obtain a copy of the License at 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * distributed under the License is distributed on an "AS IS" BASIS, 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * See the License for the specific language governing permissions and 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * limitations under the License. 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.hash; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 197dd252788645e940eada959bdde927426e2531c9Paul Duffinimport static com.google.common.hash.Hashing.ConcatenatedHashFunction; 200888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.hash.Hashing.goodFastHash; 217dd252788645e940eada959bdde927426e2531c9Paul Duffin 227dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.base.Charsets; 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.collect.ImmutableList; 247dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.collect.ImmutableTable; 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.collect.Lists; 267dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.collect.Table.Cell; 270888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.primitives.Ints; 280888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.testing.EqualsTester; 297dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.testing.NullPointerTester; 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.util.concurrent.AtomicLongMap; 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 320888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport junit.framework.TestCase; 330888a09821a98ac0680fad765217302858e70fa4Paul Duffin 340888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.lang.reflect.Method; 350888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.lang.reflect.Modifier; 367dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.nio.ByteBuffer; 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Collections; 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.List; 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Random; 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 427dd252788645e940eada959bdde927426e2531c9Paul Duffin * Unit tests for {@link Hashing}. 437dd252788645e940eada959bdde927426e2531c9Paul Duffin * 447dd252788645e940eada959bdde927426e2531c9Paul Duffin * @author Dimitris Andreou 457dd252788645e940eada959bdde927426e2531c9Paul Duffin * @author Kurt Alfred Kluever 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpublic class HashingTest extends TestCase { 487dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testMd5() { 497dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkAvalanche(Hashing.md5(), 100, 0.4); 507dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkNo2BitCharacteristics(Hashing.md5()); 517dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkNoFunnels(Hashing.md5()); 527dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.assertInvariants(Hashing.md5()); 537dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals("Hashing.md5()", Hashing.md5().toString()); 547dd252788645e940eada959bdde927426e2531c9Paul Duffin } 557dd252788645e940eada959bdde927426e2531c9Paul Duffin 567dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testSha1() { 577dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkAvalanche(Hashing.sha1(), 100, 0.4); 587dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkNo2BitCharacteristics(Hashing.sha1()); 597dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkNoFunnels(Hashing.sha1()); 607dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.assertInvariants(Hashing.sha1()); 617dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals("Hashing.sha1()", Hashing.sha1().toString()); 627dd252788645e940eada959bdde927426e2531c9Paul Duffin } 637dd252788645e940eada959bdde927426e2531c9Paul Duffin 647dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testSha256() { 657dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkAvalanche(Hashing.sha256(), 100, 0.4); 667dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkNo2BitCharacteristics(Hashing.sha256()); 677dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkNoFunnels(Hashing.sha256()); 687dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.assertInvariants(Hashing.sha256()); 697dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals("Hashing.sha256()", Hashing.sha256().toString()); 707dd252788645e940eada959bdde927426e2531c9Paul Duffin } 717dd252788645e940eada959bdde927426e2531c9Paul Duffin 727dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testSha512() { 737dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkAvalanche(Hashing.sha512(), 100, 0.4); 747dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkNo2BitCharacteristics(Hashing.sha512()); 757dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkNoFunnels(Hashing.sha512()); 767dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.assertInvariants(Hashing.sha512()); 777dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals("Hashing.sha512()", Hashing.sha512().toString()); 787dd252788645e940eada959bdde927426e2531c9Paul Duffin } 797dd252788645e940eada959bdde927426e2531c9Paul Duffin 807dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testCrc32() { 817dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.assertInvariants(Hashing.crc32()); 827dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals("Hashing.crc32()", Hashing.crc32().toString()); 837dd252788645e940eada959bdde927426e2531c9Paul Duffin } 847dd252788645e940eada959bdde927426e2531c9Paul Duffin 857dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testAdler32() { 867dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.assertInvariants(Hashing.adler32()); 877dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals("Hashing.adler32()", Hashing.adler32().toString()); 887dd252788645e940eada959bdde927426e2531c9Paul Duffin } 897dd252788645e940eada959bdde927426e2531c9Paul Duffin 907dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testMurmur3_128() { 917dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.check2BitAvalanche(Hashing.murmur3_128(), 250, 0.20); 927dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkAvalanche(Hashing.murmur3_128(), 250, 0.17); 937dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkNo2BitCharacteristics(Hashing.murmur3_128()); 947dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkNoFunnels(Hashing.murmur3_128()); 957dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.assertInvariants(Hashing.murmur3_128()); 967dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals("Hashing.murmur3_128(0)", Hashing.murmur3_128().toString()); 977dd252788645e940eada959bdde927426e2531c9Paul Duffin } 987dd252788645e940eada959bdde927426e2531c9Paul Duffin 997dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testMurmur3_32() { 1007dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.check2BitAvalanche(Hashing.murmur3_32(), 250, 0.20); 1017dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkAvalanche(Hashing.murmur3_32(), 250, 0.17); 1027dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkNo2BitCharacteristics(Hashing.murmur3_32()); 1037dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkNoFunnels(Hashing.murmur3_32()); 1047dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.assertInvariants(Hashing.murmur3_32()); 1057dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals("Hashing.murmur3_32(0)", Hashing.murmur3_32().toString()); 1067dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1077dd252788645e940eada959bdde927426e2531c9Paul Duffin 1080888a09821a98ac0680fad765217302858e70fa4Paul Duffin public void testSipHash24() { 1090888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashTestUtils.check2BitAvalanche(Hashing.sipHash24(), 250, 0.14); 1100888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashTestUtils.checkAvalanche(Hashing.sipHash24(), 250, 0.10); 1110888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashTestUtils.checkNo2BitCharacteristics(Hashing.sipHash24()); 1120888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashTestUtils.checkNoFunnels(Hashing.sipHash24()); 1130888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashTestUtils.assertInvariants(Hashing.sipHash24()); 1140888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals("Hashing.sipHash24(506097522914230528, 1084818905618843912)", 1150888a09821a98ac0680fad765217302858e70fa4Paul Duffin Hashing.sipHash24().toString()); 1160888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1170888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1187dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testGoodFastHash() { 1197dd252788645e940eada959bdde927426e2531c9Paul Duffin for (int i = 1; i < 200; i += 17) { 1207dd252788645e940eada959bdde927426e2531c9Paul Duffin HashFunction hasher = Hashing.goodFastHash(i); 1217dd252788645e940eada959bdde927426e2531c9Paul Duffin assertTrue(hasher.bits() >= i); 1227dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.assertInvariants(hasher); 1237dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1247dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1257dd252788645e940eada959bdde927426e2531c9Paul Duffin 1267dd252788645e940eada959bdde927426e2531c9Paul Duffin // goodFastHash(32) uses Murmur3_32. Use the same epsilon bounds. 1277dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testGoodFastHash32() { 1287dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.check2BitAvalanche(Hashing.goodFastHash(32), 250, 0.20); 1297dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkAvalanche(Hashing.goodFastHash(32), 250, 0.17); 1307dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkNo2BitCharacteristics(Hashing.goodFastHash(32)); 1317dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkNoFunnels(Hashing.goodFastHash(32)); 1327dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.assertInvariants(Hashing.goodFastHash(32)); 1337dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1347dd252788645e940eada959bdde927426e2531c9Paul Duffin 1357dd252788645e940eada959bdde927426e2531c9Paul Duffin // goodFastHash(128) uses Murmur3_128. Use the same epsilon bounds. 1367dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testGoodFastHash128() { 1377dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.check2BitAvalanche(Hashing.goodFastHash(128), 250, 0.20); 1387dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkAvalanche(Hashing.goodFastHash(128), 250, 0.17); 1397dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkNo2BitCharacteristics(Hashing.goodFastHash(128)); 1407dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkNoFunnels(Hashing.goodFastHash(128)); 1417dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.assertInvariants(Hashing.goodFastHash(128)); 1427dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1437dd252788645e940eada959bdde927426e2531c9Paul Duffin 1447dd252788645e940eada959bdde927426e2531c9Paul Duffin // goodFastHash(256) uses Murmur3_128. Use the same epsilon bounds. 1457dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testGoodFastHash256() { 1467dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.check2BitAvalanche(Hashing.goodFastHash(256), 250, 0.20); 1477dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkAvalanche(Hashing.goodFastHash(256), 250, 0.17); 1487dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkNo2BitCharacteristics(Hashing.goodFastHash(256)); 1497dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.checkNoFunnels(Hashing.goodFastHash(256)); 1507dd252788645e940eada959bdde927426e2531c9Paul Duffin HashTestUtils.assertInvariants(Hashing.goodFastHash(256)); 1517dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1527dd252788645e940eada959bdde927426e2531c9Paul Duffin 1531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testPadToLong() { 1541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(0x1111111111111111L, Hashing.padToLong(HashCodes.fromLong(0x1111111111111111L))); 1551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(0x9999999999999999L, Hashing.padToLong(HashCodes.fromLong(0x9999999999999999L))); 1561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(0x0000000011111111L, Hashing.padToLong(HashCodes.fromInt(0x11111111))); 1571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(0x0000000099999999L, Hashing.padToLong(HashCodes.fromInt(0x99999999))); 1581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testConsistentHash_correctness() { 1611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long[] interestingValues = { -1, 0, 1, 2, Long.MAX_VALUE, Long.MIN_VALUE }; 1621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (long h : interestingValues) { 1631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkConsistentHashCorrectness(h); 1641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Random r = new Random(7); 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < 20; i++) { 1671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkConsistentHashCorrectness(r.nextLong()); 1681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private void checkConsistentHashCorrectness(long hashCode) { 1721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int last = 0; 1731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int shards = 1; shards <= 100000; shards++) { 1741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int b = Hashing.consistentHash(hashCode, shards); 1751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (b != last) { 1761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(shards - 1, b); 1771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert last = b; 1781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testConsistentHash_probabilities() { 1831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert AtomicLongMap<Integer> map = AtomicLongMap.create(); 1841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Random r = new Random(9); 1851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < ITERS; i++) { 1861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert countRemaps(r.nextLong(), map); 1871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int shard = 2; shard <= MAX_SHARDS; shard++) { 1891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Rough: don't exceed 1.2x the expected number of remaps by more than 20 1901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(map.get(shard) <= 1.2 * ITERS / shard + 20); 1911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private void countRemaps(long h, AtomicLongMap<Integer> map) { 1951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int last = 0; 1961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int shards = 2; shards <= MAX_SHARDS; shards++) { 1971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int chosen = Hashing.consistentHash(h, shards); 1981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (chosen != last) { 1991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert map.incrementAndGet(shards); 2001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert last = chosen; 2011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final int ITERS = 10000; 2061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final int MAX_SHARDS = 500; 2071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testConsistentHash_outOfRange() { 2091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 2101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Hashing.consistentHash(5L, 0); 2111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert fail(); 2121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (IllegalArgumentException expected) { 2131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testConsistentHash_ofHashCode() { 2170888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkSameResult(HashCode.fromLong(1), 1); 2180888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkSameResult(HashCode.fromLong(0x9999999999999999L), 0x9999999999999999L); 2190888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkSameResult(HashCode.fromInt(0x99999999), 0x0000000099999999L); 2201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void checkSameResult(HashCode hashCode, long equivLong) { 2231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(Hashing.consistentHash(equivLong, 5555), Hashing.consistentHash(hashCode, 5555)); 2241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2267dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 2270888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Check a few "golden" values to see that implementations across languages 2280888a09821a98ac0680fad765217302858e70fa4Paul Duffin * are equivalent. 2297dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 2307dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testConsistentHash_linearCongruentialGeneratorCompatibility() { 2310888a09821a98ac0680fad765217302858e70fa4Paul Duffin int[] golden100 = 2320888a09821a98ac0680fad765217302858e70fa4Paul Duffin { 0, 55, 62, 8, 45, 59, 86, 97, 82, 59, 2330888a09821a98ac0680fad765217302858e70fa4Paul Duffin 73, 37, 17, 56, 86, 21, 90, 37, 38, 83 }; 2340888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (int i = 0; i < golden100.length; i++) { 2350888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(golden100[i], Hashing.consistentHash(i, 100)); 2360888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2370888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(6, Hashing.consistentHash(10863919174838991L, 11)); 2380888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(3, Hashing.consistentHash(2016238256797177309L, 11)); 2390888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(5, Hashing.consistentHash(1673758223894951030L, 11)); 2400888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(80343, Hashing.consistentHash(2, 100001)); 2410888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(22152, Hashing.consistentHash(2201, 100001)); 2420888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(15018, Hashing.consistentHash(2202, 100001)); 2431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2457dd252788645e940eada959bdde927426e2531c9Paul Duffin private static final double MAX_PERCENT_SPREAD = 0.5; 2467dd252788645e940eada959bdde927426e2531c9Paul Duffin private static final long RANDOM_SEED = 177L; 2477dd252788645e940eada959bdde927426e2531c9Paul Duffin 2481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCombineOrdered_empty() { 2491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 2501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Hashing.combineOrdered(Collections.<HashCode>emptySet()); 2511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert fail(); 2521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (IllegalArgumentException expected) { 2531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCombineOrdered_differentBitLengths() { 2571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 2580888a09821a98ac0680fad765217302858e70fa4Paul Duffin Hashing.combineOrdered(ImmutableList.of(HashCode.fromInt(32), HashCode.fromLong(32L))); 2591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert fail(); 2601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (IllegalArgumentException expected) { 2611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCombineOrdered() { 2650888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashCode hash31 = HashCode.fromInt(31); 2660888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashCode hash32 = HashCode.fromInt(32); 2671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(hash32, Hashing.combineOrdered(ImmutableList.of(hash32))); 2680888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(HashCode.fromBytes(new byte[] { (byte) 0x80, 0, 0, 0 }), 2691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Hashing.combineOrdered(ImmutableList.of(hash32, hash32))); 2700888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(HashCode.fromBytes(new byte[] { (byte) 0xa0, 0, 0, 0 }), 2711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Hashing.combineOrdered(ImmutableList.of(hash32, hash32, hash32))); 2721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertFalse( 2731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Hashing.combineOrdered(ImmutableList.of(hash31, hash32)).equals( 2741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Hashing.combineOrdered(ImmutableList.of(hash32, hash31)))); 2751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCombineOrdered_randomHashCodes() { 2781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Random random = new Random(7); 2791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<HashCode> hashCodes = Lists.newArrayList(); 2801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < 10; i++) { 2810888a09821a98ac0680fad765217302858e70fa4Paul Duffin hashCodes.add(HashCode.fromLong(random.nextLong())); 2821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert HashCode hashCode1 = Hashing.combineOrdered(hashCodes); 2841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Collections.shuffle(hashCodes, random); 2851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert HashCode hashCode2 = Hashing.combineOrdered(hashCodes); 2861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertFalse(hashCode1.equals(hashCode2)); 2881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCombineUnordered_empty() { 2911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 2921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Hashing.combineUnordered(Collections.<HashCode>emptySet()); 2931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert fail(); 2941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (IllegalArgumentException expected) { 2951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCombineUnordered_differentBitLengths() { 2991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 3000888a09821a98ac0680fad765217302858e70fa4Paul Duffin Hashing.combineUnordered(ImmutableList.of(HashCode.fromInt(32), HashCode.fromLong(32L))); 3011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert fail(); 3021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (IllegalArgumentException expected) { 3031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCombineUnordered() { 3070888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashCode hash31 = HashCode.fromInt(31); 3080888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashCode hash32 = HashCode.fromInt(32); 3091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(hash32, Hashing.combineUnordered(ImmutableList.of(hash32))); 3100888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(HashCode.fromInt(64), Hashing.combineUnordered(ImmutableList.of(hash32, hash32))); 3110888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(HashCode.fromInt(96), 3121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Hashing.combineUnordered(ImmutableList.of(hash32, hash32, hash32))); 3131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals( 3141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Hashing.combineUnordered(ImmutableList.of(hash31, hash32)), 3151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Hashing.combineUnordered(ImmutableList.of(hash32, hash31))); 3161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCombineUnordered_randomHashCodes() { 3190888a09821a98ac0680fad765217302858e70fa4Paul Duffin Random random = new Random(RANDOM_SEED); 3201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<HashCode> hashCodes = Lists.newArrayList(); 3211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < 10; i++) { 3220888a09821a98ac0680fad765217302858e70fa4Paul Duffin hashCodes.add(HashCode.fromLong(random.nextLong())); 3231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert HashCode hashCode1 = Hashing.combineUnordered(hashCodes); 3251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Collections.shuffle(hashCodes); 3261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert HashCode hashCode2 = Hashing.combineUnordered(hashCodes); 3271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(hashCode1, hashCode2); 3291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3307dd252788645e940eada959bdde927426e2531c9Paul Duffin 3310888a09821a98ac0680fad765217302858e70fa4Paul Duffin public void testConcatenatedHashFunction_equals() { 3320888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals( 3330888a09821a98ac0680fad765217302858e70fa4Paul Duffin new ConcatenatedHashFunction(Hashing.md5()), 3340888a09821a98ac0680fad765217302858e70fa4Paul Duffin new ConcatenatedHashFunction(Hashing.md5())); 3350888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals( 3360888a09821a98ac0680fad765217302858e70fa4Paul Duffin new ConcatenatedHashFunction(Hashing.md5(), Hashing.murmur3_32()), 3370888a09821a98ac0680fad765217302858e70fa4Paul Duffin new ConcatenatedHashFunction(Hashing.md5(), Hashing.murmur3_32())); 3380888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3390888a09821a98ac0680fad765217302858e70fa4Paul Duffin 3407dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testConcatenatedHashFunction_bits() { 3417dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals(Hashing.md5().bits(), 3427dd252788645e940eada959bdde927426e2531c9Paul Duffin new ConcatenatedHashFunction(Hashing.md5()).bits()); 3437dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals(Hashing.md5().bits() + Hashing.murmur3_32().bits(), 3447dd252788645e940eada959bdde927426e2531c9Paul Duffin new ConcatenatedHashFunction(Hashing.md5(), Hashing.murmur3_32()).bits()); 3457dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals(Hashing.md5().bits() + Hashing.murmur3_32().bits() + Hashing.murmur3_128().bits(), 3467dd252788645e940eada959bdde927426e2531c9Paul Duffin new ConcatenatedHashFunction( 3477dd252788645e940eada959bdde927426e2531c9Paul Duffin Hashing.md5(), Hashing.murmur3_32(), Hashing.murmur3_128()).bits()); 3487dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3497dd252788645e940eada959bdde927426e2531c9Paul Duffin 3507dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testConcatenatedHashFunction_makeHash() { 3517dd252788645e940eada959bdde927426e2531c9Paul Duffin byte[] md5Hash = Hashing.md5().hashLong(42L).asBytes(); 3527dd252788645e940eada959bdde927426e2531c9Paul Duffin byte[] murmur3Hash = Hashing.murmur3_32().hashLong(42L).asBytes(); 3537dd252788645e940eada959bdde927426e2531c9Paul Duffin byte[] combined = new byte[md5Hash.length + murmur3Hash.length]; 3547dd252788645e940eada959bdde927426e2531c9Paul Duffin ByteBuffer buffer = ByteBuffer.wrap(combined); 3557dd252788645e940eada959bdde927426e2531c9Paul Duffin buffer.put(md5Hash); 3567dd252788645e940eada959bdde927426e2531c9Paul Duffin buffer.put(murmur3Hash); 3577dd252788645e940eada959bdde927426e2531c9Paul Duffin 3580888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(HashCode.fromBytes(combined), 3597dd252788645e940eada959bdde927426e2531c9Paul Duffin new ConcatenatedHashFunction(Hashing.md5(), Hashing.murmur3_32()).hashLong(42L)); 3607dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3617dd252788645e940eada959bdde927426e2531c9Paul Duffin 3620888a09821a98ac0680fad765217302858e70fa4Paul Duffin public void testHashIntReverseBytesVsHashBytesIntsToByteArray() { 3630888a09821a98ac0680fad765217302858e70fa4Paul Duffin int input = 42; 3640888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals( 3650888a09821a98ac0680fad765217302858e70fa4Paul Duffin Hashing.md5().hashBytes(Ints.toByteArray(input)), 3660888a09821a98ac0680fad765217302858e70fa4Paul Duffin Hashing.md5().hashInt(Integer.reverseBytes(input))); 3670888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3680888a09821a98ac0680fad765217302858e70fa4Paul Duffin 3690888a09821a98ac0680fad765217302858e70fa4Paul Duffin public void testHashIntVsForLoop() { 3700888a09821a98ac0680fad765217302858e70fa4Paul Duffin int input = 42; 3710888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashCode expected = Hashing.md5().hashInt(input); 3720888a09821a98ac0680fad765217302858e70fa4Paul Duffin 3730888a09821a98ac0680fad765217302858e70fa4Paul Duffin Hasher hasher = Hashing.md5().newHasher(); 3740888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (int i = 0; i < 32; i += 8) { 3750888a09821a98ac0680fad765217302858e70fa4Paul Duffin hasher.putByte((byte) (input >> i)); 3760888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3770888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashCode actual = hasher.hash(); 3780888a09821a98ac0680fad765217302858e70fa4Paul Duffin 3790888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(expected, actual); 3800888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3810888a09821a98ac0680fad765217302858e70fa4Paul Duffin 3827dd252788645e940eada959bdde927426e2531c9Paul Duffin private static final String EMPTY_STRING = ""; 3837dd252788645e940eada959bdde927426e2531c9Paul Duffin private static final String TQBFJOTLD = "The quick brown fox jumps over the lazy dog"; 3847dd252788645e940eada959bdde927426e2531c9Paul Duffin private static final String TQBFJOTLDP = "The quick brown fox jumps over the lazy dog."; 3857dd252788645e940eada959bdde927426e2531c9Paul Duffin 3867dd252788645e940eada959bdde927426e2531c9Paul Duffin private static final ImmutableTable<HashFunction, String, String> KNOWN_HASHES = 3877dd252788645e940eada959bdde927426e2531c9Paul Duffin ImmutableTable.<HashFunction, String, String>builder() 3887dd252788645e940eada959bdde927426e2531c9Paul Duffin .put(Hashing.adler32(), EMPTY_STRING, "01000000") 3897dd252788645e940eada959bdde927426e2531c9Paul Duffin .put(Hashing.adler32(), TQBFJOTLD, "da0fdc5b") 3907dd252788645e940eada959bdde927426e2531c9Paul Duffin .put(Hashing.adler32(), TQBFJOTLDP, "0810e46b") 3917dd252788645e940eada959bdde927426e2531c9Paul Duffin .put(Hashing.md5(), EMPTY_STRING, "d41d8cd98f00b204e9800998ecf8427e") 3927dd252788645e940eada959bdde927426e2531c9Paul Duffin .put(Hashing.md5(), TQBFJOTLD, "9e107d9d372bb6826bd81d3542a419d6") 3937dd252788645e940eada959bdde927426e2531c9Paul Duffin .put(Hashing.md5(), TQBFJOTLDP, "e4d909c290d0fb1ca068ffaddf22cbd0") 3947dd252788645e940eada959bdde927426e2531c9Paul Duffin .put(Hashing.murmur3_128(), EMPTY_STRING, "00000000000000000000000000000000") 3957dd252788645e940eada959bdde927426e2531c9Paul Duffin .put(Hashing.murmur3_128(), TQBFJOTLD, "6c1b07bc7bbc4be347939ac4a93c437a") 3967dd252788645e940eada959bdde927426e2531c9Paul Duffin .put(Hashing.murmur3_128(), TQBFJOTLDP, "c902e99e1f4899cde7b68789a3a15d69") 3977dd252788645e940eada959bdde927426e2531c9Paul Duffin .put(Hashing.murmur3_32(), EMPTY_STRING, "00000000") 3987dd252788645e940eada959bdde927426e2531c9Paul Duffin .put(Hashing.murmur3_32(), TQBFJOTLD, "23f74f2e") 3997dd252788645e940eada959bdde927426e2531c9Paul Duffin .put(Hashing.murmur3_32(), TQBFJOTLDP, "fc8bc4d5") 4007dd252788645e940eada959bdde927426e2531c9Paul Duffin .put(Hashing.sha1(), EMPTY_STRING, "da39a3ee5e6b4b0d3255bfef95601890afd80709") 4017dd252788645e940eada959bdde927426e2531c9Paul Duffin .put(Hashing.sha1(), TQBFJOTLD, "2fd4e1c67a2d28fced849ee1bb76e7391b93eb12") 4027dd252788645e940eada959bdde927426e2531c9Paul Duffin .put(Hashing.sha1(), TQBFJOTLDP, "408d94384216f890ff7a0c3528e8bed1e0b01621") 4037dd252788645e940eada959bdde927426e2531c9Paul Duffin .put(Hashing.sha256(), EMPTY_STRING, 4047dd252788645e940eada959bdde927426e2531c9Paul Duffin "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855") 4057dd252788645e940eada959bdde927426e2531c9Paul Duffin .put(Hashing.sha256(), TQBFJOTLD, 4067dd252788645e940eada959bdde927426e2531c9Paul Duffin "d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592") 4077dd252788645e940eada959bdde927426e2531c9Paul Duffin .put(Hashing.sha256(), TQBFJOTLDP, 4087dd252788645e940eada959bdde927426e2531c9Paul Duffin "ef537f25c895bfa782526529a9b63d97aa631564d5d789c2b765448c8635fb6c") 4097dd252788645e940eada959bdde927426e2531c9Paul Duffin .put(Hashing.sha512(), EMPTY_STRING, 4107dd252788645e940eada959bdde927426e2531c9Paul Duffin "cf83e1357eefb8bdf1542850d66d8007d620e4050b5715dc83f4a921d36ce9ce" + 4117dd252788645e940eada959bdde927426e2531c9Paul Duffin "47d0d13c5d85f2b0ff8318d2877eec2f63b931bd47417a81a538327af927da3e") 4127dd252788645e940eada959bdde927426e2531c9Paul Duffin .put(Hashing.sha512(), TQBFJOTLD, 4137dd252788645e940eada959bdde927426e2531c9Paul Duffin "07e547d9586f6a73f73fbac0435ed76951218fb7d0c8d788a309d785436bbb64" + 4147dd252788645e940eada959bdde927426e2531c9Paul Duffin "2e93a252a954f23912547d1e8a3b5ed6e1bfd7097821233fa0538f3db854fee6") 4157dd252788645e940eada959bdde927426e2531c9Paul Duffin .put(Hashing.sha512(), TQBFJOTLDP, 4167dd252788645e940eada959bdde927426e2531c9Paul Duffin "91ea1245f20d46ae9a037a989f54f1f790f0a47607eeb8a14d12890cea77a1bb" + 4177dd252788645e940eada959bdde927426e2531c9Paul Duffin "c6c7ed9cf205e67b7f2b8fd4c7dfd3a7a8617e45f3c463d481c7e586c39ac1ed") 4180888a09821a98ac0680fad765217302858e70fa4Paul Duffin .put(Hashing.crc32(), EMPTY_STRING, "00000000") 4190888a09821a98ac0680fad765217302858e70fa4Paul Duffin .put(Hashing.crc32(), TQBFJOTLD, "39a34f41") 4200888a09821a98ac0680fad765217302858e70fa4Paul Duffin .put(Hashing.crc32(), TQBFJOTLDP, "e9259051") 4210888a09821a98ac0680fad765217302858e70fa4Paul Duffin .put(Hashing.sipHash24(), EMPTY_STRING, "310e0edd47db6f72") 4220888a09821a98ac0680fad765217302858e70fa4Paul Duffin .put(Hashing.sipHash24(), TQBFJOTLD, "e46f1fdc05612752") 4230888a09821a98ac0680fad765217302858e70fa4Paul Duffin .put(Hashing.sipHash24(), TQBFJOTLDP, "9b602581fce4d4f8") 4247dd252788645e940eada959bdde927426e2531c9Paul Duffin .build(); 4257dd252788645e940eada959bdde927426e2531c9Paul Duffin 4260888a09821a98ac0680fad765217302858e70fa4Paul Duffin public void testAllHashFunctionsHaveKnownHashes() throws Exception { 4270888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (Method method : Hashing.class.getDeclaredMethods()) { 4280888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (method.getReturnType().equals(HashFunction.class) // must return HashFunction 4290888a09821a98ac0680fad765217302858e70fa4Paul Duffin && Modifier.isPublic(method.getModifiers()) // only the public methods 4300888a09821a98ac0680fad765217302858e70fa4Paul Duffin && method.getParameterTypes().length == 0) { // only the seed-less grapes^W hash functions 4310888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashFunction hashFunction = (HashFunction) method.invoke(Hashing.class); 4320888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertTrue("There should be at least 3 entries in KNOWN_HASHES for " + hashFunction, 4330888a09821a98ac0680fad765217302858e70fa4Paul Duffin KNOWN_HASHES.row(hashFunction).size() >= 3); 4340888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 4350888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 4360888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 4370888a09821a98ac0680fad765217302858e70fa4Paul Duffin 4387dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testKnownUtf8Hashing() { 4397dd252788645e940eada959bdde927426e2531c9Paul Duffin for (Cell<HashFunction, String, String> cell : KNOWN_HASHES.cellSet()) { 4407dd252788645e940eada959bdde927426e2531c9Paul Duffin HashFunction func = cell.getRowKey(); 4417dd252788645e940eada959bdde927426e2531c9Paul Duffin String input = cell.getColumnKey(); 4427dd252788645e940eada959bdde927426e2531c9Paul Duffin String expected = cell.getValue(); 4437dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals( 4447dd252788645e940eada959bdde927426e2531c9Paul Duffin String.format("Known hash for hash(%s, UTF_8) failed", input), 4457dd252788645e940eada959bdde927426e2531c9Paul Duffin expected, 4467dd252788645e940eada959bdde927426e2531c9Paul Duffin func.hashString(input, Charsets.UTF_8).toString()); 4477dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4487dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4497dd252788645e940eada959bdde927426e2531c9Paul Duffin 4507dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testNullPointers() { 4517dd252788645e940eada959bdde927426e2531c9Paul Duffin NullPointerTester tester = new NullPointerTester() 4520888a09821a98ac0680fad765217302858e70fa4Paul Duffin .setDefault(HashCode.class, HashCode.fromLong(0)); 4537dd252788645e940eada959bdde927426e2531c9Paul Duffin tester.testAllPublicStaticMethods(Hashing.class); 4547dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4550888a09821a98ac0680fad765217302858e70fa4Paul Duffin 4560888a09821a98ac0680fad765217302858e70fa4Paul Duffin public void testSeedlessHashFunctionEquals() throws Exception { 4570888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertSeedlessHashFunctionEquals(Hashing.class); 4580888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 4590888a09821a98ac0680fad765217302858e70fa4Paul Duffin 4600888a09821a98ac0680fad765217302858e70fa4Paul Duffin public void testSeededHashFunctionEquals() throws Exception { 4610888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertSeededHashFunctionEquals(Hashing.class); 4620888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 4630888a09821a98ac0680fad765217302858e70fa4Paul Duffin 4640888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 4650888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Tests equality of {@link Hashing#goodFastHash} instances. This test must be separate from 4660888a09821a98ac0680fad765217302858e70fa4Paul Duffin * {@link #testSeededHashFunctionEquals} because the parameter to {@code goodFastHash} is a size, 4670888a09821a98ac0680fad765217302858e70fa4Paul Duffin * not a seed, and because that size is rounded up. Thus, {@code goodFastHash} instances with 4680888a09821a98ac0680fad765217302858e70fa4Paul Duffin * different parameters can be equal. That fact is a problem for {@code 4690888a09821a98ac0680fad765217302858e70fa4Paul Duffin * testSeededHashFunctionEquals}. 4700888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 4710888a09821a98ac0680fad765217302858e70fa4Paul Duffin public void testGoodFastHashEquals() throws Exception { 4720888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashFunction hashFunction1a = goodFastHash(1); 4730888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashFunction hashFunction1b = goodFastHash(32); 4740888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashFunction hashFunction2a = goodFastHash(33); 4750888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashFunction hashFunction2b = goodFastHash(128); 4760888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashFunction hashFunction3a = goodFastHash(129); 4770888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashFunction hashFunction3b = goodFastHash(256); 4780888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashFunction hashFunction4a = goodFastHash(257); 4790888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashFunction hashFunction4b = goodFastHash(384); 4800888a09821a98ac0680fad765217302858e70fa4Paul Duffin 4810888a09821a98ac0680fad765217302858e70fa4Paul Duffin new EqualsTester() 4820888a09821a98ac0680fad765217302858e70fa4Paul Duffin .addEqualityGroup(hashFunction1a, hashFunction1b) 4830888a09821a98ac0680fad765217302858e70fa4Paul Duffin .addEqualityGroup(hashFunction2a, hashFunction2b) 4840888a09821a98ac0680fad765217302858e70fa4Paul Duffin .addEqualityGroup(hashFunction3a, hashFunction3b) 4850888a09821a98ac0680fad765217302858e70fa4Paul Duffin .addEqualityGroup(hashFunction4a, hashFunction4b) 4860888a09821a98ac0680fad765217302858e70fa4Paul Duffin .testEquals(); 4870888a09821a98ac0680fad765217302858e70fa4Paul Duffin 4880888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(hashFunction1a.toString(), hashFunction1b.toString()); 4890888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(hashFunction2a.toString(), hashFunction2b.toString()); 4900888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(hashFunction3a.toString(), hashFunction3b.toString()); 4910888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(hashFunction4a.toString(), hashFunction4b.toString()); 4920888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 4930888a09821a98ac0680fad765217302858e70fa4Paul Duffin 4940888a09821a98ac0680fad765217302858e70fa4Paul Duffin static void assertSeedlessHashFunctionEquals(Class<?> clazz) throws Exception { 4950888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (Method method : clazz.getDeclaredMethods()) { 4960888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (method.getReturnType().equals(HashFunction.class) // must return HashFunction 4970888a09821a98ac0680fad765217302858e70fa4Paul Duffin && Modifier.isPublic(method.getModifiers()) // only the public methods 4980888a09821a98ac0680fad765217302858e70fa4Paul Duffin && method.getParameterTypes().length == 0) { // only the seed-less hash functions 4990888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashFunction hashFunction1a = (HashFunction) method.invoke(clazz); 5000888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashFunction hashFunction1b = (HashFunction) method.invoke(clazz); 5010888a09821a98ac0680fad765217302858e70fa4Paul Duffin 5020888a09821a98ac0680fad765217302858e70fa4Paul Duffin new EqualsTester() 5030888a09821a98ac0680fad765217302858e70fa4Paul Duffin .addEqualityGroup(hashFunction1a, hashFunction1b) 5040888a09821a98ac0680fad765217302858e70fa4Paul Duffin .testEquals(); 5050888a09821a98ac0680fad765217302858e70fa4Paul Duffin 5060888a09821a98ac0680fad765217302858e70fa4Paul Duffin // Make sure we're returning not only equal instances, but constants. 5070888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertSame(hashFunction1a, hashFunction1b); 5080888a09821a98ac0680fad765217302858e70fa4Paul Duffin 5090888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(hashFunction1a.toString(), hashFunction1b.toString()); 5100888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5110888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5120888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5130888a09821a98ac0680fad765217302858e70fa4Paul Duffin 5140888a09821a98ac0680fad765217302858e70fa4Paul Duffin static void assertSeededHashFunctionEquals(Class<?> clazz) throws Exception { 5150888a09821a98ac0680fad765217302858e70fa4Paul Duffin Random random = new Random(RANDOM_SEED); 5160888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (Method method : clazz.getDeclaredMethods()) { 5170888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (method.getReturnType().equals(HashFunction.class) // must return HashFunction 5180888a09821a98ac0680fad765217302858e70fa4Paul Duffin && Modifier.isPublic(method.getModifiers()) // only the public methods 5190888a09821a98ac0680fad765217302858e70fa4Paul Duffin && method.getParameterTypes().length != 0 // only the seeded hash functions 5200888a09821a98ac0680fad765217302858e70fa4Paul Duffin && !method.getName().equals("goodFastHash")) { // tested in testGoodFastHashEquals 5210888a09821a98ac0680fad765217302858e70fa4Paul Duffin Object[] params1 = new Object[method.getParameterTypes().length]; 5220888a09821a98ac0680fad765217302858e70fa4Paul Duffin Object[] params2 = new Object[method.getParameterTypes().length]; 5230888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (int i = 0; i < params1.length; i++) { 5240888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (method.getParameterTypes()[i] == int.class) { 5250888a09821a98ac0680fad765217302858e70fa4Paul Duffin params1[i] = random.nextInt(); 5260888a09821a98ac0680fad765217302858e70fa4Paul Duffin params2[i] = random.nextInt(); 5270888a09821a98ac0680fad765217302858e70fa4Paul Duffin } else if (method.getParameterTypes()[i] == long.class) { 5280888a09821a98ac0680fad765217302858e70fa4Paul Duffin params1[i] = random.nextLong(); 5290888a09821a98ac0680fad765217302858e70fa4Paul Duffin params2[i] = random.nextLong(); 5300888a09821a98ac0680fad765217302858e70fa4Paul Duffin } else { 5310888a09821a98ac0680fad765217302858e70fa4Paul Duffin fail("Unable to create a random parameter for " + method.getParameterTypes()[i]); 5320888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5330888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5340888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashFunction hashFunction1a = (HashFunction) method.invoke(clazz, params1); 5350888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashFunction hashFunction1b = (HashFunction) method.invoke(clazz, params1); 5360888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashFunction hashFunction2 = (HashFunction) method.invoke(clazz, params2); 5370888a09821a98ac0680fad765217302858e70fa4Paul Duffin 5380888a09821a98ac0680fad765217302858e70fa4Paul Duffin new EqualsTester() 5390888a09821a98ac0680fad765217302858e70fa4Paul Duffin .addEqualityGroup(hashFunction1a, hashFunction1b) 5400888a09821a98ac0680fad765217302858e70fa4Paul Duffin .addEqualityGroup(hashFunction2) 5410888a09821a98ac0680fad765217302858e70fa4Paul Duffin .testEquals(); 5420888a09821a98ac0680fad765217302858e70fa4Paul Duffin 5430888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(hashFunction1a.toString(), hashFunction1b.toString()); 5440888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5450888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5460888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 5471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 548