Identity hash

[rhalbersma]

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).

[HowardHinnant]

Sounds like an interesting example, thanks.

[rhalbersma]

Never mind the double notification for this pull request. I hadn't properly synced with your repo before sending the PR. AFAICS, my hard history rewrite leaves only the latest commit in the PR.

[vinniefalco]

Applications are e.g. chess engines, where the wrapped type represents the full chess Position object.

That is REALLY COOL!! Thanks for sharing this!