en	﻿[#hash_quality] = Hash Quality

en	:idprefix: hash_quality_

en	In order to work properly, hash tables require that the supplied hash function be of __good quality__, roughly meaning that it uses its `std::size_t` output space as uniformly as possible, much like a random number generator would do —except, of course, that the value of a hash function is not random but strictly determined by its input argument.

en	Closed-addressing containers in Boost.Unordered are fairly robust against hash functions with less-than-ideal quality, but open-addressing and concurrent containers are much more sensitive to this factor, and their performance can degrade dramatically if the hash function is not appropriate. In general, if you're using functions provided by or generated with link:../../../../container_hash/index.html[Boost.Hash^], the quality will be adequate, but you have to be careful when using alternative hash algorithms.

en	The rest of this section applies only to open-addressing and concurrent containers.

en	Hash Post-mixing and the Avalanching Property

en	Even if your supplied hash function does not conform to the uniform behavior required by open addressing, chances are that the performance of Boost.Unordered containers will be acceptable, because the library executes an internal __post-mixing__ step that improves the statistical properties of the calculated hash values. This comes with an extra computational cost; if you'd like to opt out of post-mixing, annotate your hash function as follows:

en	By setting the `link:../../../../container_hash/doc/html/hash.html#ref_hash_is_avalanchinghash[hash_is_avalanching]` trait, we inform Boost.Unordered that `my_string_hash_function` is of sufficient quality to be used directly without any post-mixing safety net. This comes at the risk of degraded performance in the cases where the hash function is not as well-behaved as we've declared.

en	Container Statistics

en	If we globally define the macro `BOOST_UNORDERED_ENABLE_STATS`, open-addressing and concurrent containers will calculate some internal statistics directly correlated to the quality of the hash function:

en	The `stats` object provides the following information:

en	Statistics for three internal operations are maintained: insertions (without considering the previous lookup to determine that the key is not present yet), successful lookups, and unsuccessful lookups (including those issued internally when inserting elements). _Probe length_ is the number of xref:structures.adoc#structures_open_addressing_containers[bucket groups] accessed per operation. If the hash function behaves properly:

en	Average probe lengths should be close to 1.0.

en	The average number of comparisons per successful lookup should be close to 1.0 (that is,

en	just the element found is checked).

en	The average number of comparisons per unsuccessful lookup should be close to 0.0.

en	An link:../../../benchmark/string_stats.cpp[example^] is provided that displays container statistics for `boost::hash<std::string>`, an implementation of the https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function#FNV-1a_hash[FNV-1a hash^] and two ill-behaved custom hash functions that have been incorrectly marked as avalanching: