folly::hash Namespace Reference

Namespaces
	detail

Classes
class	SpookyHashV1
class	SpookyHashV2
class	StdHasher

Functions
uint64_t	hash_128_to_64 (const uint64_t upper, const uint64_t lower) noexcept
uint64_t	twang_mix64 (uint64_t key) noexcept
uint64_t	twang_unmix64 (uint64_t key) noexcept
uint32_t	twang_32from64 (uint64_t key) noexcept
uint32_t	jenkins_rev_mix32 (uint32_t key) noexcept
uint32_t	jenkins_rev_unmix32 (uint32_t key) noexcept
uint32_t	fnv32 (const char *buf, uint32_t hash=FNV_32_HASH_START) noexcept
uint32_t	fnv32_buf (const void *buf, size_t n, uint32_t hash=FNV_32_HASH_START) noexcept
uint32_t	fnv32 (const std::string &str, uint32_t hash=FNV_32_HASH_START) noexcept
uint64_t	fnv64 (const char *buf, uint64_t hash=FNV_64_HASH_START) noexcept
uint64_t	fnv64_buf (const void *buf, size_t n, uint64_t hash=FNV_64_HASH_START) noexcept
uint64_t	fnv64 (const std::string &str, uint64_t hash=FNV_64_HASH_START) noexcept
uint64_t	fnva64_buf (const void *buf, size_t n, uint64_t hash=FNVA_64_HASH_START) noexcept
uint64_t	fnva64 (const std::string &str, uint64_t hash=FNVA_64_HASH_START) noexcept
uint32_t	hsieh_hash32_buf (const void *buf, size_t len) noexcept
uint32_t	hsieh_hash32 (const char *s) noexcept
uint32_t	hsieh_hash32_str (const std::string &str) noexcept
template<class Hash , class Value >
uint64_t	commutative_hash_combine_value_generic (uint64_t seed, Hash const &hasher, Value const &value)
template<class Iter , class Hash = std::hash<typename std::iterator_traits<Iter>::value_type>>
uint64_t	hash_range (Iter begin, Iter end, uint64_t hash=0, Hash hasher=Hash())
template<class Hash , class Iter >
uint64_t	commutative_hash_combine_range_generic (uint64_t seed, Hash const &hasher, Iter first, Iter last)
template<class Iter >
uint64_t	commutative_hash_combine_range (Iter first, Iter last)
template<class Hasher >
size_t	hash_combine_generic (const Hasher &) noexcept
template<class Hasher , typename T , typename... Ts>
size_t	hash_combine_generic (const Hasher &h, const T &t, const Ts &...ts) noexcept(noexcept(detail::c_array_size_t{h(t), h(ts)...}))
template<typename Hash , typename... Value>
uint64_t	commutative_hash_combine_generic (uint64_t seed, Hash const &hasher, Value const &...value)
template<typename T , typename... Ts>
size_t	hash_combine (const T &t, const Ts &...ts) noexcept(noexcept(hash_combine_generic(StdHasher{}, t, ts...)))
template<typename... Value>
uint64_t	commutative_hash_combine (Value const &...value)

Variables
const uint32_t	FNV_32_HASH_START = 2166136261UL
const uint64_t	FNV_64_HASH_START = 14695981039346656037ULL
const uint64_t	FNVA_64_HASH_START = 14695981039346656037ULL

Function Documentation

template<typename... Value>

uint64_t folly::hash::commutative_hash_combine

(

Value const &...

value

)

Definition at line 675 of file Hash.h.

References commutative_hash_combine_generic().

Referenced by TEST().

                                                         {
  return commutative_hash_combine_generic(0, Hash{}, value...);
}

template<typename Hash , typename... Value>

uint64_t folly::hash::commutative_hash_combine_generic	(	uint64_t	seed,
		Hash const &	hasher,
		Value const &...	value
	)

Definition at line 657 of file Hash.h.

References testing::_, commutative_hash_combine_value_generic(), seed, folly::T, and uint64_t.

