Specializing std::hash for std::array

Question

I want to have an std::unordered_map which uses arrays as keys. As long as a type has an operator== and an std::hash it can be used as a key.

Here is my std::hash<std::array>

template<class T, size_t N> 
struct std::hash<std::array<T, N>> {
    auto operator() (const std::array<T, N>& key) const {
        std::hash<T> hasher;
        size_t result = 0;
        for(size_t i = 0; i < N; ++i) {
            result = result * 31 + hasher(key[i]); // ??
        }
        return result;
    }
};

I copied the multiply by 31 from somewhere. An example here uses << and ^. I don't know which is better or how to apply the cppreference example to an array.

// cppreference example
template<> struct hash<S>
    {
        typedef S argument_type;
        typedef std::size_t result_type;
        result_type operator()(argument_type const& s) const
        {
            result_type const h1 ( std::hash<std::string>{}(s.first_name) );
            result_type const h2 ( std::hash<std::string>{}(s.last_name) );
            return h1 ^ (h2 << 1); // or use boost::hash_combine (see Discussion)
        }
    };

It seems to work. All of the code compiles and the return values for std::hash<key_type> seem ok to me.

using key_type = std::array<int, 2>;
using hash_type = std::hash<key_type>;
using map_type = std::unordered_map<key_type, int>;

map_type map; // compiles
hash_type hasher; // compiles

int main() {
    // test return values of std::hash<key_type>
    for(int y = -2; y < 3; ++y) {
        for(int x = -2; x < 3; ++x) {
            std::cout << hasher({x, y}) << " ";
        }
        std::cout << std::endl;
    }
}

The values printed from this code are:

18446744073709551552 18446744073709551583 18446744073709551614 29 60 
18446744073709551553 18446744073709551584 18446744073709551615 30 61 
18446744073709551554 18446744073709551585 0 31 62 
18446744073709551555 18446744073709551586 1 32 63 
18446744073709551556 18446744073709551587 2 33 64

I'm not sure what makes a good hash function for std::unordered_map, so I'd appreciate any feedback on how to make this hash function better.

Answer 1

Implicit assumption:

It looks like you make an implicit assumption here:

std::hash<T> hasher;

making it non-member means that you assume std::hash is not allowed to have any state, which is false. It is not required to be monostate, so the hasher should be a member of the specialization.

When the assumption can bite you?

Consider this implementation in pseudocode:

store `std::map<T, counter_type>` as data member.
on every call to hash an array, for each element:
    result = result * 31 + map[elem]

Imagine that counter_type is just a counter, e.g. each unique instance gives a unique number, in incremental order. If you would leave the std::hash<T> as local, this would happen:

on every call to hash an array for each element:
    result = result * 31 + 0 //or whatever counter starts from

So it would degrade any unordered container.

Example version

Example version uses specific operators to the specific class, whereas your code is generic. So, I guess your version should be fine with the applied change described above.

31

I've seen it being used in "Effective Java" by Joshua Bloch. I believe he described it as prime which is closest to the power of two, which has positive impact on overflow (e.g. one number won't be repeated for pretty long time). I don't have any maths to back this up, but I believe the direction is right.

Answer 2

What is a "good" hash function?

The requirement of a hash function is that it always produces the same value for a given key (in the same instance of the program) and a good hash function should produce each output with equal probability.

Your function achieves this (multiplying by a prime such as 31 is a well-known way of combining hash values to reduce collisions caused by different permutations of the same values).

However, it's up to you to decide whether the hash inputs in your application have a random distribution, or whether they have some pattern that may perturb the output distribution from the hash function.

Can you use your mental reasoning to force a collision? {1, 0} and {0, 31} might do it, for example. Can you think of any reason why your code might produce collisions more often than by independent chance?

Style points

The code is neat and clear. It might be an idea to allow an alternative to std::hash<T> to be supplied by the caller, just as std::unordered_map itself allows a user-supplied hasher. This may be useful with char* strings, for example.

You could simplify the loop, as std::array supports range-based for:

    for (const auto& element: key) {
        result = result * 31 + hasher(element);
    }

More tests

It's good that you've provided a test suite. Consider whether you could add more tests - at least one test with an element type other than int and at least least one with different array lengths (you should probably include a test for std::array<char, 1> as a boundary case, for example).

Alternatives

Boost provides a hash() function that accepts built-in (i.e. C-style) arrays, so you might be able to reinterpret_cast the std::array. I've never tried this, but I don't see why it wouldn't work...

Answer 3

Hashing and creating a good one is a complex subject that I will let other more educated people delve into:

This seems reasonable to my uneducated eye:

template<class T, size_t N> 
struct std::hash<std::array<T, N>> {
    auto operator() (const std::array<T, N>& key) const {
        std::hash<T> hasher;
        size_t result = 0;
        for(size_t i = 0; i < N; ++i) {
            result = result * 31 + hasher(key[i]); // ??
        }
        return result;
    }
};

You use a prime 31 as the multiplicand. Which seems reasonable.

The one thing I may change was the seed value result = 0;. Currently an array with a single value has the same hash as that single value. I would just generate a seed value (make it a large prime for fun 144451).

To use the return h1 ^ (h2 << 1) in your class just do the following.

template<class T, size_t N> 
struct std::hash<std::array<T, N>> {
    auto operator() (const std::array<T, N>& key) const {
        std::hash<T> hasher;
        size_t result = 0;   // I would still seed this.
        for(size_t i = 0; i < N; ++i) {
            result = (result << 1) ^ hasher(key[i]); // ??
        }
        return result;
    }
};