Что такое хорошая хеш-функция для 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.

0

Решение

То, что вы делаете в своей хэш-функции, зависит от значений, которые вы получили, а не обязательно от их типов. Если все четыре элемента данных содержат каждое значение, равномерно распределенное, я бы объединил два символа в unsigned long и вернуть результат сохранения двух значений:

typedef unsigned long ulong;
return n ^ (ulong(a << 16) | ulong(b << 8) | ulong(c));

Это конечно хэш-функция Хорошо ли это работает — это другой вопрос. Вы также можете объединить результат с std::hash<unsigned long>,

4

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

Вот базовая хеш-функция:

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 бита, и если предположить, что ваши символы не являются отрицательными, это использует всю информацию в ваших объектах для хэша.

2

Считай свой 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, похожий на тот, который я вам дал.

2

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;
0
По вопросам рекламы [email protected]