I would like to propose adding an identity_hash that stores its input bytes as result.
class identity_hash
{
std::size_t m_state;
public:
static constexpr xstd::endian endian = xstd::endian::native;
using result_type = std::size_t;
constexpr void operator()(void const* key, std::size_t /* len */) noexcept
{
m_state = *static_cast<result_type const*>(key);
}
explicit constexpr operator result_type() const noexcept
{
return m_state;
}
};
The use cases for this simple hash function are for thin wrapper classes around regular value types that cache their hash keys. E.g. below is a sketch of such a wrapper class that holds a value and its hash key. This key can be computed in the wrapper's constructor by xstd::uhash using any full-fledged hash function (fnv1a here, but also Murmur, City or even std::hash).
template<class T, class InternalHash = acme::fnv1a>
class wrap
{
T m_value;
typename InternalHash::result_type m_hash;
public:
explicit wrap(T const& u) noexcept
: m_value{u}
, m_hash{xstd::uhash<InternalHash>{}(m_value)}
{}
template<class ExternalHash>
friend void hash_append(ExternalHash& h, wrap const& w)
{
static_assert(std::is_same<ExternalHash, acme::identity_hash>{});
using xstd::hash_append;
hash_append(h, w.m_hash);
}
};
Once the key has been computed and wrapped, the wrapper object itself can be stored inside a std::unordered_set<wrap, xstd::uhash<acme::identity_hash>>. This saves recomputing the hash key.
The proposed identity_hash would enable the hash_append framework for these type of data structures. This also paves the way for (but does not depend on) using a tabulation hashing algorithm (where the key is incrementally updated when the wrapped value is mutated; caching the key is required in order to achieve this).
Applications are e.g. chess engines, where the wrapped type represents the full chess Position object. Storing the hash key and incrementally updating it as the underlying position changes, is standard practice in every top board game program (chess, checkers, Go). Similar optimizations are done in protein design and other backtracking search applications where small incremental changes and their inverses are done to the data structure.
I can send a PR if you would welcome identity_hash (I'm obivously not proposing the wrapper class).
I would like to propose adding an
identity_hashthat stores its input bytes as result.The use cases for this simple hash function are for thin wrapper classes around regular value types that cache their hash keys. E.g. below is a sketch of such a wrapper class that holds a value and its hash key. This key can be computed in the wrapper's constructor by
xstd::uhashusing any full-fledged hash function (fnv1ahere, but also Murmur, City or evenstd::hash).Once the key has been computed and wrapped, the wrapper object itself can be stored inside a
std::unordered_set<wrap, xstd::uhash<acme::identity_hash>>. This saves recomputing the hash key.The proposed
identity_hashwould enable thehash_appendframework for these type of data structures. This also paves the way for (but does not depend on) using a tabulation hashing algorithm (where the key is incrementally updated when the wrapped value is mutated; caching the key is required in order to achieve this).Applications are e.g. chess engines, where the wrapped type represents the full chess Position object. Storing the hash key and incrementally updating it as the underlying position changes, is standard practice in every top board game program (chess, checkers, Go). Similar optimizations are done in protein design and other backtracking search applications where small incremental changes and their inverses are done to the data structure.
I can send a PR if you would welcome
identity_hash(I'm obivously not proposing the wrapper class).