folly/Hash.h

   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 #pragma once
  18
  19 #include <cstdint>
  20 #include <cstring>
  21 #include <limits>
  22 #include <string>
  23 #include <tuple>
  24 #include <type_traits>
  25 #include <utility>
  26
  27 #include <folly/ApplyTuple.h>
  28 #include <folly/Bits.h>
  29 #include <folly/SpookyHashV1.h>
  30 #include <folly/SpookyHashV2.h>
  31
  32 /*
  33  * Various hashing functions.
  34  */
  35
  36 namespace folly { namespace hash {
  37
  38 // This is a general-purpose way to create a single hash from multiple
  39 // hashable objects. hash_combine_generic takes a class Hasher implementing
  40 // hash<T>; hash_combine uses a default hasher StdHasher that uses std::hash.
  41 // hash_combine_generic hashes each argument and combines those hashes in
  42 // an order-dependent way to yield a new hash.
  43
  44
  45 // This is the Hash128to64 function from Google's cityhash (available
  46 // under the MIT License).  We use it to reduce multiple 64 bit hashes
  47 // into a single hash.
  48 inline uint64_t hash_128_to_64(const uint64_t upper, const uint64_t lower) {
  49   // Murmur-inspired hashing.
  50   const uint64_t kMul = 0x9ddfea08eb382d69ULL;
  51   uint64_t a = (lower ^ upper) * kMul;
  52   a ^= (a >> 47);
  53   uint64_t b = (upper ^ a) * kMul;
  54   b ^= (b >> 47);
  55   b *= kMul;
  56   return b;
  57 }
  58
  59 // Never used, but gcc demands it.
  60 template <class Hasher>
  61 inline size_t hash_combine_generic() {
  62   return 0;
  63 }
  64
  65 template <
  66     class Iter,
  67     class Hash = std::hash<typename std::iterator_traits<Iter>::value_type>>
  68 uint64_t hash_range(Iter begin,
  69                     Iter end,
  70                     uint64_t hash = 0,
  71                     Hash hasher = Hash()) {
  72   for (; begin != end; ++begin) {
  73     hash = hash_128_to_64(hash, hasher(*begin));
  74   }
  75   return hash;
  76 }
  77
  78 inline uint32_t twang_32from64(uint64_t key);
  79
  80 template <class Hasher, typename T, typename... Ts>
  81 size_t hash_combine_generic(const T& t, const Ts&... ts) {
  82   size_t seed = Hasher::hash(t);
  83   if (sizeof...(ts) == 0) {
  84     return seed;
  85   }
  86   size_t remainder = hash_combine_generic<Hasher>(ts...);
  87   /* static */ if (sizeof(size_t) == sizeof(uint32_t)) {
  88     return twang_32from64((uint64_t(seed) << 32) | remainder);
  89   } else {
  90     return static_cast<size_t>(hash_128_to_64(seed, remainder));
  91   }
  92 }
  93
  94 // Simply uses std::hash to hash.  Note that std::hash is not guaranteed
  95 // to be a very good hash function; provided std::hash doesn't collide on
  96 // the individual inputs, you are fine, but that won't be true for, say,
  97 // strings or pairs
  98 class StdHasher {
  99  public:
 100   template <typename T>
 101   static size_t hash(const T& t) {
 102     return std::hash<T>()(t);
 103   }
 104 };
 105
 106 template <typename T, typename... Ts>
 107 size_t hash_combine(const T& t, const Ts&... ts) {
 108   return hash_combine_generic<StdHasher>(t, ts...);
 109 }
 110
 111 //////////////////////////////////////////////////////////////////////
 112
 113 /*
 114  * Thomas Wang 64 bit mix hash function
 115  */
 116
 117 inline uint64_t twang_mix64(uint64_t key) {
 118   key = (~key) + (key << 21);  // key *= (1 << 21) - 1; key -= 1;
 119   key = key ^ (key >> 24);
 120   key = key + (key << 3) + (key << 8);  // key *= 1 + (1 << 3) + (1 << 8)
 121   key = key ^ (key >> 14);
 122   key = key + (key << 2) + (key << 4);  // key *= 1 + (1 << 2) + (1 << 4)
 123   key = key ^ (key >> 28);
 124   key = key + (key << 31);  // key *= 1 + (1 << 31)
 125   return key;
 126 }
 127
 128 /*
 129  * Inverse of twang_mix64
 130  *
 131  * Note that twang_unmix64 is significantly slower than twang_mix64.
 132  */
 133
 134 inline uint64_t twang_unmix64(uint64_t key) {
 135   // See the comments in jenkins_rev_unmix32 for an explanation as to how this
 136   // was generated
 137   key *= 4611686016279904257U;
 138   key ^= (key >> 28) ^ (key >> 56);
 139   key *= 14933078535860113213U;
 140   key ^= (key >> 14) ^ (key >> 28) ^ (key >> 42) ^ (key >> 56);
 141   key *= 15244667743933553977U;
 142   key ^= (key >> 24) ^ (key >> 48);
 143   key = (key + 1) * 9223367638806167551U;
 144   return key;
 145 }
 146
 147 /*
 148  * Thomas Wang downscaling hash function
 149  */
 150
 151 inline uint32_t twang_32from64(uint64_t key) {
 152   key = (~key) + (key << 18);
 153   key = key ^ (key >> 31);
 154   key = key * 21;
 155   key = key ^ (key >> 11);
 156   key = key + (key << 6);
 157   key = key ^ (key >> 22);
 158   return (uint32_t) key;
 159 }
 160
 161 /*
 162  * Robert Jenkins' reversible 32 bit mix hash function
 163  */
 164
 165 inline uint32_t jenkins_rev_mix32(uint32_t key) {
 166   key += (key << 12);  // key *= (1 + (1 << 12))
 167   key ^= (key >> 22);
 168   key += (key << 4);   // key *= (1 + (1 << 4))
 169   key ^= (key >> 9);
 170   key += (key << 10);  // key *= (1 + (1 << 10))
 171   key ^= (key >> 2);
 172   // key *= (1 + (1 << 7)) * (1 + (1 << 12))
 173   key += (key << 7);
 174   key += (key << 12);
 175   return key;
 176 }
 177
 178 /*
 179  * Inverse of jenkins_rev_mix32
 180  *
 181  * Note that jenkinks_rev_unmix32 is significantly slower than
 182  * jenkins_rev_mix32.
 183  */
 184
 185 inline uint32_t jenkins_rev_unmix32(uint32_t key) {
 186   // These are the modular multiplicative inverses (in Z_2^32) of the
 187   // multiplication factors in jenkins_rev_mix32, in reverse order.  They were
 188   // computed using the Extended Euclidean algorithm, see
 189   // http://en.wikipedia.org/wiki/Modular_multiplicative_inverse
 190   key *= 2364026753U;
 191
 192   // The inverse of a ^= (a >> n) is
 193   // b = a
 194   // for (int i = n; i < 32; i += n) {
 195   //   b ^= (a >> i);
 196   // }
 197   key ^=
 198     (key >> 2) ^ (key >> 4) ^ (key >> 6) ^ (key >> 8) ^
 199     (key >> 10) ^ (key >> 12) ^ (key >> 14) ^ (key >> 16) ^
 200     (key >> 18) ^ (key >> 20) ^ (key >> 22) ^ (key >> 24) ^
 201     (key >> 26) ^ (key >> 28) ^ (key >> 30);
 202   key *= 3222273025U;
 203   key ^= (key >> 9) ^ (key >> 18) ^ (key >> 27);
 204   key *= 4042322161U;
 205   key ^= (key >> 22);
 206   key *= 16773121U;
 207   return key;
 208 }
 209
 210 /*
 211  * Fowler / Noll / Vo (FNV) Hash
 212  *     http://www.isthe.com/chongo/tech/comp/fnv/
 213  */
 214
 215 const uint32_t FNV_32_HASH_START = 2166136261UL;
 216 const uint64_t FNV_64_HASH_START = 14695981039346656037ULL;
 217
 218 inline uint32_t fnv32(const char* s,
 219                       uint32_t hash = FNV_32_HASH_START) {
 220   for (; *s; ++s) {
 221     hash += (hash << 1) + (hash << 4) + (hash << 7) +
 222             (hash << 8) + (hash << 24);
 223     hash ^= *s;
 224   }
 225   return hash;
 226 }
 227
 228 inline uint32_t fnv32_buf(const void* buf,
 229                           size_t n,
 230                           uint32_t hash = FNV_32_HASH_START) {
 231   // forcing signed char, since other platforms can use unsigned
 232   const signed char* char_buf = reinterpret_cast<const signed char*>(buf);
 233
 234   for (size_t i = 0; i < n; ++i) {
 235     hash += (hash << 1) + (hash << 4) + (hash << 7) +
 236             (hash << 8) + (hash << 24);
 237     hash ^= char_buf[i];
 238   }
 239
 240   return hash;
 241 }
 242
 243 inline uint32_t fnv32(const std::string& str,
 244                       uint32_t hash = FNV_32_HASH_START) {
 245   return fnv32_buf(str.data(), str.size(), hash);
 246 }
 247
 248 inline uint64_t fnv64(const char* s,
 249                       uint64_t hash = FNV_64_HASH_START) {
 250   for (; *s; ++s) {
 251     hash += (hash << 1) + (hash << 4) + (hash << 5) + (hash << 7) +
 252       (hash << 8) + (hash << 40);
 253     hash ^= *s;
 254   }
 255   return hash;
 256 }
 257
 258 inline uint64_t fnv64_buf(const void* buf,
 259                           size_t n,
 260                           uint64_t hash = FNV_64_HASH_START) {
 261   // forcing signed char, since other platforms can use unsigned
 262   const signed char* char_buf = reinterpret_cast<const signed char*>(buf);
 263
 264   for (size_t i = 0; i < n; ++i) {
 265     hash += (hash << 1) + (hash << 4) + (hash << 5) + (hash << 7) +
 266       (hash << 8) + (hash << 40);
 267     hash ^= char_buf[i];
 268   }
 269   return hash;
 270 }
 271
 272 inline uint64_t fnv64(const std::string& str,
 273                       uint64_t hash = FNV_64_HASH_START) {
 274   return fnv64_buf(str.data(), str.size(), hash);
 275 }
 276
 277 /*
 278  * Paul Hsieh: http://www.azillionmonkeys.com/qed/hash.html
 279  */
 280
 281 #define get16bits(d) folly::loadUnaligned<uint16_t>(d)
 282
 283 inline uint32_t hsieh_hash32_buf(const void* buf, size_t len) {
 284   // forcing signed char, since other platforms can use unsigned
 285   const unsigned char* s = reinterpret_cast<const unsigned char*>(buf);
 286   uint32_t hash = static_cast<uint32_t>(len);
 287   uint32_t tmp;
 288   size_t rem;
 289
 290   if (len <= 0 || buf == 0) {
 291     return 0;
 292   }
 293
 294   rem = len & 3;
 295   len >>= 2;
 296
 297   /* Main loop */
 298   for (;len > 0; len--) {
 299     hash  += get16bits (s);
 300     tmp    = (get16bits (s+2) << 11) ^ hash;
 301     hash   = (hash << 16) ^ tmp;
 302     s  += 2*sizeof (uint16_t);
 303     hash  += hash >> 11;
 304   }
 305
 306   /* Handle end cases */
 307   switch (rem) {
 308   case 3:
 309     hash += get16bits(s);
 310     hash ^= hash << 16;
 311     hash ^= s[sizeof (uint16_t)] << 18;
 312     hash += hash >> 11;
 313     break;
 314   case 2:
 315     hash += get16bits(s);
 316     hash ^= hash << 11;
 317     hash += hash >> 17;
 318     break;
 319   case 1:
 320     hash += *s;
 321     hash ^= hash << 10;
 322     hash += hash >> 1;
 323   }
 324
 325   /* Force "avalanching" of final 127 bits */
 326   hash ^= hash << 3;
 327   hash += hash >> 5;
 328   hash ^= hash << 4;
 329   hash += hash >> 17;
 330   hash ^= hash << 25;
 331   hash += hash >> 6;
 332
 333   return hash;
 334 };
 335
 336 #undef get16bits
 337
 338 inline uint32_t hsieh_hash32(const char* s) {
 339   return hsieh_hash32_buf(s, std::strlen(s));
 340 }
 341
 342 inline uint32_t hsieh_hash32_str(const std::string& str) {
 343   return hsieh_hash32_buf(str.data(), str.size());
 344 }
 345
 346 //////////////////////////////////////////////////////////////////////
 347
 348 } // namespace hash
 349
 350 template<class Key, class Enable = void>
 351 struct hasher;
 352
 353 struct Hash {
 354   template <class T>
 355   size_t operator()(const T& v) const {
 356     return hasher<T>()(v);
 357   }
 358
 359   template <class T, class... Ts>
 360   size_t operator()(const T& t, const Ts&... ts) const {
 361     return hash::hash_128_to_64((*this)(t), (*this)(ts...));
 362   }
 363 };
 364
 365 template <>
 366 struct hasher<bool> {
 367   size_t operator()(bool key) const {
 368     // Make sure that all the output bits depend on the input.
 369     return key ? std::numeric_limits<size_t>::max() : 0;
 370   }
 371 };
 372
 373 template<> struct hasher<int32_t> {
 374   size_t operator()(int32_t key) const {
 375     return hash::jenkins_rev_mix32(uint32_t(key));
 376   }
 377 };
 378
 379 template<> struct hasher<uint32_t> {
 380   size_t operator()(uint32_t key) const {
 381     return hash::jenkins_rev_mix32(key);
 382   }
 383 };
 384
 385 template<> struct hasher<int16_t> {
 386   size_t operator()(int16_t key) const {
 387     return hasher<int32_t>()(key); // as impl accident, sign-extends
 388   }
 389 };
 390
 391 template<> struct hasher<uint16_t> {
 392   size_t operator()(uint16_t key) const {
 393     return hasher<uint32_t>()(key);
 394   }
 395 };
 396
 397 template<> struct hasher<int8_t> {
 398   size_t operator()(int8_t key) const {
 399     return hasher<int32_t>()(key); // as impl accident, sign-extends
 400   }
 401 };
 402
 403 template<> struct hasher<uint8_t> {
 404   size_t operator()(uint8_t key) const {
 405     return hasher<uint32_t>()(key);
 406   }
 407 };
 408
 409 template<> struct hasher<char> {
 410   using explicit_type =
 411       std::conditional<std::is_signed<char>::value, int8_t, uint8_t>::type;
 412   size_t operator()(char key) const {
 413     return hasher<explicit_type>()(key); // as impl accident, sign-extends
 414   }
 415 };
 416
 417 template<> struct hasher<int64_t> {
 418   size_t operator()(int64_t key) const {
 419     return static_cast<size_t>(hash::twang_mix64(uint64_t(key)));
 420   }
 421 };
 422
 423 template<> struct hasher<uint64_t> {
 424   size_t operator()(uint64_t key) const {
 425     return static_cast<size_t>(hash::twang_mix64(key));
 426   }
 427 };
 428
 429 template<> struct hasher<std::string> {
 430   size_t operator()(const std::string& key) const {
 431     return static_cast<size_t>(
 432         hash::SpookyHashV2::Hash64(key.data(), key.size(), 0));
 433   }
 434 };
 435
 436 template <class T>
 437 struct hasher<T, typename std::enable_if<std::is_enum<T>::value, void>::type> {
 438   size_t operator()(T key) const {
 439     return Hash()(static_cast<typename std::underlying_type<T>::type>(key));
 440   }
 441 };
 442
 443 template <class T1, class T2>
 444 struct hasher<std::pair<T1, T2>> {
 445   size_t operator()(const std::pair<T1, T2>& key) const {
 446     return Hash()(key.first, key.second);
 447   }
 448 };
 449
 450 template <typename... Ts>
 451 struct hasher<std::tuple<Ts...>> {
 452   size_t operator() (const std::tuple<Ts...>& key) const {
 453     return applyTuple(Hash(), key);
 454   }
 455 };
 456
 457 // recursion
 458 template <size_t index, typename... Ts>
 459 struct TupleHasher {
 460   size_t operator()(std::tuple<Ts...> const& key) const {
 461     return hash::hash_combine(
 462       TupleHasher<index - 1, Ts...>()(key),
 463       std::get<index>(key));
 464   }
 465 };
 466
 467 // base
 468 template <typename... Ts>
 469 struct TupleHasher<0, Ts...> {
 470   size_t operator()(std::tuple<Ts...> const& key) const {
 471     // we could do std::hash here directly, but hash_combine hides all the
 472     // ugly templating implicitly
 473     return hash::hash_combine(std::get<0>(key));
 474   }
 475 };
 476
 477 } // namespace folly
 478
 479 // Custom hash functions.
 480 namespace std {
 481   // Hash function for pairs. Requires default hash functions for both
 482   // items in the pair.
 483   template <typename T1, typename T2>
 484   struct hash<std::pair<T1, T2> > {
 485   public:
 486     size_t operator()(const std::pair<T1, T2>& x) const {
 487       return folly::hash::hash_combine(x.first, x.second);
 488     }
 489   };
 490
 491   // Hash function for tuples. Requires default hash functions for all types.
 492   template <typename... Ts>
 493   struct hash<std::tuple<Ts...>> {
 494     size_t operator()(std::tuple<Ts...> const& key) const {
 495       folly::TupleHasher<
 496         std::tuple_size<std::tuple<Ts...>>::value - 1, // start index
 497         Ts...> hasher;
 498
 499       return hasher(key);
 500     }
 501   };
 502 } // namespace std