Хэш-функция C ++, как выглядит оригинальный хэзер, т. Е. Hash & lt; int xkey & gt; реализованы
Я новичок в хешировании в целом, а также в мире STL и увидел новое станд :: unrdered_set и SGI: hash_set, оба из которых используют хэш хэш. Я понимаю, что для получения хорошего коэффициента загрузки вам может потребоваться написать собственную хэш-функцию, и я смог ее написать.
Тем не менее, я пытаюсь углубиться в то, как написано оригинальное значение по умолчанию has_functions.
Мой вопрос:
1) Как пишется оригинальный HashFcn по умолчанию; Конкретнее, как генерируется хеш?
Это основано на каком-то псевдослучайном числе. Может кто-нибудь указать мне какой-нибудь заголовочный файл (я немного потерян с документацией), где я могу посмотреть; как реализован хеш хэш
2) Как это гарантирует, что каждый раз вы сможете получить один и тот же ключ?
Пожалуйста, дайте мне знать, если я смогу прояснить мои вопросы в любом случае?
Решение
В версии gcc, которую я здесь установил, необходимые хеш-функции находятся в /usr/lib/gcc/i686-pc-cygwin/4.7.3/include/c++/bits/functional_hash.h
Хэши для целочисленных типов определяются с помощью макроса _Cxx_hashtable_define_trivial_hash, Как и следовало ожидать от названия, это просто приводит значение ввода к size_t,
Вот как это делает GCC. Если вы используете gcc, то у вас должен быть файл с аналогичным именем. Если вы используете другой компилятор, то источник будет где-то еще. Не обязательно, чтобы каждая реализация использовала тривиальный хеш для целочисленных типов, но я подозреваю, что это очень распространено.
Он не основан на генераторе случайных чисел, и, надеюсь, теперь вам совершенно очевидно, как эта функция гарантирует, что каждый раз будет возвращать один и тот же ключ для одного и того же ввода! Причина использования тривиального хэша в том, что он настолько быстр, насколько это возможно. Если это дает плохое распределение для ваших данных (потому что ваши значения имеют тенденцию сталкиваться по модулю количества сегментов), тогда вы можете использовать другую, более медленную хэш-функцию или другое количество сегментов (std::unordered_set не позволяет указать точное количество сегментов, но позволяет установить минимум). Поскольку разработчики библиотек ничего не знают о ваших данных, я думаю, что они не будут использовать более медленные хеш-функции по умолчанию.
Другие решения
Хеш-функция должна быть детерминированной — то есть один и тот же вход должен всегда давать один и тот же результат.
Вообще говоря, вы хочу хеш-функция для получения всех выходов с примерно равной вероятностью для произвольных входных данных (но, хотя желательно, это не является обязательным — и для любой данной хэш-функции всегда будет произвольное количество входных данных, которые производят идентичные выходные данные).
Вообще говоря, вы хотите, чтобы хеш-функция была быстрой и зависела (хотя бы до некоторой степени) от всего ввода.
Довольно часто встречающийся шаблон: начните с некоторого полуслучайного ввода. Объедините один байт ввода с текущим значением. Сделайте что-нибудь, что переместит биты (умножение, вращение и т. Д.) Повторите для всех байтов ввода.