Referenced by commutative_hash_combine().

                           {
  // variadic foreach:
  uint64_t _[] = {
      0, seed = commutative_hash_combine_value_generic(seed, hasher, value)...};
  (void)_;
  return seed;
}

template<class Iter >

uint64_t folly::hash::commutative_hash_combine_range	(	Iter	first,
		Iter	last
	)

Definition at line 624 of file Hash.h.

References commutative_hash_combine_range_generic(), and folly::gen::first.

Referenced by TEST().

                                                               {
  return commutative_hash_combine_range_generic(0, Hash{}, first, last);
}

template<class Hash , class Iter >

uint64_t folly::hash::commutative_hash_combine_range_generic	(	uint64_t	seed,
		Hash const &	hasher,
		Iter	first,
		Iter	last
	)

Definition at line 612 of file Hash.h.

References commutative_hash_combine_value_generic(), and seed.

Referenced by commutative_hash_combine_range(), and TEST().

               {
  while (first != last) {
    seed = commutative_hash_combine_value_generic(seed, hasher, *first++);
  }
  return seed;
}

template<class Hash , class Value >

uint64_t folly::hash::commutative_hash_combine_value_generic	(	uint64_t	seed,
		Hash const &	hasher,
		Value const &	value
	)

Definition at line 584 of file Hash.h.

References gen_gtest_pred_impl::Iter(), twang_mix64(), and uint64_t.

Referenced by commutative_hash_combine_generic(), commutative_hash_combine_range_generic(), and TEST().

                        {
  auto const x = hasher(value);
  auto const y = IsAvalanchingHasher<Hash, Value>::value ? x : twang_mix64(x);
  // Commutative accumulator taken from this paper:
  // https://www.preprints.org/manuscript/201710.0192/v1/download
  return 3860031 + (seed + y) * 2779 + (seed * y * 2);
}

uint32_t folly::hash::fnv32 ( const char *  buf, uint32_t  hash = FNV_32_HASH_START  )

inlinenoexcept

Definition at line 149 of file Hash.h.

References s.

Referenced by TEST().

                                                {
  // forcing signed char, since other platforms can use unsigned
  const signed char* s = reinterpret_cast<const signed char*>(buf);

  for (; *s; ++s) {
    hash +=
        (hash << 1) + (hash << 4) + (hash << 7) + (hash << 8) + (hash << 24);
    hash ^= *s;
  }
  return hash;
}

uint32_t folly::hash::fnv32 ( const std::string &  str, uint32_t  hash = FNV_32_HASH_START  )

inlinenoexcept

Definition at line 179 of file Hash.h.

References fnv32_buf().

                                                {
  return fnv32_buf(str.data(), str.size(), hash);
}

uint32_t folly::hash::fnv32_buf ( const void *  buf, size_t  n, uint32_t  hash = FNV_32_HASH_START  )

inlinenoexcept

Definition at line 163 of file Hash.h.

References i.

Referenced by fnv32(), folly::IPAddressV4::hash(), and TEST().

                                                {
  // forcing signed char, since other platforms can use unsigned
  const signed char* char_buf = reinterpret_cast<const signed char*>(buf);

  for (size_t i = 0; i < n; ++i) {
    hash +=
        (hash << 1) + (hash << 4) + (hash << 7) + (hash << 8) + (hash << 24);
    hash ^= char_buf[i];
  }

  return hash;
}

uint64_t folly::hash::fnv64 ( const char *  buf, uint64_t  hash = FNV_64_HASH_START  )

inlinenoexcept

Definition at line 185 of file Hash.h.

References s.

Referenced by TEST().

                                                {
  // forcing signed char, since other platforms can use unsigned
  const signed char* s = reinterpret_cast<const signed char*>(buf);

  for (; *s; ++s) {
    hash += (hash << 1) + (hash << 4) + (hash << 5) + (hash << 7) +
        (hash << 8) + (hash << 40);
    hash ^= *s;
  }
  return hash;
}

uint64_t folly::hash::fnv64 ( const std::string &  str, uint64_t  hash = FNV_64_HASH_START  )

