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