A good hash function for a vector
40,049
Solution 1
Always go with the experts when possible: http://www.boost.org/doc/libs/release/doc/html/hash/reference.html#boost.hash_combine
Solution 2
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.
![Martin Kristiansen](https://i.stack.imgur.com/5IH0v.jpg?s=256&g=1)
Author by
Martin Kristiansen
Updated on August 28, 2021Comments
-
Martin Kristiansen almost 3 years
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- how often does the hash get calculated, only one, some random number or times?
- 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 :(