folly/hash/test/HashTest.cpp

   1 /*
   2  * Copyright 2017-present Facebook, Inc.
   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
  17 #include <folly/hash/Hash.h>
  18 #include <folly/MapUtil.h>
  19 #include <folly/portability/GTest.h>
  20 #include <stdint.h>
  21 #include <unordered_map>
  22 #include <unordered_set>
  23 #include <utility>
  24
  25 using namespace folly::hash;
  26
  27 TEST(Hash, Fnv32) {
  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)));
  32
  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)));
  37
  38   const char* s3 = "";
  39   const uint32_t s3_res = 2166136261UL;
  40   EXPECT_EQ(fnv32(s3), s3_res);
  41   EXPECT_EQ(fnv32(s3), fnv32_buf(s3, strlen(s3)));
  42
  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)));
  48 }
  49
  50 TEST(Hash, Fnv64) {
  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)));
  55
  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)));
  60
  61   const char* s3 = "";
  62   const uint64_t s3_res = 14695981039346656037ULL;
  63   EXPECT_EQ(fnv64(s3), s3_res);
  64   EXPECT_EQ(fnv64(s3), fnv64_buf(s3, strlen(s3)));
  65
  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)));
  71
  72   // note: Use fnv64_buf to make a single hash value from multiple
  73   // fields/datatypes.
  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,
  80                                 strlen(t4_a));
  81   uint64_t t4_hash2 = fnv64_buf(reinterpret_cast<void*>(&t4_b),
  82                                 sizeof(int64_t),
  83                                 t4_hash1);
  84   uint64_t t4_hash3 = fnv64_buf(reinterpret_cast<void*>(&t4_c),
  85                                 sizeof(int32_t),
  86                                 t4_hash2);
  87   uint64_t t4_hash4 = fnv64_buf(t4_d,
  88                                 strlen(t4_d),
  89                                 t4_hash3);
  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
  93   // working.
  94   EXPECT_NE(t4_hash1, t4_hash4);
  95   EXPECT_NE(t4_hash2, t4_hash4);
  96   EXPECT_NE(t4_hash3, t4_hash4);
  97 }
  98
  99 TEST(Hash, Hsieh32) {
 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)));
 104
 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)));
 109
 110   const char* s3 = "";
 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)));
 114 }
 115
 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));
 121
 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));
 126 }
 127
 128 namespace {
 129 void checkTWang(uint64_t r) {
 130   uint64_t result = twang_mix64(r);
 131   EXPECT_EQ(r, twang_unmix64(result));
 132 }
 133 } // namespace
 134
 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);
 141   }
 142 }
 143
 144 TEST(Hash, TWang_32From64) {
 145   uint64_t i1 = 0x78a87873e2d31dafULL;
 146   uint32_t i1_res = 1525586863ul;
 147   EXPECT_EQ(twang_32from64(i1), i1_res);
 148
 149   uint64_t i2 = 0x0123456789abcdefULL;
 150   uint32_t i2_res = 2918899159ul;
 151   EXPECT_EQ(twang_32from64(i2), i2_res);
 152 }
 153
 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));
 159
 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));
 164 }
 165
 166 namespace {
 167 void checkJenkins(uint32_t r) {
 168   uint32_t result = jenkins_rev_mix32(r);
 169   EXPECT_EQ(r, jenkins_rev_unmix32(result));
 170 }
 171 } // namespace
 172
 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);
 179   }
 180 }
 181
 182 TEST(Hash, hasher) {
 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);
 187 }
 188
 189 TEST(Hash, integral_types) {
 190   // Basically just confirms that things compile ok.
 191   std::unordered_set<size_t> hashes;
 192   folly::Hash hasher;
 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());
 218 }
 219
 220 TEST(Hash, float_types) {
 221   folly::Hash hasher;
 222
 223   EXPECT_EQ(hasher(0.0f), hasher(-0.0f));
 224   EXPECT_EQ(hasher(0.0), hasher(-0.0));
 225
 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));
 234
 235   EXPECT_EQ(6, hashes.size());
 236 }
 237
 238 // Not a full hasher since only handles one type
 239 class TestHasher {
 240  public:
 241   static size_t hash(const std::pair<int, int>& p) {
 242     return p.first + p.second;
 243   }
 244 };
 245
 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...);
 249 }
 250
 251 TEST(Hash, pair) {
 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),
 257             hash_combine(c));
 258   EXPECT_NE(hash_combine(b),
 259             hash_combine(c));
 260   EXPECT_NE(hash_combine(d),
 261             hash_combine(c));
 262
 263   // With composition
 264   EXPECT_EQ(hash_combine(a, b),
 265             hash_combine(c, b));
 266   // Test order dependence
 267   EXPECT_NE(hash_combine(a, b),
 268             hash_combine(b, a));
 269
 270   // Test with custom hasher
 271   EXPECT_EQ(hash_combine_test(a),
 272             hash_combine_test(c));
 273   // 3 + 4 != 1 + 2
 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));
 279   // With composition
 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));
 288 }
 289
 290 TEST(Hash, hash_combine) {
 291   EXPECT_NE(hash_combine(1, 2), hash_combine(2, 1));
 292 }
 293
 294 TEST(Hash, hash_bool) {
 295   const auto hash = folly::Hash();
 296   EXPECT_NE(hash(true), hash(false));
 297 }
 298
 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}) {
 312                       values.insert(
 313                           hash(b1, b2, b3, b4, b5, b6, b7, b8, b9, b10));
 314                     }
 315                   }
 316                 }
 317               }
 318             }
 319           }
 320         }
 321       }
 322     }
 323   }
 324   EXPECT_EQ(values.size(), 1 << 10);
 325 }
 326
 327 TEST(Hash, std_tuple) {
 328   typedef std::tuple<int64_t, std::string, int32_t> tuple3;
 329   tuple3 t(42, "foo", 1);
 330
 331   std::unordered_map<tuple3, std::string> m;
 332   m[t] = "bar";
 333   EXPECT_EQ("bar", m[t]);
 334 }
 335
 336 TEST(Hash, enum_type) {
 337   const auto hash = folly::Hash();
 338
 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));
 343
 344   std::unordered_map<Enum32, std::string, folly::Hash> m32;
 345   m32[Enum32::Foo] = "foo";
 346   EXPECT_EQ("foo", m32[Enum32::Foo]);
 347
 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));
 352
 353   std::unordered_map<Enum64, std::string, folly::Hash> m64;
 354   m64[Enum64::Foo] = "foo";
 355   EXPECT_EQ("foo", m64[Enum64::Foo]);
 356 }
 357
 358 TEST(Hash, pair_folly_hash) {
 359   typedef std::pair<int64_t, int32_t> pair2;
 360   pair2 p(42, 1);
 361
 362   std::unordered_map<pair2, std::string, folly::Hash> m;
 363   m[p] = "bar";
 364   EXPECT_EQ("bar", m[p]);
 365 }
 366
 367 TEST(Hash, tuple_folly_hash) {
 368   typedef std::tuple<int64_t, int32_t, int32_t> tuple3;
 369   tuple3 t(42, 1, 1);
 370
 371   std::unordered_map<tuple3, std::string, folly::Hash> m;
 372   m[t] = "bar";
 373   EXPECT_EQ("bar", m[t]);
 374 }
 375
 376 namespace {
 377 template <class T>
 378 size_t hash_vector(const std::vector<T>& v) {
 379   return hash_range(v.begin(), v.end());
 380 }
 381 } // namespace
 382
 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>({}));
 387 }
 388
 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);
 394
 395   EXPECT_NE(std::hash<tuple3>()(t1),
 396             std::hash<tuple3>()(t2));
 397   EXPECT_NE(std::hash<tuple3>()(t1),
 398             std::hash<tuple3>()(t3));
 399 }
 400
 401 TEST(Hash, Strings) {
 402   using namespace folly;
 403
 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");
 410   Hash h2;
 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));
 422
 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()));
 428 }
 429
 430 struct FNVTestParam {
 431   std::string in;
 432   uint64_t out;
 433 };
 434
 435 class FNVTest : public ::testing::TestWithParam<FNVTestParam> {};
 436
 437 TEST_P(FNVTest, Fnva64Buf) {
 438   EXPECT_EQ(GetParam().out,
 439             fnva64_buf(GetParam().in.data(), GetParam().in.size()));
 440 }
 441
 442 TEST_P(FNVTest, Fnva64) {
 443   EXPECT_EQ(GetParam().out, fnva64(GetParam().in));
 444 }
 445
 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,
 451             fnva64_buf(
 452                 data + partialLen, GetParam().in.size() - partialLen, partial));
 453 }
 454
 455 // Taken from http://www.isthe.com/chongo/src/fnv/test_fnv.c
 456 INSTANTIATE_TEST_CASE_P(
 457     FNVTesting,
 458     FNVTest,
 459     ::testing::Values(
 460         (FNVTestParam){"foobar", // 11
 461                        0x85944171f73967e8},
 462         (FNVTestParam){"chongo was here!\n", // 39
 463                        0x46810940eff5f915},
 464         (FNVTestParam){"127.0.0.3", // 106,
 465                        0xaabafc7104d91158},
 466         (FNVTestParam){
 467             "http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash", // 126
 468             0xd9b957fb7fe794c5},
 469         (FNVTestParam){"http://norvig.com/21-days.html", // 136
 470                        0x07aaa640476e0b9a}));