folly/test/HashTest.cpp

   1 /*
   2  * Copyright 2017 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.h>
  18 #include <folly/MapUtil.h>
  19 #include <folly/portability/GTest.h>
  20 #include <stdint.h>
  21 #include <unordered_map>
  22 #include <utility>
  23
  24 using namespace folly::hash;
  25
  26 TEST(Hash, Fnv32) {
  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)));
  31
  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)));
  36
  37   const char* s3 = "";
  38   const uint32_t s3_res = 2166136261UL;
  39   EXPECT_EQ(fnv32(s3), s3_res);
  40   EXPECT_EQ(fnv32(s3), fnv32_buf(s3, strlen(s3)));
  41
  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)));
  47 }
  48
  49 TEST(Hash, Fnv64) {
  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)));
  54
  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)));
  59
  60   const char* s3 = "";
  61   const uint64_t s3_res = 14695981039346656037ULL;
  62   EXPECT_EQ(fnv64(s3), s3_res);
  63   EXPECT_EQ(fnv64(s3), fnv64_buf(s3, strlen(s3)));
  64
  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)));
  70
  71   // note: Use fnv64_buf to make a single hash value from multiple
  72   // fields/datatypes.
  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,
  79                                 strlen(t4_a));
  80   uint64_t t4_hash2 = fnv64_buf(reinterpret_cast<void*>(&t4_b),
  81                                 sizeof(int64_t),
  82                                 t4_hash1);
  83   uint64_t t4_hash3 = fnv64_buf(reinterpret_cast<void*>(&t4_c),
  84                                 sizeof(int32_t),
  85                                 t4_hash2);
  86   uint64_t t4_hash4 = fnv64_buf(t4_d,
  87                                 strlen(t4_d),
  88                                 t4_hash3);
  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
  92   // working.
  93   EXPECT_NE(t4_hash1, t4_hash4);
  94   EXPECT_NE(t4_hash2, t4_hash4);
  95   EXPECT_NE(t4_hash3, t4_hash4);
  96 }
  97
  98 TEST(Hash, Hsieh32) {
  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)));
 103
 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)));
 108
 109   const char* s3 = "";
 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)));
 113 }
 114
 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));
 120
 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));
 125 }
 126
 127 namespace {
 128 void checkTWang(uint64_t r) {
 129   uint64_t result = twang_mix64(r);
 130   EXPECT_EQ(r, twang_unmix64(result));
 131 }
 132 }  // namespace
 133
 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);
 140   }
 141 }
 142
 143 TEST(Hash, TWang_32From64) {
 144   uint64_t i1 = 0x78a87873e2d31dafULL;
 145   uint32_t i1_res = 1525586863ul;
 146   EXPECT_EQ(twang_32from64(i1), i1_res);
 147
 148   uint64_t i2 = 0x0123456789abcdefULL;
 149   uint32_t i2_res = 2918899159ul;
 150   EXPECT_EQ(twang_32from64(i2), i2_res);
 151 }
 152
 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));
 158
 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));
 163 }
 164
 165 namespace {
 166 void checkJenkins(uint32_t r) {
 167   uint32_t result = jenkins_rev_mix32(r);
 168   EXPECT_EQ(r, jenkins_rev_unmix32(result));
 169 }
 170 }  // namespace
 171
 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);
 178   }
 179 }
 180
 181 TEST(Hash, hasher) {
 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);
 186 }
 187
 188 // Not a full hasher since only handles one type
 189 class TestHasher {
 190  public:
 191   static size_t hash(const std::pair<int, int>& p) {
 192     return p.first + p.second;
 193   }
 194 };
 195
 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...);
 199 }
 200
 201 TEST(Hash, pair) {
 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),
 207             hash_combine(c));
 208   EXPECT_NE(hash_combine(b),
 209             hash_combine(c));
 210   EXPECT_NE(hash_combine(d),
 211             hash_combine(c));
 212
 213   // With composition
 214   EXPECT_EQ(hash_combine(a, b),
 215             hash_combine(c, b));
 216   // Test order dependence
 217   EXPECT_NE(hash_combine(a, b),
 218             hash_combine(b, a));
 219
 220   // Test with custom hasher
 221   EXPECT_EQ(hash_combine_test(a),
 222             hash_combine_test(c));
 223   // 3 + 4 != 1 + 2
 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));
 229   // With composition
 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));
 238 }
 239
 240 TEST(Hash, hash_combine) {
 241   EXPECT_NE(hash_combine(1, 2), hash_combine(2, 1));
 242 }
 243
 244 TEST(Hash, hash_bool) {
 245   const auto hash = folly::Hash();
 246   EXPECT_NE(hash(true), hash(false));
 247 }
 248
 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}) {
 262                       values.insert(
 263                           hash(b1, b2, b3, b4, b5, b6, b7, b8, b9, b10));
 264                     }
 265                   }
 266                 }
 267               }
 268             }
 269           }
 270         }
 271       }
 272     }
 273   }
 274   EXPECT_EQ(values.size(), 1 << 10);
 275 }
 276
 277 TEST(Hash, std_tuple) {
 278   typedef std::tuple<int64_t, std::string, int32_t> tuple3;
 279   tuple3 t(42, "foo", 1);
 280
 281   std::unordered_map<tuple3, std::string> m;
 282   m[t] = "bar";
 283   EXPECT_EQ("bar", m[t]);
 284 }
 285
 286 TEST(Hash, enum_type) {
 287   const auto hash = folly::Hash();
 288
 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));
 293
 294   std::unordered_map<Enum32, std::string, folly::Hash> m32;
 295   m32[Enum32::Foo] = "foo";
 296   EXPECT_EQ("foo", m32[Enum32::Foo]);
 297
 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));
 302
 303   std::unordered_map<Enum64, std::string, folly::Hash> m64;
 304   m64[Enum64::Foo] = "foo";
 305   EXPECT_EQ("foo", m64[Enum64::Foo]);
 306 }
 307
 308 TEST(Hash, pair_folly_hash) {
 309   typedef std::pair<int64_t, int32_t> pair2;
 310   pair2 p(42, 1);
 311
 312   std::unordered_map<pair2, std::string, folly::Hash> m;
 313   m[p] = "bar";
 314   EXPECT_EQ("bar", m[p]);
 315 }
 316
 317 TEST(Hash, tuple_folly_hash) {
 318   typedef std::tuple<int64_t, int32_t, int32_t> tuple3;
 319   tuple3 t(42, 1, 1);
 320
 321   std::unordered_map<tuple3, std::string, folly::Hash> m;
 322   m[t] = "bar";
 323   EXPECT_EQ("bar", m[t]);
 324 }
 325
 326 namespace {
 327 template <class T>
 328 size_t hash_vector(const std::vector<T>& v) {
 329   return hash_range(v.begin(), v.end());
 330 }
 331 }
 332
 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>({}));
 337 }
 338
 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);
 344
 345   EXPECT_NE(std::hash<tuple3>()(t1),
 346             std::hash<tuple3>()(t2));
 347   EXPECT_NE(std::hash<tuple3>()(t1),
 348             std::hash<tuple3>()(t3));
 349 }
 350
 351 TEST(Hash, Strings) {
 352   using namespace folly;
 353
 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");
 360   Hash h2;
 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));
 372
 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()));
 378 }