hashing std::pair and std::tuple

Lately I have been refactoring some old code & found it littered with all sorts of things. This particular code had a custom hash-table for hashing based off 3 values instead of 1. std::tuple are the best fit, or probably providing a custom struct with std::hash specialization would have served as well. What std library provides is std::hash for basic types, reference here. There is nothing for composite types. Even for std::pair.

Providing a std::hash for both std::pair and std::tuple is what I want to address with this post.

hashing a std::pair


A pair has two elements, thus it is quite straight forward to specialize the hash, just have to use a special hash_combine:

    //  on why XOR is not a good choice for hash-combining:
    //  https://stackoverflow.com/questions/5889238/why-is-xor-the-default-way-to-combine-hashes
    //  
    //  this is from boost
    //
    template<typename T>
    inline void hash_combine(std::size_t& seed, const T& val)
    {
        std::hash<T> hasher;
        seed ^= hasher(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    }

    //  taken from https://stackoverflow.com/a/7222201/916549
    //
    template<typename S, typename T>
    struct hash<std::pair<S, T>>
    {
        inline size_t operator()(const std::pair<S, T>& val) const
        {
            size_t seed = 0;
            hash_combine(seed, val.first);
            hash_combine(seed, val.second);
            return seed;
        }
    };

hash_combine is from boost, so that helps and the link has pretty good explanation for this algorithm.

For std::pair just call it twice and be done with it. The complexity comes with std::tuple and how do you handle #types to be hashed without specialization for arity of types.

hashing a std::tuple


Now along similar lines, here is the specialization of hash, but in this case we need something that iterates/recurses over all the types.


    template<class... TupleArgs>
    struct std::hash<std::tuple<TupleArgs...>>
    {
        size_t operator()(std::tuple<TupleArgs...> tupleValue) const
        {
            size_t seed = 0;
            hash_combine_tup(seed, tupleValue);
            return seed;
        }
    };

I want to reuse hash_combine from before, yet want to define a way to iterate over the types of std::tuple and compute new hash using std::hash and hash_combine. Since I am fiddling with types here this calls for recursion instead of iteration. Fancy functional programming

There are various ways to do this, one could be to construct a new std::tuple with fewer elements and pass to the specialization or other is to increase/decrease the type index. I would go with type-index as it avoids copying business.

To achieve this we need:

  1. termination function, that does nothing- stops recursion

    
    //  this is a termination condition
    //  N == sizeof...(TupleTypes)
    //
    template<size_t Idx, typename... TupleTypes>
    inline typename std::enable_if<Idx == sizeof...(TupleTypes), void>::type
    hash_combine_tup(size_t& seed, const std::tuple<TupleTypes...>& tup)
    {        
    }
    
  2. and a function that computes hash & recurses to termination

    //  this is the computation workhorse
    //  N < sizeof...(TupleTypes)
    //
    template<size_t Idx, typename... TupleTypes>
    inline typename std::enable_if<Idx < sizeof...(TupleTypes), void>::type
    hash_combine_tup(size_t& seed, const std::tuple<TupleTypes...>& tup)
    {
        hash_combine(seed, std::get<Idx>(tup));
    
        //  on to next element
        hash_combine_tup<Idx+1>(seed, tup);
    }
    

Putting all of this together:


    template <class T>
    inline void hash_combine(std::size_t& seed, T v)
    {
        seed ^= std::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    }

    template<class... TupleArgs>
    struct std::hash<std::tuple<TupleArgs...>>
    {
    private:
        //  this is a termination condition
        //  N == sizeof...(TupleTypes)
        //
        template<size_t Idx = 0, typename... TupleTypes>
        inline typename std::enable_if<N == sizeof...(TupleTypes), void>::type
        hash_combine_tup(size_t& seed, const std::tuple<TupleTypes...>& tup) const
        {        
        }

        //  this is the computation workhorse
        //  N < sizeof...(TupleTypes)
        //
        template<size_t Idx = 0, typename... TupleTypes>
        inline typename std::enable_if<N < sizeof...(TupleTypes), void>::type
        hash_combine_tup(size_t& seed, const std::tuple<TupleTypes...>& tup) const
        {
            hash_combine(seed, std::get<Idx>(tup));

            //  on to next element
            hash_combine_tup<Idx+1>(seed, tup);
        }
    
    public:
        size_t operator()(std::tuple<TupleArgs...> tupleValue) const
        {
            size_t seed = 0;
            hash_combine_tup<0>(seed, tupleValue);
            return seed;
        }
    };

That’s it for now.. I have posted entire thing as a gist here.