folly/test/HashTest.cpp

   1 /*
   2  * Copyright 2013 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 <gtest/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
  43 TEST(Hash, Fnv64) {
  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)));
  48
  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)));
  53
  54   const char* s3 = "";
  55   const uint64_t s3_res = 14695981039346656037ULL;
  56   EXPECT_EQ(fnv64(s3), s3_res);
  57   EXPECT_EQ(fnv64(s3), fnv64_buf(s3, strlen(s3)));
  58
  59   // note: Use fnv64_buf to make a single hash value from multiple
  60   // fields/datatypes.
  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,
  67                                 strlen(t4_a));
  68   uint64_t t4_hash2 = fnv64_buf(reinterpret_cast<void*>(&t4_b),
  69                                 sizeof(int64_t),
  70                                 t4_hash1);
  71   uint64_t t4_hash3 = fnv64_buf(reinterpret_cast<void*>(&t4_c),
  72                                 sizeof(int32_t),
  73                                 t4_hash2);
  74   uint64_t t4_hash4 = fnv64_buf(t4_d,
  75                                 strlen(t4_d),
  76                                 t4_hash3);
  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
  80   // working.
  81   EXPECT_NE(t4_hash1, t4_hash4);
  82   EXPECT_NE(t4_hash2, t4_hash4);
  83   EXPECT_NE(t4_hash3, t4_hash4);
  84 }
  85
  86 TEST(Hash, Hsieh32) {
  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)));
  91
  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)));
  96
  97   const char* s3 = "";
  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)));
 101 }
 102
 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));
 108
 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));
 113 }
 114
 115 namespace {
 116 void checkTWang(uint64_t r) {
 117   uint64_t result = twang_mix64(r);
 118   EXPECT_EQ(r, twang_unmix64(result));
 119 }
 120 }  // namespace
 121
 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);
 126     checkTWang(1U << i);
 127     checkTWang((1U << i) + 1);
 128   }
 129 }
 130
 131 TEST(Hash, TWang_32From64) {
 132   uint64_t i1 = 0x78a87873e2d31dafULL;
 133   uint32_t i1_res = 1525586863ul;
 134   EXPECT_EQ(twang_32from64(i1), i1_res);
 135
 136   uint64_t i2 = 0x0123456789abcdefULL;
 137   uint32_t i2_res = 2918899159ul;
 138   EXPECT_EQ(twang_32from64(i2), i2_res);
 139 }
 140
 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));
 146
 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));
 151 }
 152
 153 namespace {
 154 void checkJenkins(uint32_t r) {
 155   uint32_t result = jenkins_rev_mix32(r);
 156   EXPECT_EQ(r, jenkins_rev_unmix32(result));
 157 }
 158 }  // namespace
 159
 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);
 166   }
 167 }
 168
 169 TEST(Hash, hasher) {
 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);
 174 }
 175
 176 // Not a full hasher since only handles one type
 177 class TestHasher {
 178  public:
 179   static size_t hash(const std::pair<int, int>& p) {
 180     return p.first + p.second;
 181   }
 182 };
 183
 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...);
 187 }
 188
 189 TEST(Hash, pair) {
 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),
 195             hash_combine(c));
 196   EXPECT_NE(hash_combine(b),
 197             hash_combine(c));
 198   EXPECT_NE(hash_combine(d),
 199             hash_combine(c));
 200
 201   // With composition
 202   EXPECT_EQ(hash_combine(a, b),
 203             hash_combine(c, b));
 204   // Test order dependence
 205   EXPECT_NE(hash_combine(a, b),
 206             hash_combine(b, a));
 207
 208   // Test with custom hasher
 209   EXPECT_EQ(hash_combine_test(a),
 210             hash_combine_test(c));
 211   // 3 + 4 != 1 + 2
 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));
 217   // With composition
 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));
 226 }
 227
 228 TEST(Hash, hash_combine) {
 229   EXPECT_NE(hash_combine(1, 2), hash_combine(2, 1));
 230 }
 231
 232 TEST(Hash, std_tuple) {
 233   typedef std::tuple<int64_t, std::string, int32_t> tuple3;
 234   tuple3 t(42, "foo", 1);
 235
 236   std::unordered_map<tuple3, std::string> m;
 237   m[t] = "bar";
 238   EXPECT_EQ("bar", m[t]);
 239 }
 240
 241 TEST(Hash, std_tuple_different_hash) {
 242   typedef std::tuple<int64_t, std::string, int32_t> tuple3;
 243   tuple3 t1(42, "foo", 1);
 244   tuple3 t2(9, "bar", 3);
 245   tuple3 t3(42, "foo", 3);
 246
 247   EXPECT_NE(std::hash<tuple3>()(t1),
 248             std::hash<tuple3>()(t2));
 249   EXPECT_NE(std::hash<tuple3>()(t1),
 250             std::hash<tuple3>()(t3));
 251 }