HashingTest.java revision 1d580d0f6ee4f21eb309ba7b509d2c6d671c4044 
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
17package com.google.common.hash;
18
19import com.google.common.collect.ImmutableList;
20import com.google.common.collect.Lists;
21import com.google.common.util.concurrent.AtomicLongMap;
22
23import junit.framework.TestCase;
24
25import java.util.Collections;
26import java.util.List;
27import java.util.Random;
28
29/**
30 * Unit tests for functions of {@code Hashing} that don't have their own tests.
31 */
32public 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