A good hash function for a vector

user_750186 0
Viewed 44885

I have some vector of integer that I would like to store efficiently in a unordered_map in c++11 my question is this:

How do I best store these and optimize for .find queries?

I came up with the following hasher:

class uint32_vector_hasher {
public:
  std::size_t operator()(std::vector<uint32_t> const& vec) const {
    std::size_t ret = 0;
    for(auto& i : vec) {
      ret ^= std::hash<uint32_t>()(i);
    }
    return ret;
  }
};

and then store the objects in an unordered_map I do however have a couple of questions

  1. how often does the hash get calculated, only one, some random number or times?
  2. Would it make sense to create a wrapper object with == and hash functions to make memorize the hash and avoid it being calculated more than once?

When profiling I've noticed that a rather large amount of my cpu time is spend doing lookups on the unordered maps, this is not exactly optimal :(

c++11 hash c++
3 Answers

The hash function in the currently highest voted answer by HolKann results in a high collision rate for numerous vectors that all contain elements from a small continuous distribution.

To combat this, bits of each element are distributed evenly (algorithm taken from Thomas Mueller's answer).

std::size_t operator()(std::vector<uint32_t> const& vec) const {
  std::size_t seed = vec.size();
  for(auto x : vec) {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = (x >> 16) ^ x;
    seed ^= x + 0x9e3779b9 + (seed << 6) + (seed >> 2);
  }
  return seed;
}
user_53028130

boost::hash_combine is good enough but not particularly good

HolKann's answer is good enough, but I'd recommend using a good hash for each entry and then combining them. The problem is std::hash is not a good hash and boost::hash_combine is not strong enough to make up for that.

template<typename T>
T xorshift(const T& n,int i){
  return n^(n>>i);
}

uint32_t hash(const uint32_t& v) {
  uint32_t p = 0x55555555ul; // pattern of alternating 0 and 1
  uint32_t c = 3423571495ul; // random uneven integer constant; 
  return c*xorshift(p*xorshift(n,16),16);
}

// if c++20 rotl is not available:
template <typename T,typename S>
typename std::enable_if<std::is_unsigned<T>::value,T>::type
constexpr rotl(const T n, const S i){
  const T m = (std::numeric_limits<T>::digits-1);
  const T c = i&m;
  return (n<<c)|(n>>((T(0)-c)&m)); // this is usually recognized by the compiler to mean rotation, also c++20 now gives us rotl directly
}

class uint32_vector_hasher {
public:
  std::size_t operator()(std::vector<uint32_t> const& vec) const {
    std::size_t ret = 0;
    for(auto& i : vec) {
      ret = rotl(ret,11)^hash(i);
    }
    return ret;
  }
};
user_21193770
Related