2 * Copyright 2014 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 <gtest/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)));
44 const char* s1 = "hello, world!";
45 const uint64_t s1_res = 13991426986746681734ULL;
46 EXPECT_EQ(fnv64(s1), s1_res);
47 EXPECT_EQ(fnv64(s1), fnv64_buf(s1, strlen(s1)));
49 const char* s2 = "monkeys! m0nk3yz! ev3ry \\/\\/here~~~~";
50 const uint64_t s2_res = 6091394665637302478ULL;
51 EXPECT_EQ(fnv64(s2), s2_res);
52 EXPECT_EQ(fnv64(s2), fnv64_buf(s2, strlen(s2)));
55 const uint64_t s3_res = 14695981039346656037ULL;
56 EXPECT_EQ(fnv64(s3), s3_res);
57 EXPECT_EQ(fnv64(s3), fnv64_buf(s3, strlen(s3)));
59 // note: Use fnv64_buf to make a single hash value from multiple
61 const char* t4_a = "E Pluribus";
62 int64_t t4_b = 0xF1E2D3C4B5A69788;
63 int32_t t4_c = 0xAB12CD34;
64 const char* t4_d = "Unum";
65 uint64_t t4_res = 15571330457339273965ULL;
66 uint64_t t4_hash1 = fnv64_buf(t4_a,
68 uint64_t t4_hash2 = fnv64_buf(reinterpret_cast<void*>(&t4_b),
71 uint64_t t4_hash3 = fnv64_buf(reinterpret_cast<void*>(&t4_c),
74 uint64_t t4_hash4 = fnv64_buf(t4_d,
77 EXPECT_EQ(t4_hash4, t4_res);
78 // note: These are probabalistic, not determinate, but c'mon.
79 // These hash values should be different, or something's not
81 EXPECT_NE(t4_hash1, t4_hash4);
82 EXPECT_NE(t4_hash2, t4_hash4);
83 EXPECT_NE(t4_hash3, t4_hash4);
87 const char* s1 = "hello, world!";
88 const uint32_t s1_res = 2918802987ul;
89 EXPECT_EQ(hsieh_hash32(s1), s1_res);
90 EXPECT_EQ(hsieh_hash32(s1), hsieh_hash32_buf(s1, strlen(s1)));
92 const char* s2 = "monkeys! m0nk3yz! ev3ry \\/\\/here~~~~";
93 const uint32_t s2_res = 47373213ul;
94 EXPECT_EQ(hsieh_hash32(s2), s2_res);
95 EXPECT_EQ(hsieh_hash32(s2), hsieh_hash32_buf(s2, strlen(s2)));
98 const uint32_t s3_res = 0;
99 EXPECT_EQ(hsieh_hash32(s3), s3_res);
100 EXPECT_EQ(hsieh_hash32(s3), hsieh_hash32_buf(s3, strlen(s3)));
103 TEST(Hash, TWang_Mix64) {
104 uint64_t i1 = 0x78a87873e2d31dafULL;
105 uint64_t i1_res = 3389151152926383528ULL;
106 EXPECT_EQ(i1_res, twang_mix64(i1));
107 EXPECT_EQ(i1, twang_unmix64(i1_res));
109 uint64_t i2 = 0x0123456789abcdefULL;
110 uint64_t i2_res = 3061460455458984563ull;
111 EXPECT_EQ(i2_res, twang_mix64(i2));
112 EXPECT_EQ(i2, twang_unmix64(i2_res));
116 void checkTWang(uint64_t r) {
117 uint64_t result = twang_mix64(r);
118 EXPECT_EQ(r, twang_unmix64(result));
122 TEST(Hash, TWang_Unmix64) {
123 // We'll try (1 << i), (1 << i) + 1, (1 << i) - 1
124 for (int i = 1; i < 64; i++) {
125 checkTWang((1U << i) - 1);
127 checkTWang((1U << i) + 1);
131 TEST(Hash, TWang_32From64) {
132 uint64_t i1 = 0x78a87873e2d31dafULL;
133 uint32_t i1_res = 1525586863ul;
134 EXPECT_EQ(twang_32from64(i1), i1_res);
136 uint64_t i2 = 0x0123456789abcdefULL;
137 uint32_t i2_res = 2918899159ul;
138 EXPECT_EQ(twang_32from64(i2), i2_res);
141 TEST(Hash, Jenkins_Rev_Mix32) {
142 uint32_t i1 = 3805486511ul;
143 uint32_t i1_res = 381808021ul;
144 EXPECT_EQ(i1_res, jenkins_rev_mix32(i1));
145 EXPECT_EQ(i1, jenkins_rev_unmix32(i1_res));
147 uint32_t i2 = 2309737967ul;
148 uint32_t i2_res = 1834777923ul;
149 EXPECT_EQ(i2_res, jenkins_rev_mix32(i2));
150 EXPECT_EQ(i2, jenkins_rev_unmix32(i2_res));
154 void checkJenkins(uint32_t r) {
155 uint32_t result = jenkins_rev_mix32(r);
156 EXPECT_EQ(r, jenkins_rev_unmix32(result));
160 TEST(Hash, Jenkins_Rev_Unmix32) {
161 // We'll try (1 << i), (1 << i) + 1, (1 << i) - 1
162 for (int i = 1; i < 32; i++) {
163 checkJenkins((1U << i) - 1);
164 checkJenkins(1U << i);
165 checkJenkins((1U << i) + 1);
170 // Basically just confirms that things compile ok.
171 std::unordered_map<int32_t,int32_t,folly::hasher<int32_t>> m;
172 m.insert(std::make_pair(4, 5));
173 EXPECT_EQ(get_default(m, 4), 5);
176 // Not a full hasher since only handles one type
179 static size_t hash(const std::pair<int, int>& p) {
180 return p.first + p.second;
184 template <typename T, typename... Ts>
185 size_t hash_combine_test(const T& t, const Ts&... ts) {
186 return hash_combine_generic<TestHasher>(t, ts...);
190 auto a = std::make_pair(1, 2);
191 auto b = std::make_pair(3, 4);
192 auto c = std::make_pair(1, 2);
193 auto d = std::make_pair(2, 1);
194 EXPECT_EQ(hash_combine(a),
196 EXPECT_NE(hash_combine(b),
198 EXPECT_NE(hash_combine(d),
202 EXPECT_EQ(hash_combine(a, b),
204 // Test order dependence
205 EXPECT_NE(hash_combine(a, b),
208 // Test with custom hasher
209 EXPECT_EQ(hash_combine_test(a),
210 hash_combine_test(c));
212 EXPECT_NE(hash_combine_test(b),
213 hash_combine_test(c));
214 // This time, thanks to a terrible hash function, these are equal
215 EXPECT_EQ(hash_combine_test(d),
216 hash_combine_test(c));
218 EXPECT_EQ(hash_combine_test(a, b),
219 hash_combine_test(c, b));
220 // Test order dependence
221 EXPECT_NE(hash_combine_test(a, b),
222 hash_combine_test(b, a));
223 // Again, 1 + 2 == 2 + 1
224 EXPECT_EQ(hash_combine_test(a, b),
225 hash_combine_test(d, b));
228 TEST(Hash, hash_combine) {
229 EXPECT_NE(hash_combine(1, 2), hash_combine(2, 1));
232 TEST(Hash, std_tuple) {
233 typedef std::tuple<int64_t, std::string, int32_t> tuple3;
234 tuple3 t(42, "foo", 1);
236 std::unordered_map<tuple3, std::string> m;
238 EXPECT_EQ("bar", m[t]);
243 size_t hash_vector(const std::vector<T>& v) {
244 return hash_range(v.begin(), v.end());
248 TEST(Hash, hash_range) {
249 EXPECT_EQ(hash_vector<int32_t>({1, 2}), hash_vector<int16_t>({1, 2}));
250 EXPECT_NE(hash_vector<int>({2, 1}), hash_vector<int>({1, 2}));
251 EXPECT_EQ(hash_vector<int>({}), hash_vector<float>({}));
254 TEST(Hash, std_tuple_different_hash) {
255 typedef std::tuple<int64_t, std::string, int32_t> tuple3;
256 tuple3 t1(42, "foo", 1);
257 tuple3 t2(9, "bar", 3);
258 tuple3 t3(42, "foo", 3);
260 EXPECT_NE(std::hash<tuple3>()(t1),
261 std::hash<tuple3>()(t2));
262 EXPECT_NE(std::hash<tuple3>()(t1),
263 std::hash<tuple3>()(t3));