Хеш-функция для неупорядоченных ассоциативных контейнеров в переполнении стека
В C ++ для каждого неупорядоченного ассоциативного контейнера (например, unordered_map, unordered_set, unordered_multimap) нам нужно определить хеш-функцию. Как указано Википедия,
struct X{int i,j,k;};
struct hash_X{
size_t operator()(const X &x) const{
return hash<int>()(x.i) ^ hash<int>()(x.j) ^ hash<int>()(x.k);
}
};
struct hash_X пользовательская функция хеширования struct X, Но что делает эта функция? Зачем нам нужна хеш-функция? Может ли быть какой-либо другой тип пользовательских функций хеширования? Если да, то как мы можем сравнить эффективность между любыми двумя такими функциями?
Решение
Цель функции хеширования состоит в том, чтобы отобразить содержимое произвольной структуры данных в целое число таким образом, чтобы большинство элементов, с которыми вы можете столкнуться, отображались на разные целые числа, и чтобы весь набор элементов, которые вы, вероятно, могли встреча вместе распространяется равномерно по множеству целых чисел. С такой функцией в руке становится легко построить контейнер (такой как unordered_map), который ищет произвольные элементы очень быстро.
Я понимаю, что это определение несколько абстрактно. Более конкретно, рассмотрим пример, который вы привели выше из Википедии. Это XORS i, j а также k поля структуры вместе, чтобы сформировать хэш-значение. Это допустимая хеш-функция (она объединила структуру в одно целое число). Но если i, j а также k у всех одинаковые диапазоны значений, тогда это может быть не очень хорошая функция хеширования. Например, (1,2,3) а также (3,1,2) оба хешируют одно и то же значение.
Идеальная функция хеширования обычно больше похожа на генератор случайных чисел: для предсказуемых входных данных она дает, казалось бы, случайные выходные данные. (Но помните, один и тот же вход должен всегда давать один и тот же результат.) Лучшая хеш-функция для вашей структуры данных действительно зависит от того, какой тип данных вы будете хэшировать.
Этот набор примечаний к лекции выглядит так, как будто он охватывает большинство важных моментов: http://www.cs.cornell.edu/Courses/cs312/2008sp/lectures/lec21.html
Вы можете найти других, погуглив.
Другие решения
Краткий ответ: быстро найти элементы.
В отличие от упорядоченных контейнеров, которые хранят элементы в некоторой форме red-black trees (или другое дерево AVL), неупорядоченные использует indexed buckets содержать узлы. Получение корзины по индексу O(1) сложность.
Hash function это функция, которая берет элемент и преобразует его в такой целочисленный индекс.
Следовательно, поскольку область индексов меньше, чем область всех элементов, collision может произойти, и больше элементов может быть помещено в одно ведро, что снижает эффективность поиска элементов. Поэтому наименьшая вероятность столкновения определенно является свойством хэш-функции, к которой нужно стремиться. Другим из них должна быть эффективность вычисления хеша.
Увидеть Идеальная хэш-функция для дальнейшего анализа