c ++ не может найти элемент unordered_set с тем же хешем

Question

У меня есть пользовательская функция ha sh для unordered_set векторов :

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

И для двух таких векторов у меня один и тот же ха sh равен 3:

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

Но когда я пытаюсь вставить первый вектор v1 в unordered_set, а затем проверить, есть ли у меня такой же вектор на ha sh, как v2 в моем unordered_set, я получаю 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"

Я предполагаю, что если два элемента в unordered_set имеют одинаковое значение ha sh, то если у меня есть v1 в моем unordered_set, метод find должен возвращать true, когда я пытаюсь найти v2. Но это не тот случай.

Может ли кто-нибудь объяснить мне, что не так в моих рассуждениях?

Answer 1

Ха sh не все, то, что вы видите здесь, является столкновением.

Оба std::vector<int> имеют здесь одинаковое значение ha sh, но после того, как ха sh является Если вычислить, std::unordered_map будет фактически проверять равенство элементов, используя operator== для проверки равенства элементов, что в данном случае не удается, и не удается найти элемент.

Столкновения - это обычная вещь в HashMaps Мало, что вы можете сделать здесь без предоставления пользовательских operator==.

Answer 2

Я предполагаю, что если два элемента в unordered_set имеют одинаковое значение ha sh, то, если у меня есть v1 в моем unordered_set, метод find должен вернуть true, когда я пытаюсь найти v2.

Это предположение неверно, то же самое sh не означает, что объекты равны.

unordered_map использует предикат равенства для определения равенства ключей (по умолчанию std::equal_to) .

Answer 3

вам нужно предоставить компаратор для unordered_set, а если вы хотите, чтобы два элемента совпадали, вы можете сделать что-то вроде этого:

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

и создать свой unordered_set вот так

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

Тогда вы должны получить ожидаемый результат

Answer 4

Если вам нужны уникальные идентификаторы, но вы не можете автоматически сравнивать значения, вы можете использовать (unordered_)map<int, vector<int>> и использовать эту функцию VectorHa sh для генерации ключа int:

unordered_map<int, vector<int>> map;

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