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

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

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

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

2 ответа

Решение

Я думаю, что это может быть лучшей альтернативой ответу 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
}

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

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

  1. Принимает один параметр типа Key ,
  2. Возвращает значение типа size_t это представляет значение хеш-значения параметра.
  3. Не выдает исключений при вызове.
  4. Для двух параметров k1 а также k2 которые равны, std::hash<Key>()(k1) == std::hash<Key>()(k2) ,
  5. Для двух разных параметров 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::set s отличаются и остаются такими же, когда члены не отличаются как 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 функтор также.

Другие вопросы по тегам