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>
24 using namespace folly::hash;
27 const char* s1 = "hello, world!";
28 const uint32_t s1_res = 3605494790UL;
29 EXPECT_EQ(fnv32(s1), s1_res);
30 EXPECT_EQ(fnv32(s1), fnv32_buf(s1, strlen(s1)));
32 const char* s2 = "monkeys! m0nk3yz! ev3ry \\/\\/here~~~~";
33 const uint32_t s2_res = 1270448334UL;
34 EXPECT_EQ(fnv32(s2), s2_res);
35 EXPECT_EQ(fnv32(s2), fnv32_buf(s2, strlen(s2)));
38 const uint32_t s3_res = 2166136261UL;
39 EXPECT_EQ(fnv32(s3), s3_res);
40 EXPECT_EQ(fnv32(s3), fnv32_buf(s3, strlen(s3)));
42 const uint8_t s4_data[] = {0xFF, 0xFF, 0xFF, 0x00};
43 const char* s4 = reinterpret_cast<const char*>(s4_data);
44 const uint32_t s4_res = 2420936562UL;
45 EXPECT_EQ(fnv32(s4), s4_res);
46 EXPECT_EQ(fnv32(s4), fnv32_buf(s4, strlen(s4)));
50 const char* s1 = "hello, world!";
51 const uint64_t s1_res = 13991426986746681734ULL;
52 EXPECT_EQ(fnv64(s1), s1_res);
53 EXPECT_EQ(fnv64(s1), fnv64_buf(s1, strlen(s1)));
55 const char* s2 = "monkeys! m0nk3yz! ev3ry \\/\\/here~~~~";
56 const uint64_t s2_res = 6091394665637302478ULL;
57 EXPECT_EQ(fnv64(s2), s2_res);
58 EXPECT_EQ(fnv64(s2), fnv64_buf(s2, strlen(s2)));
61 const uint64_t s3_res = 14695981039346656037ULL;
62 EXPECT_EQ(fnv64(s3), s3_res);
63 EXPECT_EQ(fnv64(s3), fnv64_buf(s3, strlen(s3)));
65 const uint8_t s4_data[] = {0xFF, 0xFF, 0xFF, 0x00};
66 const char* s4 = reinterpret_cast<const char*>(s4_data);
67 const uint64_t s4_res = 2787597222566293202ULL;
68 EXPECT_EQ(fnv64(s4), s4_res);
69 EXPECT_EQ(fnv64(s4), fnv64_buf(s4, strlen(s4)));
71 // note: Use fnv64_buf to make a single hash value from multiple
73 const char* t4_a = "E Pluribus";
74 int64_t t4_b = 0xF1E2D3C4B5A69788;
75 int32_t t4_c = 0xAB12CD34;
76 const char* t4_d = "Unum";
77 uint64_t t4_res = 15571330457339273965ULL;
78 uint64_t t4_hash1 = fnv64_buf(t4_a,
80 uint64_t t4_hash2 = fnv64_buf(reinterpret_cast<void*>(&t4_b),
83 uint64_t t4_hash3 = fnv64_buf(reinterpret_cast<void*>(&t4_c),
86 uint64_t t4_hash4 = fnv64_buf(t4_d,
89 EXPECT_EQ(t4_hash4, t4_res);
90 // note: These are probabalistic, not determinate, but c'mon.
91 // These hash values should be different, or something's not
93 EXPECT_NE(t4_hash1, t4_hash4);
94 EXPECT_NE(t4_hash2, t4_hash4);
95 EXPECT_NE(t4_hash3, t4_hash4);
99 const char* s1 = "hello, world!";
100 const uint32_t s1_res = 2918802987ul;
101 EXPECT_EQ(hsieh_hash32(s1), s1_res);
102 EXPECT_EQ(hsieh_hash32(s1), hsieh_hash32_buf(s1, strlen(s1)));
104 const char* s2 = "monkeys! m0nk3yz! ev3ry \\/\\/here~~~~";
105 const uint32_t s2_res = 47373213ul;
106 EXPECT_EQ(hsieh_hash32(s2), s2_res);
107 EXPECT_EQ(hsieh_hash32(s2), hsieh_hash32_buf(s2, strlen(s2)));
110 const uint32_t s3_res = 0;
111 EXPECT_EQ(hsieh_hash32(s3), s3_res);
112 EXPECT_EQ(hsieh_hash32(s3), hsieh_hash32_buf(s3, strlen(s3)));
115 TEST(Hash, TWang_Mix64) {
116 uint64_t i1 = 0x78a87873e2d31dafULL;
117 uint64_t i1_res = 3389151152926383528ULL;
118 EXPECT_EQ(i1_res, twang_mix64(i1));
119 EXPECT_EQ(i1, twang_unmix64(i1_res));
121 uint64_t i2 = 0x0123456789abcdefULL;
122 uint64_t i2_res = 3061460455458984563ull;
123 EXPECT_EQ(i2_res, twang_mix64(i2));
124 EXPECT_EQ(i2, twang_unmix64(i2_res));
128 void checkTWang(uint64_t r) {
129 uint64_t result = twang_mix64(r);
130 EXPECT_EQ(r, twang_unmix64(result));
134 TEST(Hash, TWang_Unmix64) {
135 // We'll try (1 << i), (1 << i) + 1, (1 << i) - 1
136 for (int i = 1; i < 64; i++) {
137 checkTWang((uint64_t(1) << i) - 1);
138 checkTWang(uint64_t(1) << i);
139 checkTWang((uint64_t(1) << i) + 1);
143 TEST(Hash, TWang_32From64) {
144 uint64_t i1 = 0x78a87873e2d31dafULL;
145 uint32_t i1_res = 1525586863ul;
146 EXPECT_EQ(twang_32from64(i1), i1_res);
148 uint64_t i2 = 0x0123456789abcdefULL;
149 uint32_t i2_res = 2918899159ul;
150 EXPECT_EQ(twang_32from64(i2), i2_res);
153 TEST(Hash, Jenkins_Rev_Mix32) {
154 uint32_t i1 = 3805486511ul;
155 uint32_t i1_res = 381808021ul;
156 EXPECT_EQ(i1_res, jenkins_rev_mix32(i1));
157 EXPECT_EQ(i1, jenkins_rev_unmix32(i1_res));
159 uint32_t i2 = 2309737967ul;
160 uint32_t i2_res = 1834777923ul;
161 EXPECT_EQ(i2_res, jenkins_rev_mix32(i2));
162 EXPECT_EQ(i2, jenkins_rev_unmix32(i2_res));
166 void checkJenkins(uint32_t r) {
167 uint32_t result = jenkins_rev_mix32(r);
168 EXPECT_EQ(r, jenkins_rev_unmix32(result));
172 TEST(Hash, Jenkins_Rev_Unmix32) {
173 // We'll try (1 << i), (1 << i) + 1, (1 << i) - 1
174 for (int i = 1; i < 32; i++) {
175 checkJenkins((1U << i) - 1);
176 checkJenkins(1U << i);
177 checkJenkins((1U << i) + 1);
182 // Basically just confirms that things compile ok.
183 std::unordered_map<int32_t,int32_t,folly::hasher<int32_t>> m;
184 m.insert(std::make_pair(4, 5));
185 EXPECT_EQ(get_default(m, 4), 5);
188 // Not a full hasher since only handles one type
191 static size_t hash(const std::pair<int, int>& p) {
192 return p.first + p.second;
196 template <typename T, typename... Ts>
197 size_t hash_combine_test(const T& t, const Ts&... ts) {
198 return hash_combine_generic<TestHasher>(t, ts...);
202 auto a = std::make_pair(1, 2);
203 auto b = std::make_pair(3, 4);
204 auto c = std::make_pair(1, 2);
205 auto d = std::make_pair(2, 1);
206 EXPECT_EQ(hash_combine(a),
208 EXPECT_NE(hash_combine(b),
210 EXPECT_NE(hash_combine(d),
214 EXPECT_EQ(hash_combine(a, b),
216 // Test order dependence
217 EXPECT_NE(hash_combine(a, b),
220 // Test with custom hasher
221 EXPECT_EQ(hash_combine_test(a),
222 hash_combine_test(c));
224 EXPECT_NE(hash_combine_test(b),
225 hash_combine_test(c));
226 // This time, thanks to a terrible hash function, these are equal
227 EXPECT_EQ(hash_combine_test(d),
228 hash_combine_test(c));
230 EXPECT_EQ(hash_combine_test(a, b),
231 hash_combine_test(c, b));
232 // Test order dependence
233 EXPECT_NE(hash_combine_test(a, b),
234 hash_combine_test(b, a));
235 // Again, 1 + 2 == 2 + 1
236 EXPECT_EQ(hash_combine_test(a, b),
237 hash_combine_test(d, b));
240 TEST(Hash, hash_combine) {
241 EXPECT_NE(hash_combine(1, 2), hash_combine(2, 1));
244 TEST(Hash, hash_bool) {
245 const auto hash = folly::Hash();
246 EXPECT_NE(hash(true), hash(false));
249 TEST(Hash, hash_bool10) {
250 const auto hash = folly::Hash();
251 std::set<size_t> values;
252 for (bool b1 : {false, true}) {
253 for (bool b2 : {false, true}) {
254 for (bool b3 : {false, true}) {
255 for (bool b4 : {false, true}) {
256 for (bool b5 : {false, true}) {
257 for (bool b6 : {false, true}) {
258 for (bool b7 : {false, true}) {
259 for (bool b8 : {false, true}) {
260 for (bool b9 : {false, true}) {
261 for (bool b10 : {false, true}) {
263 hash(b1, b2, b3, b4, b5, b6, b7, b8, b9, b10));
274 EXPECT_EQ(values.size(), 1 << 10);
277 TEST(Hash, std_tuple) {
278 typedef std::tuple<int64_t, std::string, int32_t> tuple3;
279 tuple3 t(42, "foo", 1);
281 std::unordered_map<tuple3, std::string> m;
283 EXPECT_EQ("bar", m[t]);
286 TEST(Hash, enum_type) {
287 const auto hash = folly::Hash();
289 enum class Enum32 : int32_t { Foo, Bar };
290 EXPECT_EQ(hash(static_cast<int32_t>(Enum32::Foo)), hash(Enum32::Foo));
291 EXPECT_EQ(hash(static_cast<int32_t>(Enum32::Bar)), hash(Enum32::Bar));
292 EXPECT_NE(hash(Enum32::Foo), hash(Enum32::Bar));
294 std::unordered_map<Enum32, std::string, folly::Hash> m32;
295 m32[Enum32::Foo] = "foo";
296 EXPECT_EQ("foo", m32[Enum32::Foo]);
298 enum class Enum64 : int64_t { Foo, Bar };
299 EXPECT_EQ(hash(static_cast<int64_t>(Enum64::Foo)), hash(Enum64::Foo));
300 EXPECT_EQ(hash(static_cast<int64_t>(Enum64::Bar)), hash(Enum64::Bar));
301 EXPECT_NE(hash(Enum64::Foo), hash(Enum64::Bar));
303 std::unordered_map<Enum64, std::string, folly::Hash> m64;
304 m64[Enum64::Foo] = "foo";
305 EXPECT_EQ("foo", m64[Enum64::Foo]);
308 TEST(Hash, pair_folly_hash) {
309 typedef std::pair<int64_t, int32_t> pair2;
312 std::unordered_map<pair2, std::string, folly::Hash> m;
314 EXPECT_EQ("bar", m[p]);
317 TEST(Hash, tuple_folly_hash) {
318 typedef std::tuple<int64_t, int32_t, int32_t> tuple3;
321 std::unordered_map<tuple3, std::string, folly::Hash> m;
323 EXPECT_EQ("bar", m[t]);
328 size_t hash_vector(const std::vector<T>& v) {
329 return hash_range(v.begin(), v.end());
333 TEST(Hash, hash_range) {
334 EXPECT_EQ(hash_vector<int32_t>({1, 2}), hash_vector<int16_t>({1, 2}));
335 EXPECT_NE(hash_vector<int>({2, 1}), hash_vector<int>({1, 2}));
336 EXPECT_EQ(hash_vector<int>({}), hash_vector<float>({}));
339 TEST(Hash, std_tuple_different_hash) {
340 typedef std::tuple<int64_t, std::string, int32_t> tuple3;
341 tuple3 t1(42, "foo", 1);
342 tuple3 t2(9, "bar", 3);
343 tuple3 t3(42, "foo", 3);
345 EXPECT_NE(std::hash<tuple3>()(t1),
346 std::hash<tuple3>()(t2));
347 EXPECT_NE(std::hash<tuple3>()(t1),
348 std::hash<tuple3>()(t3));
351 TEST(Hash, Strings) {
352 using namespace folly;
354 StringPiece a1 = "10050517", b1 = "51107032",
355 a2 = "10050518", b2 = "51107033",
356 a3 = "10050519", b3 = "51107034",
357 a4 = "10050525", b4 = "51107040";
358 Range<const wchar_t*> w1 = range(L"10050517"), w2 = range(L"51107032"),
359 w3 = range(L"10050518"), w4 = range(L"51107033");
361 EXPECT_NE(h2(a1), h2(b1));
362 EXPECT_NE(h2(a1), h2(b1));
363 EXPECT_NE(h2(a2), h2(b2));
364 EXPECT_NE(h2(a3), h2(b3));
365 EXPECT_NE(h2(ByteRange(a1)), h2(ByteRange(b1)));
366 EXPECT_NE(h2(ByteRange(a2)), h2(ByteRange(b2)));
367 EXPECT_NE(h2(ByteRange(a3)), h2(ByteRange(b3)));
368 EXPECT_NE(h2(ByteRange(a4)), h2(ByteRange(b4)));
369 EXPECT_NE(h2(w1), h2(w2));
370 EXPECT_NE(h2(w1), h2(w3));
371 EXPECT_NE(h2(w2), h2(w4));
373 // Check compatibility with std::string.
374 EXPECT_EQ(h2(a1), h2(a1.str()));
375 EXPECT_EQ(h2(a2), h2(a2.str()));
376 EXPECT_EQ(h2(a3), h2(a3.str()));
377 EXPECT_EQ(h2(a4), h2(a4.str()));