hash function for a vector of pair<int, int>

c++, hash, vector

Solution

All you need is a function to "hash in" an integer. You can steal such a function from boost:

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

Now your function is trivial:

struct ObjectHasher
{
  std::size_t operator()(const Object& k) const
  {
    std::size_t hash = 0;
    for (auto i = k.vec.begin(); i != k.vec.end(); ++i)
    {
      hash_combine(hash, i->first);
      hash_combine(hash, i->second);
    }
    return hash;
  }
};

Problem

I'm trying to implement an unordered_map for a vector< pair < int,int> >. Since there's no such default hash function, I tried to imagine a function of my own : ``` struct ObjectHasher { std::size_t operator()(const Object& k) const { std::string h_string(""); for (auto i = k.vec.begin(); i != k.vec.end(); ++i) { h_string.push_back(97+i->first); h_string.push_back(47); // '-' h_string.push_back(97+i->second); h_string.push_back(43); // '+' } return std::hash<std::string>()(h_string); } }; ``` The main idea is to change the list of integers, say ( (97, 98), (105, 107) ) into a formatted string like "a-b+i-k" and to compute its hash thanks to hash < string >(). I choosed the 97, 48 and 43 numbers only to allow the hash string to be easily displayed in a terminal during my tests. I know this kind of function might be a very naive idea since a good hash function should be fast and strong against collisions. Well, if the integers given to push_back() are greater than 255 I don't know what might happen... So, what do you think of the following questions : - (1) is my function ok for big integers ? - (2) is my function ok for all environments/platforms ? - (3) is my function too slow to be a hash function ? - (4) ... do you have anything better ?

Original source