inlinenoexcept

Definition at line 214 of file Hash.h.

References fnv64_buf().

                                                {
  return fnv64_buf(str.data(), str.size(), hash);
}

uint64_t folly::hash::fnv64_buf ( const void *  buf, size_t  n, uint64_t  hash = FNV_64_HASH_START  )

inlinenoexcept

Definition at line 199 of file Hash.h.

References i.

Referenced by proxygen::RendezvousHash::computeHash(), fnv64(), folly::io::test::DataHolder::hash(), folly::io::test::hashIOBuf(), main(), detail::FNV64::operator()(), and TEST().

                                                {
  // forcing signed char, since other platforms can use unsigned
  const signed char* char_buf = reinterpret_cast<const signed char*>(buf);

  for (size_t i = 0; i < n; ++i) {
    hash += (hash << 1) + (hash << 4) + (hash << 5) + (hash << 7) +
        (hash << 8) + (hash << 40);
    hash ^= char_buf[i];
  }
  return hash;
}

uint64_t folly::hash::fnva64 ( const std::string &  str, uint64_t  hash = FNVA_64_HASH_START  )

inlinenoexcept

Definition at line 234 of file Hash.h.

References fnva64_buf().

Referenced by TEST_P().

                                                 {
  return fnva64_buf(str.data(), str.size(), hash);
}

uint64_t folly::hash::fnva64_buf ( const void *  buf, size_t  n, uint64_t  hash = FNVA_64_HASH_START  )

inlinenoexcept

Definition at line 220 of file Hash.h.

References i, and uint8_t.

Referenced by fnva64(), and TEST_P().

                                                 {
  const uint8_t* char_buf = reinterpret_cast<const uint8_t*>(buf);

  for (size_t i = 0; i < n; ++i) {
    hash ^= char_buf[i];
    hash += (hash << 1) + (hash << 4) + (hash << 5) + (hash << 7) +
        (hash << 8) + (hash << 40);
  }
  return hash;
}

uint64_t folly::hash::hash_128_to_64 ( const uint64_t  upper, const uint64_t  lower  )

inlinenoexcept

Definition at line 570 of file Hash.h.

References a, b, and uint64_t.

Referenced by hash_range(), folly::detail::integral_hasher< signed long long >::operator()(), and folly::Hash::operator()().

                                   {
  // Murmur-inspired hashing.
  const uint64_t kMul = 0x9ddfea08eb382d69ULL;
  uint64_t a = (lower ^ upper) * kMul;
  a ^= (a >> 47);
  uint64_t b = (upper ^ a) * kMul;
  b ^= (b >> 47);
  b *= kMul;
  return b;
}

template<typename T , typename... Ts>

size_t folly::hash::hash_combine ( const T &  t, const Ts &...  ts  )

noexcept

Definition at line 669 of file Hash.h.

References hash_combine_generic(), folly::pushmi::detail::t, and testing::Value().

Referenced by folly::detail::MemoryIdler::getVariationTimeout(), folly::IPAddressV4::hash(), folly::IPAddressV6::hash(), folly::SocketAddress::hash(), wangle::SSLContextKeyHash::operator()(), folly::detail::TypeDescriptorHasher::operator()(), folly::TupleHasher< index, Ts >::operator()(), folly::TupleHasher< 0, Ts... >::operator()(), std::hash< std::pair< T1, T2 > >::operator()(), and TEST().

                                           {}, t, ts...))) {
  return hash_combine_generic(StdHasher{}, t, ts...);
}

template<class Hasher >

size_t folly::hash::hash_combine_generic ( const Hasher &  )

inlinenoexcept

Definition at line 634 of file Hash.h.

References folly::T.

Referenced by hash_combine(), and hash_combine_test().

                                                           {
  return 0;
}

template<class Hasher , typename T , typename... Ts>

size_t folly::hash::hash_combine_generic ( const Hasher &  h, const T &  t, const Ts &...  ts  )

noexcept

Definition at line 639 of file Hash.h.

