2 * Copyright 2017-present Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #include <folly/hash/Hash.h>
18 #include <folly/MapUtil.h>
19 #include <folly/portability/GTest.h>
21 #include <unordered_map>
22 #include <unordered_set>
25 using namespace folly::hash;
28 const char* s1 = "hello, world!";
29 const uint32_t s1_res = 3605494790UL;
30 EXPECT_EQ(fnv32(s1), s1_res);
31 EXPECT_EQ(fnv32(s1), fnv32_buf(s1, strlen(s1)));
33 const char* s2 = "monkeys! m0nk3yz! ev3ry \\/\\/here~~~~";
34 const uint32_t s2_res = 1270448334UL;
35 EXPECT_EQ(fnv32(s2), s2_res);
36 EXPECT_EQ(fnv32(s2), fnv32_buf(s2, strlen(s2)));
39 const uint32_t s3_res = 2166136261UL;
40 EXPECT_EQ(fnv32(s3), s3_res);
41 EXPECT_EQ(fnv32(s3), fnv32_buf(s3, strlen(s3)));
43 const uint8_t s4_data[] = {0xFF, 0xFF, 0xFF, 0x00};
44 const char* s4 = reinterpret_cast<const char*>(s4_data);
45 const uint32_t s4_res = 2420936562UL;
46 EXPECT_EQ(fnv32(s4), s4_res);
47 EXPECT_EQ(fnv32(s4), fnv32_buf(s4, strlen(s4)));
51 const char* s1 = "hello, world!";
52 const uint64_t s1_res = 13991426986746681734ULL;
53 EXPECT_EQ(fnv64(s1), s1_res);
54 EXPECT_EQ(fnv64(s1), fnv64_buf(s1, strlen(s1)));
56 const char* s2 = "monkeys! m0nk3yz! ev3ry \\/\\/here~~~~";
57 const uint64_t s2_res = 6091394665637302478ULL;
58 EXPECT_EQ(fnv64(s2), s2_res);
59 EXPECT_EQ(fnv64(s2), fnv64_buf(s2, strlen(s2)));
62 const uint64_t s3_res = 14695981039346656037ULL;
63 EXPECT_EQ(fnv64(s3), s3_res);
64 EXPECT_EQ(fnv64(s3), fnv64_buf(s3, strlen(s3)));
66 const uint8_t s4_data[] = {0xFF, 0xFF, 0xFF, 0x00};
67 const char* s4 = reinterpret_cast<const char*>(s4_data);
68 const uint64_t s4_res = 2787597222566293202ULL;
69 EXPECT_EQ(fnv64(s4), s4_res);
70 EXPECT_EQ(fnv64(s4), fnv64_buf(s4, strlen(s4)));
72 // note: Use fnv64_buf to make a single hash value from multiple
74 const char* t4_a = "E Pluribus";
75 int64_t t4_b = 0xF1E2D3C4B5A69788;
76 int32_t t4_c = 0xAB12CD34;
77 const char* t4_d = "Unum";
78 uint64_t t4_res = 15571330457339273965ULL;
79 uint64_t t4_hash1 = fnv64_buf(t4_a,
81 uint64_t t4_hash2 = fnv64_buf(reinterpret_cast<void*>(&t4_b),
84 uint64_t t4_hash3 = fnv64_buf(reinterpret_cast<void*>(&t4_c),
87 uint64_t t4_hash4 = fnv64_buf(t4_d,
90 EXPECT_EQ(t4_hash4, t4_res);
91 // note: These are probabalistic, not determinate, but c'mon.
92 // These hash values should be different, or something's not
94 EXPECT_NE(t4_hash1, t4_hash4);
95 EXPECT_NE(t4_hash2, t4_hash4);
96 EXPECT_NE(t4_hash3, t4_hash4);
100 const char* s1 = "hello, world!";
101 const uint32_t s1_res = 2918802987ul;
102 EXPECT_EQ(hsieh_hash32(s1), s1_res);
103 EXPECT_EQ(hsieh_hash32(s1), hsieh_hash32_buf(s1, strlen(s1)));
105 const char* s2 = "monkeys! m0nk3yz! ev3ry \\/\\/here~~~~";
106 const uint32_t s2_res = 47373213ul;
107 EXPECT_EQ(hsieh_hash32(s2), s2_res);
108 EXPECT_EQ(hsieh_hash32(s2), hsieh_hash32_buf(s2, strlen(s2)));
111 const uint32_t s3_res = 0;
112 EXPECT_EQ(hsieh_hash32(s3), s3_res);
113 EXPECT_EQ(hsieh_hash32(s3), hsieh_hash32_buf(s3, strlen(s3)));
116 TEST(Hash, TWang_Mix64) {
117 uint64_t i1 = 0x78a87873e2d31dafULL;
118 uint64_t i1_res = 3389151152926383528ULL;
119 EXPECT_EQ(i1_res, twang_mix64(i1));
120 EXPECT_EQ(i1, twang_unmix64(i1_res));
122 uint64_t i2 = 0x0123456789abcdefULL;
123 uint64_t i2_res = 3061460455458984563ull;
124 EXPECT_EQ(i2_res, twang_mix64(i2));
125 EXPECT_EQ(i2, twang_unmix64(i2_res));
129 void checkTWang(uint64_t r) {
130 uint64_t result = twang_mix64(r);
131 EXPECT_EQ(r, twang_unmix64(result));
135 TEST(Hash, TWang_Unmix64) {
136 // We'll try (1 << i), (1 << i) + 1, (1 << i) - 1
137 for (int i = 1; i < 64; i++) {
138 checkTWang((uint64_t(1) << i) - 1);
139 checkTWang(uint64_t(1) << i);
140 checkTWang((uint64_t(1) << i) + 1);
144 TEST(Hash, TWang_32From64) {
145 uint64_t i1 = 0x78a87873e2d31dafULL;
146 uint32_t i1_res = 1525586863ul;
147 EXPECT_EQ(twang_32from64(i1), i1_res);
149 uint64_t i2 = 0x0123456789abcdefULL;
150 uint32_t i2_res = 2918899159ul;
151 EXPECT_EQ(twang_32from64(i2), i2_res);
154 TEST(Hash, Jenkins_Rev_Mix32) {
155 uint32_t i1 = 3805486511ul;
156 uint32_t i1_res = 381808021ul;
157 EXPECT_EQ(i1_res, jenkins_rev_mix32(i1));
158 EXPECT_EQ(i1, jenkins_rev_unmix32(i1_res));
160 uint32_t i2 = 2309737967ul;
161 uint32_t i2_res = 1834777923ul;
162 EXPECT_EQ(i2_res, jenkins_rev_mix32(i2));
163 EXPECT_EQ(i2, jenkins_rev_unmix32(i2_res));
167 void checkJenkins(uint32_t r) {
168 uint32_t result = jenkins_rev_mix32(r);
169 EXPECT_EQ(r, jenkins_rev_unmix32(result));
173 TEST(Hash, Jenkins_Rev_Unmix32) {
174 // We'll try (1 << i), (1 << i) + 1, (1 << i) - 1
175 for (int i = 1; i < 32; i++) {
176 checkJenkins((1U << i) - 1);
177 checkJenkins(1U << i);
178 checkJenkins((1U << i) + 1);
183 // Basically just confirms that things compile ok.
184 std::unordered_map<int32_t,int32_t,folly::hasher<int32_t>> m;
185 m.insert(std::make_pair(4, 5));
186 EXPECT_EQ(get_default(m, 4), 5);
189 TEST(Hash, integral_types) {
190 // Basically just confirms that things compile ok.
191 std::unordered_set<size_t> hashes;
193 hashes.insert(hasher((char)1));
194 hashes.insert(hasher((signed char)2));
195 hashes.insert(hasher((unsigned char)3));
196 hashes.insert(hasher((short)4));
197 hashes.insert(hasher((signed short)5));
198 hashes.insert(hasher((unsigned short)6));
199 hashes.insert(hasher((int)7));
200 hashes.insert(hasher((signed int)8));
201 hashes.insert(hasher((unsigned int)9));
202 hashes.insert(hasher((long)10));
203 hashes.insert(hasher((signed long)11));
204 hashes.insert(hasher((unsigned long)12));
205 hashes.insert(hasher((long long)13));
206 hashes.insert(hasher((signed long long)14));
207 hashes.insert(hasher((unsigned long long)15));
208 hashes.insert(hasher((int8_t)16));
209 hashes.insert(hasher((uint8_t)17));
210 hashes.insert(hasher((int16_t)18));
211 hashes.insert(hasher((uint16_t)19));
212 hashes.insert(hasher((int32_t)20));
213 hashes.insert(hasher((uint32_t)21));
214 hashes.insert(hasher((int64_t)22));
215 hashes.insert(hasher((uint64_t)23));
216 hashes.insert(hasher((size_t)24));
217 EXPECT_EQ(24, hashes.size());
220 TEST(Hash, float_types) {
223 EXPECT_EQ(hasher(0.0f), hasher(-0.0f));
224 EXPECT_EQ(hasher(0.0), hasher(-0.0));
226 // Basically just confirms that things compile ok.
227 std::unordered_set<size_t> hashes;
228 hashes.insert(hasher(0.0f));
229 hashes.insert(hasher(0.1f));
230 hashes.insert(hasher(0.2));
231 hashes.insert(hasher(0.2f));
232 hashes.insert(hasher(-0.3));
233 hashes.insert(hasher(-0.3f));
235 EXPECT_EQ(6, hashes.size());
238 // Not a full hasher since only handles one type
241 static size_t hash(const std::pair<int, int>& p) {
242 return p.first + p.second;
246 template <typename T, typename... Ts>
247 size_t hash_combine_test(const T& t, const Ts&... ts) {
248 return hash_combine_generic<TestHasher>(t, ts...);
252 auto a = std::make_pair(1, 2);
253 auto b = std::make_pair(3, 4);
254 auto c = std::make_pair(1, 2);
255 auto d = std::make_pair(2, 1);
256 EXPECT_EQ(hash_combine(a),
258 EXPECT_NE(hash_combine(b),
260 EXPECT_NE(hash_combine(d),
264 EXPECT_EQ(hash_combine(a, b),
266 // Test order dependence
267 EXPECT_NE(hash_combine(a, b),
270 // Test with custom hasher
271 EXPECT_EQ(hash_combine_test(a),
272 hash_combine_test(c));
274 EXPECT_NE(hash_combine_test(b),
275 hash_combine_test(c));
276 // This time, thanks to a terrible hash function, these are equal
277 EXPECT_EQ(hash_combine_test(d),
278 hash_combine_test(c));
280 EXPECT_EQ(hash_combine_test(a, b),
281 hash_combine_test(c, b));
282 // Test order dependence
283 EXPECT_NE(hash_combine_test(a, b),
284 hash_combine_test(b, a));
285 // Again, 1 + 2 == 2 + 1
286 EXPECT_EQ(hash_combine_test(a, b),
287 hash_combine_test(d, b));
290 TEST(Hash, hash_combine) {
291 EXPECT_NE(hash_combine(1, 2), hash_combine(2, 1));
294 TEST(Hash, hash_bool) {
295 const auto hash = folly::Hash();
296 EXPECT_NE(hash(true), hash(false));
299 TEST(Hash, hash_bool10) {
300 const auto hash = folly::Hash();
301 std::set<size_t> values;
302 for (bool b1 : {false, true}) {
303 for (bool b2 : {false, true}) {
304 for (bool b3 : {false, true}) {
305 for (bool b4 : {false, true}) {
306 for (bool b5 : {false, true}) {
307 for (bool b6 : {false, true}) {
308 for (bool b7 : {false, true}) {
309 for (bool b8 : {false, true}) {
310 for (bool b9 : {false, true}) {
311 for (bool b10 : {false, true}) {
313 hash(b1, b2, b3, b4, b5, b6, b7, b8, b9, b10));
324 EXPECT_EQ(values.size(), 1 << 10);
327 TEST(Hash, std_tuple) {
328 typedef std::tuple<int64_t, std::string, int32_t> tuple3;
329 tuple3 t(42, "foo", 1);
331 std::unordered_map<tuple3, std::string> m;
333 EXPECT_EQ("bar", m[t]);
336 TEST(Hash, enum_type) {
337 const auto hash = folly::Hash();
339 enum class Enum32 : int32_t { Foo, Bar };
340 EXPECT_EQ(hash(static_cast<int32_t>(Enum32::Foo)), hash(Enum32::Foo));
341 EXPECT_EQ(hash(static_cast<int32_t>(Enum32::Bar)), hash(Enum32::Bar));
342 EXPECT_NE(hash(Enum32::Foo), hash(Enum32::Bar));
344 std::unordered_map<Enum32, std::string, folly::Hash> m32;
345 m32[Enum32::Foo] = "foo";
346 EXPECT_EQ("foo", m32[Enum32::Foo]);
348 enum class Enum64 : int64_t { Foo, Bar };
349 EXPECT_EQ(hash(static_cast<int64_t>(Enum64::Foo)), hash(Enum64::Foo));
350 EXPECT_EQ(hash(static_cast<int64_t>(Enum64::Bar)), hash(Enum64::Bar));
351 EXPECT_NE(hash(Enum64::Foo), hash(Enum64::Bar));
353 std::unordered_map<Enum64, std::string, folly::Hash> m64;
354 m64[Enum64::Foo] = "foo";
355 EXPECT_EQ("foo", m64[Enum64::Foo]);
358 TEST(Hash, pair_folly_hash) {
359 typedef std::pair<int64_t, int32_t> pair2;
362 std::unordered_map<pair2, std::string, folly::Hash> m;
364 EXPECT_EQ("bar", m[p]);
367 TEST(Hash, tuple_folly_hash) {
368 typedef std::tuple<int64_t, int32_t, int32_t> tuple3;
371 std::unordered_map<tuple3, std::string, folly::Hash> m;
373 EXPECT_EQ("bar", m[t]);
378 size_t hash_vector(const std::vector<T>& v) {
379 return hash_range(v.begin(), v.end());
383 TEST(Hash, hash_range) {
384 EXPECT_EQ(hash_vector<int32_t>({1, 2}), hash_vector<int16_t>({1, 2}));
385 EXPECT_NE(hash_vector<int>({2, 1}), hash_vector<int>({1, 2}));
386 EXPECT_EQ(hash_vector<int>({}), hash_vector<float>({}));
389 TEST(Hash, std_tuple_different_hash) {
390 typedef std::tuple<int64_t, std::string, int32_t> tuple3;
391 tuple3 t1(42, "foo", 1);
392 tuple3 t2(9, "bar", 3);
393 tuple3 t3(42, "foo", 3);
395 EXPECT_NE(std::hash<tuple3>()(t1),
396 std::hash<tuple3>()(t2));
397 EXPECT_NE(std::hash<tuple3>()(t1),
398 std::hash<tuple3>()(t3));
401 TEST(Hash, Strings) {
402 using namespace folly;
404 StringPiece a1 = "10050517", b1 = "51107032",
405 a2 = "10050518", b2 = "51107033",
406 a3 = "10050519", b3 = "51107034",
407 a4 = "10050525", b4 = "51107040";
408 Range<const wchar_t*> w1 = range(L"10050517"), w2 = range(L"51107032"),
409 w3 = range(L"10050518"), w4 = range(L"51107033");
411 EXPECT_NE(h2(a1), h2(b1));
412 EXPECT_NE(h2(a1), h2(b1));
413 EXPECT_NE(h2(a2), h2(b2));
414 EXPECT_NE(h2(a3), h2(b3));
415 EXPECT_NE(h2(ByteRange(a1)), h2(ByteRange(b1)));
416 EXPECT_NE(h2(ByteRange(a2)), h2(ByteRange(b2)));
417 EXPECT_NE(h2(ByteRange(a3)), h2(ByteRange(b3)));
418 EXPECT_NE(h2(ByteRange(a4)), h2(ByteRange(b4)));
419 EXPECT_NE(h2(w1), h2(w2));
420 EXPECT_NE(h2(w1), h2(w3));
421 EXPECT_NE(h2(w2), h2(w4));
423 // Check compatibility with std::string.
424 EXPECT_EQ(h2(a1), h2(a1.str()));
425 EXPECT_EQ(h2(a2), h2(a2.str()));
426 EXPECT_EQ(h2(a3), h2(a3.str()));
427 EXPECT_EQ(h2(a4), h2(a4.str()));
430 struct FNVTestParam {
435 class FNVTest : public ::testing::TestWithParam<FNVTestParam> {};
437 TEST_P(FNVTest, Fnva64Buf) {
438 EXPECT_EQ(GetParam().out,
439 fnva64_buf(GetParam().in.data(), GetParam().in.size()));
442 TEST_P(FNVTest, Fnva64) {
443 EXPECT_EQ(GetParam().out, fnva64(GetParam().in));
446 TEST_P(FNVTest, Fnva64Partial) {
447 size_t partialLen = GetParam().in.size() / 2;
448 auto data = GetParam().in.data();
449 auto partial = fnva64_buf(data, partialLen);
450 EXPECT_EQ(GetParam().out,
452 data + partialLen, GetParam().in.size() - partialLen, partial));
455 // Taken from http://www.isthe.com/chongo/src/fnv/test_fnv.c
456 INSTANTIATE_TEST_CASE_P(
460 (FNVTestParam){"foobar", // 11
462 (FNVTestParam){"chongo was here!\n", // 39
464 (FNVTestParam){"127.0.0.3", // 106,
467 "http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash", // 126
469 (FNVTestParam){"http://norvig.com/21-days.html", // 136
470 0x07aaa640476e0b9a}));