hash — C ++ unordered_map с использованием пользовательского типа класса в качестве ключа

Чтобы иметь возможность использовать std::unordered_map (или один из других неупорядоченных ассоциативных контейнеров) с определяемым пользователем типом ключа, вам нужно определить две вещи:

1. хэш-функция; это должен быть класс, который переопределяет operator() и вычисляет значение хеш-функции, заданное для объекта типа ключа. Одним из особенно простых способов сделать это является специализация std::hash шаблон для вашего типа ключа.

2. функция сравнения на равенство; это необходимо, поскольку хеш-функция не может полагаться на тот факт, что хеш-функция всегда будет предоставлять уникальное значение хеш-функции для каждого отдельного ключа (т. е. она должна иметь возможность справляться с коллизиями), поэтому ей нужен способ сравнения двух заданных ключей. для точного соответствия. Вы можете реализовать это либо как класс, который переопределяет operator()или как специализация std::equalили — проще всего — перегрузкой operator==() для вашего типа ключа (как вы уже сделали).

Сложность хеш-функции заключается в том, что если ваш тип ключа состоит из нескольких элементов, у вас обычно есть хеш-функция, которая вычисляет значения хеш-функции для отдельных элементов, а затем каким-то образом объединяет их в одно значение хеш-функции для всего объекта. Для обеспечения хорошей производительности (т. Е. Нескольких коллизий) вы должны тщательно продумать, как объединить отдельные значения хеш-функции, чтобы избежать слишком частого получения одного и того же вывода для разных объектов.

Достаточно хорошей отправной точкой для хеш-функции является та, которая использует битовое смещение и битовое XOR для объединения отдельных хеш-значений. Например, предполагая тип ключа, подобный этому:

struct Key
{
std::string first;
std::string second;
int         third;

bool operator==(const Key &other) const
{ return (first == other.first
&& second == other.second
&& third == other.third);
}
};

Вот простая хеш-функция (адаптированная от той, которая используется в Пример cppreference для пользовательских хеш-функций):

namespace std {

template <>
struct hash<Key>
{
std::size_t operator()(const Key& k) const
{
using std::size_t;
using std::hash;
using std::string;

// Compute individual hash values for first,
// second and third and combine them using XOR
// and bit shifting:

return ((hash<string>()(k.first)
^ (hash<string>()(k.second) << 1)) >> 1)
^ (hash<int>()(k.third) << 1);
}
};

}

С этим на месте, вы можете создать экземпляр std::unordered_map для типа ключа:

int main()
{
std::unordered_map<Key,std::string> m6 = {
{ {"John", "Doe", 12}, "example"},
{ {"Mary", "Sue", 21}, "another"}
};
}

Это будет автоматически использовать std::hash<Key> как определено выше для вычислений значения хеша, и operator== определяется как функция-член Key для проверки на равенство.

Если вы не хотите специализировать шаблон внутри std Пространство имен (хотя в данном случае это совершенно законно), вы можете определить хеш-функцию как отдельный класс и добавить ее в список аргументов шаблона для карты:

struct KeyHasher
{
std::size_t operator()(const Key& k) const
{
using std::size_t;
using std::hash;
using std::string;

return ((hash<string>()(k.first)
^ (hash<string>()(k.second) << 1)) >> 1)
^ (hash<int>()(k.third) << 1);
}
};

int main()
{
std::unordered_map<Key,std::string,KeyHasher> m6 = {
{ {"John", "Doe", 12}, "example"},
{ {"Mary", "Sue", 21}, "another"}
};
}

Как определить лучшую хэш-функцию? Как сказано выше, определение хорошей хеш-функции важно, чтобы избежать коллизий и получить хорошую производительность. Для действительно хорошего вы должны принять во внимание распределение возможных значений всех полей и определить хеш-функцию, которая проецирует это распределение в пространство возможных результатов как можно более широкое и равномерное распределение.

Это может быть сложно; описанный выше метод XOR / битового сдвига, вероятно, неплохое начало. Для лучшего начала вы можете использовать hash_value а также hash_combine шаблон функции из библиотеки Boost. Первый действует так же, как std::hash для стандартных типов (недавно также включая кортежи и другие полезные стандартные типы); последнее помогает вам объединить отдельные значения хеша в одно. Вот переписать хеш-функцию, которая использует вспомогательные функции Boost:

#include <boost/functional/hash.hpp>

struct KeyHasher
{
std::size_t operator()(const Key& k) const
{
using boost::hash_value;
using boost::hash_combine;

// Start with a hash value of 0    .
std::size_t seed = 0;

// Modify 'seed' by XORing and bit-shifting in
// one member of 'Key' after the other:
hash_combine(seed,hash_value(k.first));
hash_combine(seed,hash_value(k.second));
hash_combine(seed,hash_value(k.third));

// Return the result.
return seed;
}
};

И вот переписывание, которое не использует boost, но использует хороший метод объединения хэшей:

namespace std
{
template <>
struct hash<Key>
{
size_t operator()( const Key& k ) const
{
// Compute individual hash values for first, second and third
// http://stackoverflow.com/a/1646913/126995
size_t res = 17;
res = res * 31 + hash<string>()( k.first );
res = res * 31 + hash<string>()( k.second );
res = res * 31 + hash<int>()( k.third );
return res;
}
};
}