Hash Traits

<boost/unordered/hash_traits.hpp> Synopsis

namespace boost {
namespace unordered {

template<typename Hash>
struct hash_is_avalanching;

} // namespace unordered
} // namespace boost

hash_is_avalanching

template<typename Hash>
struct hash_is_avalanching;

A hash function is said to have the avalanching property if small changes in the input translate to large changes in the returned hash code —ideally, flipping one bit in the representation of the input value results in each bit of the hash code flipping with probability 50%. Approaching this property is critical for the proper behavior of open-addressing hash containers.

hash_is_avalanching<Hash>::value is:

  • false if Hash::is_avalanching is not present,

  • Hash::is_avalanching::value if this is present and convertible at compile time to a bool,

  • true if Hash::is_avalanching is void (this usage is deprecated),

  • ill-formed otherwise.

Users can then declare a hash function Hash as avalanching either by embedding an appropriate is_avalanching typedef into the definition of Hash, or directly by specializing hash_is_avalanching<Hash> to a class with an embedded compile-time constant value set to true.

Open-addressing and concurrent containers use the provided hash function Hash as-is if hash_is_avalanching<Hash>::value is true; otherwise, they implement a bit-mixing post-processing stage to increase the quality of hashing at the expense of extra computational cost.