2 * Copyright 2017 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.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 // Not a full hasher since only handles one type
223 static size_t hash(const std::pair<int, int>& p) {
224 return p.first + p.second;
228 template <typename T, typename... Ts>
229 size_t hash_combine_test(const T& t, const Ts&... ts) {
230 return hash_combine_generic<TestHasher>(t, ts...);
234 auto a = std::make_pair(1, 2);
235 auto b = std::make_pair(3, 4);
236 auto c = std::make_pair(1, 2);
237 auto d = std::make_pair(2, 1);
238 EXPECT_EQ(hash_combine(a),
240 EXPECT_NE(hash_combine(b),
242 EXPECT_NE(hash_combine(d),
246 EXPECT_EQ(hash_combine(a, b),
248 // Test order dependence
249 EXPECT_NE(hash_combine(a, b),
252 // Test with custom hasher
253 EXPECT_EQ(hash_combine_test(a),
254 hash_combine_test(c));
256 EXPECT_NE(hash_combine_test(b),
257 hash_combine_test(c));
258 // This time, thanks to a terrible hash function, these are equal
259 EXPECT_EQ(hash_combine_test(d),
260 hash_combine_test(c));
262 EXPECT_EQ(hash_combine_test(a, b),
263 hash_combine_test(c, b));
264 // Test order dependence
265 EXPECT_NE(hash_combine_test(a, b),
266 hash_combine_test(b, a));
267 // Again, 1 + 2 == 2 + 1
268 EXPECT_EQ(hash_combine_test(a, b),
269 hash_combine_test(d, b));
272 TEST(Hash, hash_combine) {
273 EXPECT_NE(hash_combine(1, 2), hash_combine(2, 1));
276 TEST(Hash, hash_bool) {
277 const auto hash = folly::Hash();
278 EXPECT_NE(hash(true), hash(false));
281 TEST(Hash, hash_bool10) {
282 const auto hash = folly::Hash();
283 std::set<size_t> values;
284 for (bool b1 : {false, true}) {
285 for (bool b2 : {false, true}) {
286 for (bool b3 : {false, true}) {
287 for (bool b4 : {false, true}) {
288 for (bool b5 : {false, true}) {
289 for (bool b6 : {false, true}) {
290 for (bool b7 : {false, true}) {
291 for (bool b8 : {false, true}) {
292 for (bool b9 : {false, true}) {
293 for (bool b10 : {false, true}) {
295 hash(b1, b2, b3, b4, b5, b6, b7, b8, b9, b10));
306 EXPECT_EQ(values.size(), 1 << 10);
309 TEST(Hash, std_tuple) {
310 typedef std::tuple<int64_t, std::string, int32_t> tuple3;
311 tuple3 t(42, "foo", 1);
313 std::unordered_map<tuple3, std::string> m;
315 EXPECT_EQ("bar", m[t]);
318 TEST(Hash, enum_type) {
319 const auto hash = folly::Hash();
321 enum class Enum32 : int32_t { Foo, Bar };
322 EXPECT_EQ(hash(static_cast<int32_t>(Enum32::Foo)), hash(Enum32::Foo));
323 EXPECT_EQ(hash(static_cast<int32_t>(Enum32::Bar)), hash(Enum32::Bar));
324 EXPECT_NE(hash(Enum32::Foo), hash(Enum32::Bar));
326 std::unordered_map<Enum32, std::string, folly::Hash> m32;
327 m32[Enum32::Foo] = "foo";
328 EXPECT_EQ("foo", m32[Enum32::Foo]);
330 enum class Enum64 : int64_t { Foo, Bar };
331 EXPECT_EQ(hash(static_cast<int64_t>(Enum64::Foo)), hash(Enum64::Foo));
332 EXPECT_EQ(hash(static_cast<int64_t>(Enum64::Bar)), hash(Enum64::Bar));
333 EXPECT_NE(hash(Enum64::Foo), hash(Enum64::Bar));
335 std::unordered_map<Enum64, std::string, folly::Hash> m64;
336 m64[Enum64::Foo] = "foo";
337 EXPECT_EQ("foo", m64[Enum64::Foo]);
340 TEST(Hash, pair_folly_hash) {
341 typedef std::pair<int64_t, int32_t> pair2;
344 std::unordered_map<pair2, std::string, folly::Hash> m;
346 EXPECT_EQ("bar", m[p]);
349 TEST(Hash, tuple_folly_hash) {
350 typedef std::tuple<int64_t, int32_t, int32_t> tuple3;
353 std::unordered_map<tuple3, std::string, folly::Hash> m;
355 EXPECT_EQ("bar", m[t]);
360 size_t hash_vector(const std::vector<T>& v) {
361 return hash_range(v.begin(), v.end());
365 TEST(Hash, hash_range) {
366 EXPECT_EQ(hash_vector<int32_t>({1, 2}), hash_vector<int16_t>({1, 2}));
367 EXPECT_NE(hash_vector<int>({2, 1}), hash_vector<int>({1, 2}));
368 EXPECT_EQ(hash_vector<int>({}), hash_vector<float>({}));
371 TEST(Hash, std_tuple_different_hash) {
372 typedef std::tuple<int64_t, std::string, int32_t> tuple3;
373 tuple3 t1(42, "foo", 1);
374 tuple3 t2(9, "bar", 3);
375 tuple3 t3(42, "foo", 3);
377 EXPECT_NE(std::hash<tuple3>()(t1),
378 std::hash<tuple3>()(t2));
379 EXPECT_NE(std::hash<tuple3>()(t1),
380 std::hash<tuple3>()(t3));
383 TEST(Hash, Strings) {
384 using namespace folly;
386 StringPiece a1 = "10050517", b1 = "51107032",
387 a2 = "10050518", b2 = "51107033",
388 a3 = "10050519", b3 = "51107034",
389 a4 = "10050525", b4 = "51107040";
390 Range<const wchar_t*> w1 = range(L"10050517"), w2 = range(L"51107032"),
391 w3 = range(L"10050518"), w4 = range(L"51107033");
393 EXPECT_NE(h2(a1), h2(b1));
394 EXPECT_NE(h2(a1), h2(b1));
395 EXPECT_NE(h2(a2), h2(b2));
396 EXPECT_NE(h2(a3), h2(b3));
397 EXPECT_NE(h2(ByteRange(a1)), h2(ByteRange(b1)));
398 EXPECT_NE(h2(ByteRange(a2)), h2(ByteRange(b2)));
399 EXPECT_NE(h2(ByteRange(a3)), h2(ByteRange(b3)));
400 EXPECT_NE(h2(ByteRange(a4)), h2(ByteRange(b4)));
401 EXPECT_NE(h2(w1), h2(w2));
402 EXPECT_NE(h2(w1), h2(w3));
403 EXPECT_NE(h2(w2), h2(w4));
405 // Check compatibility with std::string.
406 EXPECT_EQ(h2(a1), h2(a1.str()));
407 EXPECT_EQ(h2(a2), h2(a2.str()));
408 EXPECT_EQ(h2(a3), h2(a3.str()));
409 EXPECT_EQ(h2(a4), h2(a4.str()));
412 struct FNVTestParam {
417 class FNVTest : public ::testing::TestWithParam<FNVTestParam> {};
419 TEST_P(FNVTest, Fnva64Buf) {
420 EXPECT_EQ(GetParam().out,
421 fnva64_buf(GetParam().in.data(), GetParam().in.size()));
424 TEST_P(FNVTest, Fnva64) {
425 EXPECT_EQ(GetParam().out, fnva64(GetParam().in));
428 TEST_P(FNVTest, Fnva64Partial) {
429 size_t partialLen = GetParam().in.size() / 2;
430 auto data = GetParam().in.data();
431 auto partial = fnva64_buf(data, partialLen);
432 EXPECT_EQ(GetParam().out,
434 data + partialLen, GetParam().in.size() - partialLen, partial));
437 // Taken from http://www.isthe.com/chongo/src/fnv/test_fnv.c
438 INSTANTIATE_TEST_CASE_P(
442 (FNVTestParam){"foobar", // 11
444 (FNVTestParam){"chongo was here!\n", // 39
446 (FNVTestParam){"127.0.0.3", // 106,
449 "http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash", // 126
451 (FNVTestParam){"http://norvig.com/21-days.html", // 136
452 0x07aaa640476e0b9a}));