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
ifHash::is_avalanching
is not present, -
Hash::is_avalanching::value
if this is present and convertible at compile time to abool
, -
true
ifHash::is_avalanching
isvoid
(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.