References h, and folly::pushmi::detail::t.

                                                           {h(t),
                                                              h(ts)...})) {
  size_t seed = h(t);
  if (sizeof...(ts) == 0) {
    return seed;
  }
  size_t remainder = hash_combine_generic(h, ts...);
  if /* constexpr */ (sizeof(size_t) == sizeof(uint32_t)) {
    return twang_32from64((uint64_t(seed) << 32) | remainder);
  } else {
    return static_cast<size_t>(hash_128_to_64(seed, remainder));
  }
}

template<class Iter , class Hash = std::hash<typename std::iterator_traits<Iter>::value_type>>

uint64_t folly::hash::hash_range	(	Iter	begin,
		Iter	end,
		uint64_t	hash = 0,
		Hash	hasher = Hash()
	)

Definition at line 604 of file Hash.h.

References folly::test::begin(), folly::test::end(), and hash_128_to_64().

Referenced by folly::dynamic::hash(), std::hash< StringVector >::operator()(), and TEST().

                                                                          {
  for (; begin != end; ++begin) {
    hash = hash_128_to_64(hash, hasher(*begin));
  }
  return hash;
}

uint32_t folly::hash::hsieh_hash32 ( const char *  s )

inlinenoexcept

Definition at line 301 of file Hash.h.

References hsieh_hash32_buf(), and s.

Referenced by TEST().

                                                     {
  return hsieh_hash32_buf(s, std::strlen(s));
}

uint32_t folly::hash::hsieh_hash32_buf ( const void *  buf, size_t  len  )

inlinenoexcept

Definition at line 246 of file Hash.h.

References get16bits, s, uint16_t, and uint32_t.

Referenced by hsieh_hash32(), hsieh_hash32_str(), and TEST().

                                                                       {
  // forcing signed char, since other platforms can use unsigned
  const unsigned char* s = reinterpret_cast<const unsigned char*>(buf);
  uint32_t hash = static_cast<uint32_t>(len);
  uint32_t tmp;
  size_t rem;

  if (len <= 0 || buf == nullptr) {
    return 0;
  }

  rem = len & 3;
  len >>= 2;

  /* Main loop */
  for (; len > 0; len--) {
    hash += get16bits(s);
    tmp = (get16bits(s + 2) << 11) ^ hash;
    hash = (hash << 16) ^ tmp;
    s += 2 * sizeof(uint16_t);
    hash += hash >> 11;
  }

  /* Handle end cases */
  switch (rem) {
    case 3:
      hash += get16bits(s);
      hash ^= hash << 16;
      hash ^= s[sizeof(uint16_t)] << 18;
      hash += hash >> 11;
      break;
    case 2:
      hash += get16bits(s);
      hash ^= hash << 11;
      hash += hash >> 17;
      break;
    case 1:
      hash += *s;
      hash ^= hash << 10;
      hash += hash >> 1;
  }

  /* Force "avalanching" of final 127 bits */
  hash ^= hash << 3;
  hash += hash >> 5;
  hash ^= hash << 4;
  hash += hash >> 17;
  hash ^= hash << 25;
  hash += hash >> 6;

  return hash;
}

uint32_t folly::hash::hsieh_hash32_str ( const std::string &  str )

inlinenoexcept

Definition at line 305 of file Hash.h.

References hsieh_hash32_buf().

                                                                {
  return hsieh_hash32_buf(str.data(), str.size());
}

uint32_t folly::hash::jenkins_rev_mix32 ( uint32_t  key )

inlinenoexcept

Definition at line 97 of file Hash.h.

Referenced by createEntry(), folly::detail::integral_hasher< signed long long >::operator()(), and TEST().

                                                         {
  key += (key << 12); // key *= (1 + (1 << 12))
  key ^= (key >> 22);
  key += (key << 4); // key *= (1 + (1 << 4))
  key ^= (key >> 9);
  key += (key << 10); // key *= (1 + (1 << 10))
  key ^= (key >> 2);
  // key *= (1 + (1 << 7)) * (1 + (1 << 12))
  key += (key << 7);
  key += (key << 12);
  return key;
}

