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