1 /* 2 * Copyright (C) 2011 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.common.hash; 18 19 import com.google.common.collect.ImmutableList; 20 import com.google.common.collect.Lists; 21 import com.google.common.util.concurrent.AtomicLongMap; 22 23 import junit.framework.TestCase; 24 25 import java.util.Collections; 26 import java.util.List; 27 import java.util.Random; 28 29 /** 30 * Unit tests for functions of {@code Hashing} that don't have their own tests. 31 */ 32 public class HashingTest extends TestCase { 33 public void testPadToLong() { 34 assertEquals(0x1111111111111111L, Hashing.padToLong(HashCodes.fromLong(0x1111111111111111L))); 35 assertEquals(0x9999999999999999L, Hashing.padToLong(HashCodes.fromLong(0x9999999999999999L))); 36 assertEquals(0x0000000011111111L, Hashing.padToLong(HashCodes.fromInt(0x11111111))); 37 assertEquals(0x0000000099999999L, Hashing.padToLong(HashCodes.fromInt(0x99999999))); 38 } 39 40 public void testConsistentHash_correctness() { 41 long[] interestingValues = { -1, 0, 1, 2, Long.MAX_VALUE, Long.MIN_VALUE }; 42 for (long h : interestingValues) { 43 checkConsistentHashCorrectness(h); 44 } 45 Random r = new Random(7); 46 for (int i = 0; i < 20; i++) { 47 checkConsistentHashCorrectness(r.nextLong()); 48 } 49 } 50 51 private void checkConsistentHashCorrectness(long hashCode) { 52 int last = 0; 53 for (int shards = 1; shards <= 100000; shards++) { 54 int b = Hashing.consistentHash(hashCode, shards); 55 if (b != last) { 56 assertEquals(shards - 1, b); 57 last = b; 58 } 59 } 60 } 61 62 public void testConsistentHash_probabilities() { 63 AtomicLongMap<Integer> map = AtomicLongMap.create(); 64 Random r = new Random(9); 65 for (int i = 0; i < ITERS; i++) { 66 countRemaps(r.nextLong(), map); 67 } 68 for (int shard = 2; shard <= MAX_SHARDS; shard++) { 69 // Rough: don't exceed 1.2x the expected number of remaps by more than 20 70 assertTrue(map.get(shard) <= 1.2 * ITERS / shard + 20); 71 } 72 } 73 74 private void countRemaps(long h, AtomicLongMap<Integer> map) { 75 int last = 0; 76 for (int shards = 2; shards <= MAX_SHARDS; shards++) { 77 int chosen = Hashing.consistentHash(h, shards); 78 if (chosen != last) { 79 map.incrementAndGet(shards); 80 last = chosen; 81 } 82 } 83 } 84 85 private static final int ITERS = 10000; 86 private static final int MAX_SHARDS = 500; 87 88 public void testConsistentHash_outOfRange() { 89 try { 90 Hashing.consistentHash(5L, 0); 91 fail(); 92 } catch (IllegalArgumentException expected) { 93 } 94 } 95 96 public void testConsistentHash_ofHashCode() { 97 checkSameResult(HashCodes.fromLong(1), 1); 98 checkSameResult(HashCodes.fromLong(0x9999999999999999L), 0x9999999999999999L); 99 checkSameResult(HashCodes.fromInt(0x99999999), 0x0000000099999999L); 100 } 101 102 public void checkSameResult(HashCode hashCode, long equivLong) { 103 assertEquals(Hashing.consistentHash(equivLong, 5555), Hashing.consistentHash(hashCode, 5555)); 104 } 105 106 public void testCombineOrdered_null() { 107 try { 108 Hashing.combineOrdered(null); 109 fail(); 110 } catch (NullPointerException expected) { 111 } 112 } 113 114 public void testCombineOrdered_empty() { 115 try { 116 Hashing.combineOrdered(Collections.<HashCode>emptySet()); 117 fail(); 118 } catch (IllegalArgumentException expected) { 119 } 120 } 121 122 public void testCombineOrdered_differentBitLengths() { 123 try { 124 Hashing.combineOrdered(ImmutableList.of(HashCodes.fromInt(32), HashCodes.fromLong(32L))); 125 fail(); 126 } catch (IllegalArgumentException expected) { 127 } 128 } 129 130 public void testCombineOrdered() { 131 HashCode hash31 = HashCodes.fromInt(31); 132 HashCode hash32 = HashCodes.fromInt(32); 133 assertEquals(hash32, Hashing.combineOrdered(ImmutableList.of(hash32))); 134 assertEquals(HashCodes.fromBytes(new byte[] { (byte) 0x80, 0, 0, 0 }), 135 Hashing.combineOrdered(ImmutableList.of(hash32, hash32))); 136 assertEquals(HashCodes.fromBytes(new byte[] { (byte) 0xa0, 0, 0, 0 }), 137 Hashing.combineOrdered(ImmutableList.of(hash32, hash32, hash32))); 138 assertFalse( 139 Hashing.combineOrdered(ImmutableList.of(hash31, hash32)).equals( 140 Hashing.combineOrdered(ImmutableList.of(hash32, hash31)))); 141 } 142 143 public void testCombineOrdered_randomHashCodes() { 144 Random random = new Random(7); 145 List<HashCode> hashCodes = Lists.newArrayList(); 146 for (int i = 0; i < 10; i++) { 147 hashCodes.add(HashCodes.fromLong(random.nextLong())); 148 } 149 HashCode hashCode1 = Hashing.combineOrdered(hashCodes); 150 Collections.shuffle(hashCodes, random); 151 HashCode hashCode2 = Hashing.combineOrdered(hashCodes); 152 153 assertFalse(hashCode1.equals(hashCode2)); 154 } 155 156 public void testCombineUnordered_null() { 157 try { 158 Hashing.combineUnordered(null); 159 fail(); 160 } catch (NullPointerException expected) { 161 } 162 } 163 164 public void testCombineUnordered_empty() { 165 try { 166 Hashing.combineUnordered(Collections.<HashCode>emptySet()); 167 fail(); 168 } catch (IllegalArgumentException expected) { 169 } 170 } 171 172 public void testCombineUnordered_differentBitLengths() { 173 try { 174 Hashing.combineUnordered(ImmutableList.of(HashCodes.fromInt(32), HashCodes.fromLong(32L))); 175 fail(); 176 } catch (IllegalArgumentException expected) { 177 } 178 } 179 180 public void testCombineUnordered() { 181 HashCode hash31 = HashCodes.fromInt(31); 182 HashCode hash32 = HashCodes.fromInt(32); 183 assertEquals(hash32, Hashing.combineUnordered(ImmutableList.of(hash32))); 184 assertEquals(HashCodes.fromInt(64), Hashing.combineUnordered(ImmutableList.of(hash32, hash32))); 185 assertEquals(HashCodes.fromInt(96), 186 Hashing.combineUnordered(ImmutableList.of(hash32, hash32, hash32))); 187 assertEquals( 188 Hashing.combineUnordered(ImmutableList.of(hash31, hash32)), 189 Hashing.combineUnordered(ImmutableList.of(hash32, hash31))); 190 } 191 192 public void testCombineUnordered_randomHashCodes() { 193 Random random = new Random(); 194 List<HashCode> hashCodes = Lists.newArrayList(); 195 for (int i = 0; i < 10; i++) { 196 hashCodes.add(HashCodes.fromLong(random.nextLong())); 197 } 198 HashCode hashCode1 = Hashing.combineUnordered(hashCodes); 199 Collections.shuffle(hashCodes); 200 HashCode hashCode2 = Hashing.combineUnordered(hashCodes); 201 202 assertEquals(hashCode1, hashCode2); 203 } 204 } 205