uint32_t folly::hash::jenkins_rev_unmix32 ( uint32_t  key )

inlinenoexcept

Definition at line 117 of file Hash.h.

Referenced by TEST().

                                                           {
  // These are the modular multiplicative inverses (in Z_2^32) of the
  // multiplication factors in jenkins_rev_mix32, in reverse order.  They were
  // computed using the Extended Euclidean algorithm, see
  // http://en.wikipedia.org/wiki/Modular_multiplicative_inverse
  key *= 2364026753U;

  // The inverse of a ^= (a >> n) is
  // b = a
  // for (int i = n; i < 32; i += n) {
  //   b ^= (a >> i);
  // }
  key ^= (key >> 2) ^ (key >> 4) ^ (key >> 6) ^ (key >> 8) ^ (key >> 10) ^
      (key >> 12) ^ (key >> 14) ^ (key >> 16) ^ (key >> 18) ^ (key >> 20) ^
      (key >> 22) ^ (key >> 24) ^ (key >> 26) ^ (key >> 28) ^ (key >> 30);
  key *= 3222273025U;
  key ^= (key >> 9) ^ (key >> 18) ^ (key >> 27);
  key *= 4042322161U;
  key ^= (key >> 22);
  key *= 16773121U;
  return key;
}

uint32_t folly::hash::twang_32from64 ( uint64_t  key )

inlinenoexcept

Definition at line 83 of file Hash.h.

References uint32_t.

Referenced by folly::HashingThreadId::get(), and TEST().

                                                      {
  key = (~key) + (key << 18);
  key = key ^ (key >> 31);
  key = key * 21;
  key = key ^ (key >> 11);
  key = key + (key << 6);
  key = key ^ (key >> 22);
  return (uint32_t)key;
}

uint64_t folly::hash::twang_mix64 ( uint64_t  key )

inlinenoexcept

Definition at line 49 of file Hash.h.

Referenced by commutative_hash_combine_value_generic(), proxygen::RendezvousHash::computeHash(), folly::detail::MemoryIdler::getVariationTimeout(), folly::SocketAddress::hash(), ShardedAtomicInt::inc(), folly::detail::integral_hasher< signed long long >::operator()(), folly::detail::float_hasher< float >::operator()(), folly::ParkingLot< Data >::park_until(), TEST(), and folly::ParkingLot< Data >::unpark().

                                                   {
  key = (~key) + (key << 21); // key *= (1 << 21) - 1; key -= 1;
  key = key ^ (key >> 24);
  key = key + (key << 3) + (key << 8); // key *= 1 + (1 << 3) + (1 << 8)
  key = key ^ (key >> 14);
  key = key + (key << 2) + (key << 4); // key *= 1 + (1 << 2) + (1 << 4)
  key = key ^ (key >> 28);
  key = key + (key << 31); // key *= 1 + (1 << 31)
  return key;
}

uint64_t folly::hash::twang_unmix64 ( uint64_t  key )

inlinenoexcept

Definition at line 66 of file Hash.h.

Referenced by TEST().

                                                     {
  // See the comments in jenkins_rev_unmix32 for an explanation as to how this
  // was generated
  key *= 4611686016279904257U;
  key ^= (key >> 28) ^ (key >> 56);
  key *= 14933078535860113213U;
  key ^= (key >> 14) ^ (key >> 28) ^ (key >> 42) ^ (key >> 56);
  key *= 15244667743933553977U;
  key ^= (key >> 24) ^ (key >> 48);
  key = (key + 1) * 9223367638806167551U;
  return key;
}

Variable Documentation

const uint32_t folly::hash::FNV_32_HASH_START = 2166136261UL

Definition at line 145 of file Hash.h.

const uint64_t folly::hash::FNV_64_HASH_START = 14695981039346656037ULL

Definition at line 146 of file Hash.h.

Referenced by folly::io::test::hashIOBuf().

const uint64_t folly::hash::FNVA_64_HASH_START = 14695981039346656037ULL

Definition at line 147 of file Hash.h.