c++ cannot find element is unordered_set with the same hash

Question

I have custom hash function for unordered_set of vectors< int >:

struct VectorHash {
int operator()(const vector<int> &V) const {
    int hsh=V[0] + V[1];
    return  hash<int>()(hsh);
}};

And for two such vectors I have the same hash equal 3:

vector<int> v1{2,1};
vector<int> v2{1,2};

But when I try to insert first vector v1 in unordered_set, and then check if I have the same vector by hash as v2 in my unordered_set I get false:

std::unordered_set<std::vector<int>, VectorHash> mySet;
mySet.insert(v1); 

if(mySet.find(v2) == mySet.end())
    cout << "didn't find" << endl;

Output:  "didn't find"

I assume that if two elements in unordered_set have the same hash then if I have v1 in my unordered_set, find method should return true, when I try to find v2. But it is not the case.

Could anyone explain me what is wrong in my reasoning?

Answer 1

Hash isn't everything, what you're seeing here, is a collision.

Both std::vector<int> have the same hash value here, but after hash is calculated, std::unordered_map will actually actually check for equality of elements using operator== to check for equality of elements, which fails in this case, and fails to find the element.

Collisions are a normal thing in HashMaps, not much you can do here without providing custom operator==.

Answer 2

I assume that if two elements in unordered_set have the same hash then if I have v1 in my unordered_set, find method should return true, when I try to find v2.

That assumption is incorrect, same hash doesn't mean objects are equal.

unordered_map uses the equality predicate to determine key equality (by default std::equal_to).

Answer 3

If you happen to want unique identifiers but not automatically compare values, you could use an (unordered_)map<int, vector<int>> and use that VectorHash function to generate the int key:

unordered_map<int, vector<int>> map;

int key=V[0] + V[1]
map[key] = V;

Answer 4

you need to provide a comparator to the unordered_set as well if you want the two elements to match, you can do something along the lines of this:

struct VectorComparator {
  bool operator()(const std::vector<int> & obj1, const std::vector<int> & obj2) const
  {
    if ((obj1[0] + obj1[1]) == (obj2[0] + obj2[1]))
      return true;
    return false;
  }
};

and create your unordered_set like this

std::unordered_set<std::vector<int>, VectorHash, VectorComparator> mySet;

Then you should get the result you are expecting