возвращение хеш-функции unordered_map

Question

возвращение хеш-функции unordered_map

Я хотел бы иметь unordered_map с struct, что я хотел бы использовать в качестве ключа, из нескольких std::set< std::string >,

Я вижу, что пользовательская хэш-функция необходимо и что строка может иметь std::hash применяется; однако я не могу определить, что должно быть возвращено, чтобы удовлетворить цели хэш-функции этих наборов для unordered_map.

Как должна возвращать пользовательская хеш-функция?

1

c++hash-function set struct unordered-map

Решение

Другие решения

Требования std::hash как следует: (http://en.cppreference.com/w/cpp/utility/hash)

Шаблон хеша определяет объект функции, который реализует хеш-функцию. Экземпляры этого функционального объекта удовлетворяют Hash. В частности, они определяют Оператор () тот:

Принимает один параметр типа Key,
Возвращает значение типа size_t это представляет значение хеш-значения параметра.
Не выдает исключений при вызове.
Для двух параметров k1 а также k2 которые равны, std::hash<Key>()(k1) == std::hash<Key>()(k2),
Для двух разных параметров k1 а также k2 которые не равны, вероятность того, что std::hash<Key>()(k1) == std::hash<Key>()(k2) должно быть очень маленьким, приближается 1.0 / std::numeric_limits<size_t>::max(),

Шаблон хеша CopyConstructible а также Destructible.

Итак, что вам нужно, это в основном функция, которая возвращает std::size_t это уникально для каждого myStruct объект и возвращает то же значение для объектов, которые считаются эквивалентными.

Редактировать: следующее может быть не самым надежным способом генерирования хеша, но это послужит базовым примером того, как это можно сделать.

Один из способов сделать это — использовать стандартную специализацию для std::hash<std::string> объединяя все строки в каждом std::set член, использующий последовательность разделителей а затем объединить все полученные объединенные строки в одну и вернуть значение хеш-функции, используя стандартную хеш-функцию.

Объединенная супер-строка будет уникальной для каждого myStruct возражать, если член std::setS отличаются и остаются такими же, когда члены не отличаются как std::set это заказанный контейнер.

struct myStruct {
std::set<std::string> s1;
std::set<std::string> s2;
};

std::string mergeAllStrings(const myStruct& ms) {
static const std::string SEPARATOR = "#¤%&"; // Some uncommon sequence.
std::string super;
for (const auto& s : ms.s1) {
super += s + SEPARATOR; // Append separator.
}
for (const auto& s : ms.s2) {
super += s + SEPARATOR; // Append separator.
}
return super;
}

int main() {
myStruct ms1{{"apple", "pear", "orange"}, {"red", "green", "blue"}};
myStruct ms2{{"pear", "apple", "orange"}, {"red", "green", "blue"}};
myStruct ms3{{"apple", "banana", "orange"}, {"red", "green", "blue"}};

std::cout << std::hash<std::string>()(mergeAllStrings(ms1)) << std::endl;
std::cout << std::hash<std::string>()(mergeAllStrings(ms2)) << std::endl;
std::cout << std::hash<std::string>()(mergeAllStrings(ms3)) << std::endl;
}

Выход:

2681724430859750844 // Same
2681724430859750844 // Same
2942368903851914580 // Different

Теперь вы можете создать хеш-функтор, например как:

struct MyHash {
std::size_t operator()(const myStruct& ms) const {
return std::hash<std::string>()(mergeAllStrings(ms));
}
};

и использовать его с std::unordered_map как:

std::unordered_map<myStruct, myValue, MyHash> m;

Обратите внимание, что вы должны предоставить equal_to функтор также.

1

Источник

Accepted Answer

Я думаю, что это может быть лучшей альтернативой Ответ Snps. Это реализует специализацию std::hash для пользовательского типа, и он хэширует структуру без создания временных строк.

Я скопировал две функции из Boost, hash_combine а также hash_range, чтобы вычислить одно значение хеша из двух контейнеров.

#include <iostream>
#include <functional>
#include <set>
#include <unordered_map>

// user-defined type
struct myStruct {
std::set<std::string> s1;
std::set<std::string> s2;

bool operator==(const myStruct &other) const {
return (s1 == other.s1) && (s2 == other.s2);
}
};

// hash helper functions plagiarized from Boost
template <typename T>
void hash_combine(size_t &seed, const T &v)
{
using std::hash;
seed ^= hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

template <typename It>
void hash_range(size_t &seed, It first, It last)
{
for (; first != last; ++first) {
hash_combine(seed, *first);
}
}

// std::hash specialization
namespace std
{
template<> struct hash<myStruct> {
size_t operator()(const myStruct &key) const {
size_t seed = 0;
hash_range(seed, key.s1.begin(), key.s1.end());
hash_range(seed, key.s2.begin(), key.s2.end());
return seed;
}
};
}

int main()
{
std::unordered_map<myStruct, int> myMap;

myStruct ms1{ { "apple", "pear", "orange" }, { "red", "green", "blue" } };
myStruct ms2{ { "pear", "apple", "orange" }, { "red", "green", "blue" } };
myStruct ms3{ { "apple", "banana", "orange" }, { "red", "green", "blue" } };

myMap[ms1] = 1;
myMap[ms2] = 2;
myMap[ms3] = 3;

std::cout << myMap.size() << '\n'; // output: 2
}

2