Что такое хорошая хеш-функция для struct с 3-мя беззнаковыми символами и int для unordered_map?
Я просто хочу использовать unordered_map с моей структурой в качестве ключа, так как мне не нужно ничего упорядочивать … но я просто не могу найти себя со всеми этими хэшами …
Как уместный вопрос. Когда люди сравнивают неупорядоченную и упорядоченную карту, они никогда не говорят о хэш-функции, как это может быть? Может плохая хеш-функция делает неупорядоченную карту медленнее, чем карта? (исключительно из-за хэш-функции)
struct exemple{
unsigned char a,b,c;
unsigned int n;
bool operator == ( const exemple & other) const {..}
};
namespace std {
template <>
struct hash<exemple> : public std::unary_function<const exemple &, std::size_t>
{
inline std::size_t operator()(const exemple & exemple_p ) const
{
return 0;// what do I do
}
};
}
-редактировать-
a, b, c может иметь только значения «a», «b», «c» или «d», а n варьируется от ~ 3 до 60.
Решение
То, что вы делаете в своей хэш-функции, зависит от значений, которые вы получили, а не обязательно от их типов. Если все четыре элемента данных содержат каждое значение, равномерно распределенное, я бы объединил два символа в unsigned long и вернуть результат сохранения двух значений:
typedef unsigned long ulong;
return n ^ (ulong(a << 16) | ulong(b << 8) | ulong(c));
Это конечно хэш-функция Хорошо ли это работает — это другой вопрос. Вы также можете объединить результат с std::hash<unsigned long>,
Другие решения
Вот базовая хеш-функция:
unsigned long long h = (n << 24) | (a << 16) | (b << 8) | c;
return std::hash(h);
Т.е., просто упакуйте участников в unsigned long longзатем переложить работу на std::hash, В общем случае это int имеет ширину 32 бита и long long 64 бита, и если предположить, что ваши символы не являются отрицательными, это использует всю информацию в ваших объектах для хэша.
Считай свой struct в целом, чтобы быть строкой байтов (7, чтобы быть точным). Вы можете использовать любую приемлемо общую строковую хеш-функцию для этих 7 байтов. Вот общая хэш-функция битовой строки FNV (Fowler / Noll / Vo), примененная к вашему примеру (в рамках заданного класса хэш-функторов):
inline std::size_t operator()(const exemple& obj ) const
{
const unsigned char* p = reinterpret_cast<const unsigned char*>( &obj );
std::size_t h = 2166136261;
for (unsigned int i = 0; i < sizeof(obj); ++i)
h = (h * 16777619) ^ p[i];
return h;
}
Обратите внимание, как я преобразовал ссылку на exemple состав (obj) указатель на const unsigned char так, чтобы я мог обращаться к байтам структуры один за другим, и я рассматриваю это как непрозрачный двоичный объект. Обратите внимание, что sizeof(obj) на самом деле может быть 8, а не 7, в зависимости от заполнения компилятора (что означает, что где-то в структуре есть байт заполнения мусора, возможно, между c а также n, Если вы хотите, вы можете переписать хеш-функцию для перебора a, b, а также c а затем байты n в порядке (или любом порядке), который бы исключил влияние любых байтов заполнения (которые могут существовать или не существовать) на хэш вашего struct,
Да, плохая хеш-функция может сделать unordered_map медленнее чем ordered_map, Это не всегда обсуждается, поскольку предполагается, что обобщенные быстрые алгоритмы, такие как хэш FNV, приведенный выше, используются теми, кто использует unordered_mapи в этих случаях, как правило, unordered_map быстрее, чем ordered_map за счет возможности перебирать элементы контейнера по порядку. Однако, да, вы должны использовать хорошую хеш-функцию для своих данных, и обычно достаточно использовать одну из этих известных хешей. В конечном счете, однако, каждая хеш-функция имеет свои недостатки в зависимости от входных данных (здесь, содержимое exemple структура) распределение.
Хорошее обсуждение обобщенного хеширования и пример хеширования можно найти по адресу Вечно Смущенный, включая хэш FNV в стиле C, похожий на тот, который я вам дал.
boost::hash_combine предназначен для этой цели:
std::size_t hash = 0;
for (const auto& value : {a, b, c}) {
boost::hash_combine(hash, value);
}
boost::hash_combine(hash, n);
return hash;