A good hash function for a vector

Question

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 :(

Answer 1

So, when not wanting to use boost, Michael Blurr's comment led to the following hash function implementation:

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

Seems to work.

Edit: see's answer is a little bit slower, but indeed yields a better hash distribution. I'd go with that one.

Answer 2

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;
}

Answer 3

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;
  }
};

Answer 4

I tried see's answer to solve a leet code problem. But for some inputs, the function would overflow ints. So, I reverted to your approach. But, your function causes lots of collisions if you have elements like: {0}, {0, 0}, {0, 0, 0}, etc. because hash of int is the number itself and all these hash to 0.

I tweaked it slightly to include the index to reduce the collision rate:

struct hash {
    std::size_t operator()(std::vector<int> const& vec) const {
        std::hash<uint32_t> h;
        std::size_t ret = vec.size();
        for(auto& i : vec) {
            ret ^= h(i) | i;
        }
        return ret;
    }
};

I am just Oring the hash with the index so {0}, {0, 0}, {0, 0, 0} produce different hashes. Its a very bad hash function but it works for my purposes :P