Если кто-то, как и я, наивно полагает, что std::hash<size_t>()(100) вернет 100, то разработчики стандартной библиотеки С++ в Майкрософт с ним не согласны и считают хеш так:
inline size_t _Hash_seq(const unsigned char *_First, size_t _Count)
{ // FNV-1a hash function for bytes in [_First, _First + _Count)#if defined(_WIN64)
static_assert(sizeof(size_t) == 8, "This code is for 64-bit size_t.");
const size_t _FNV_offset_basis = 14695981039346656037ULL;
const size_t _FNV_prime = 1099511628211ULL;
#else/* defined(_WIN64) */
static_assert(sizeof(size_t) == 4, "This code is for 32-bit size_t.");
const size_t _FNV_offset_basis = 2166136261U;
const size_t _FNV_prime = 16777619U;
#endif/* defined(_WIN64) */
size_t _Val = _FNV_offset_basis;
for (size_t _Next = 0; _Next < _Count; ++_Next)
{ // fold in another byte
_Val ^= (size_t)_First[_Next];
_Val *= _FNV_prime;
}
return (_Val);
}
template<class _Kty>
struct _Bitwise_hash
{ // hash functor for plain old datatypedef _Kty argument_type;
typedef size_t result_type;
size_t operator()(const _Kty& _Keyval) const
{ // hash _Keyval to size_t value by pseudorandomizing transformreturn (_Hash_seq((const unsigned char *)&_Keyval, sizeof (_Kty)));
}
};
template<>
struct hash<long long>
: public _Bitwise_hash<long long>
{ // hash functor for long long
};
Разработчики g++ лишены такой фантазии и тупо делают следующее:
несколько лет назад мы увидели просадку производительности в хешированных контейнерах, где ключами являются численные типы в VS2015
мы присели и подсунули boost::hash в std::unordered_map, стало гораздо лучше ) в VS2015 делают побайтную свертку, оверкил для интегральных типов. математикой надо!
что там в VS2017 не смотрел еще, но вроде обещали улучшить
Здравствуйте, MTD, Вы писали:
MTD>Если кто-то, как и я, наивно полагает, что std::hash<size_t>()(100) вернет 100...
Я бы по умолчанию так не предполагал бы. Возможно, недостаток рандомизации может негативно отразиться в каких-нибудь алгоритмах и структурах данных. Под рандомизацией я имею в виду то желаемое свойство хэш-функции, что для близких значений аргументов обычно возвращает разбросанные хэш-значения.
MTD>то разработчики стандартной библиотеки С++ в Майкрософт с ним не согласны...
Можешь задать этот вопрос непосредственно STL'ю (Stephan T. Lavavej).
Здравствуйте, Qbit86, Вы писали:
Q>Можешь задать этот вопрос непосредственно STL'ю (Stephan T. Lavavej).
Я этот вопрос ему непосредственно задал. Ответом было "намного важнее не допустить вырожденного (O[n]) поведения чем преследовать более частое оптимальное поведение." Т.е. при плохом наборе входных значений текущая хэш-функция всё равно прекрасно перемешает биты и распихает числа по разным бакетам, в то время как identity с радостью всё сложит в один. Я немного поспорил, потому что не согласен с настолько жестоким ударом по ничего не подозревающим программистам, но Степан уверен что так лучше, потому баг в конце концов был закрыт как "by design"
Вроде как есть для этого оправдание: в MSVC используют power-of-2 для числа бакетов, а в остальных стлях — prime number. Получается что при вычислении индекса MSVC делает битовое и, и оставшиеся биты у хэща используются те что были. В гцц/кланге берётся остаток от деления на простое число, который сам по себе достаточно сильно меняет число, но заметно тяжелее как операция. Так identity hash работает отлично для гцц/кланга, но опасен в MSVC.
Выбор степеней двойки как числа бакетов позволяет сконфигурировать контейнер эффективнее если знать входные данные и самому написать хэшфункцию под них, но очень мешает сделать быстро в общем виде. Простые числа работают ровно наоборот.
Здравствуйте, MT-Wizard, Вы писали:
MW>не согласен с настолько жестоким ударом по ничего не подозревающим программистам
Каким ещё «жестоким ударом»? Что хэш-функция перемешивает биты? Как раз наоборот, Принцип Наименьшего Удивления нарушается в случае g++, где для каких-то избранных типов хэш-функция вдруг перестаёт перемешивать биты а возвращает аргумент как есть, просто потому что у него размер такой же, как у хэш-значения. А для чего ещё у них есть такие внезапные оптимизации? Для uint8_t тоже? Для uint128_t просто младшие биты возьмёт?
У стандартных алгоритмов, использующих хэширование, должны быть перегрузки, принимающие хэш-функцию. И если достаточно «тривиальной» хэш-функции — то её тривиально и самому реализовать и явно передать. А по умолчанию пусть будет «рандомизированная» функция.
Здравствуйте, Qbit86, Вы писали:
Q>Каким ещё «жестоким ударом»? Что хэш-функция перемешивает биты? Как раз наоборот, Принцип Наименьшего Удивления нарушается в случае g++, где для каких-то избранных типов хэш-функция вдруг перестаёт перемешивать биты а возвращает аргумент как есть, просто потому что у него размер такой же, как у хэш-значения.
Возвращает она аргумент не потому, что он такого же размера, а потому, что лучшей хеш-функции для целого, чем вернуть само значение не придумать.
Здравствуйте, Qbit86, Вы писали:
MTD>>лучшей хеш-функции для целого, чем вернуть само значение не придумать.
Q>Ты, похоже, не читал ответы в этом треде?
Читал, а ты без кривляний объяснить можешь чем для целых плоха хеш-функция value? Вообще-то это идеальная хеш-функция (такой термин есть), то есть отображает ключ в хеш без коллизий. Переходим к хеш-таблицам, чем плоха хеш-функция k mod M, если M — простое число? Вспомним требования к хеш-функциям:
1. Быстрое вычисление
2. Минимальное число коллизий
Можешь привести за и против по этим требованиям при озвученных в первом посте подходах?
Перечитай комментарий от @MT-Wizard выше. Согласно ему:
в MSVC используют power-of-2 для числа бакетов, а в остальных стлях — prime number. Получается что при вычислении индекса MSVC делает битовое и, и оставшиеся биты у хэща используются те что были. В гцц/кланге берётся остаток от деления на простое число, который сам по себе достаточно сильно меняет число, но заметно тяжелее как операция. Так identity hash работает отлично для гцц/кланга, но опасен в MSVC.
MTD>Вообще-то это идеальная хеш-функция (такой термин есть), то есть отображает ключ в хеш без коллизий. Переходим к хеш-таблицам, чем плоха хеш-функция k mod M, если M — простое число?
Во-первых, если верить @MT-Wizard, M — не простое число, а степень двойки в хэш-таблицах реализации Microsoft. Во-вторых, в любом случае (хоть степень, хоть простое), для такой функции есть плохие наборы { k_i } — для которых k_i даёт одинаковый остаток при делении на M. Скажем, арифметические прогрессии с такой разностью, или просто куча разных чисел вида p_i*M + r. Для степеней двойки получить такие наборы в «реальной жизни» кажется более правдоподобным, чем для простого M. Но тем не менее, вполне могут быть наборы из какого-нибудь решета. То есть наивная identity-хэш-функция может сносно работать для случайных наборов данных и вдруг встревать на наборах с нехитрой закономерностью.
Для того и нужна «рандомизация», она страхует от плохих наборов. Не требует «случайности» исходных данных, а сама её «генерирует». Теоретически может быть набор ключей, который породит коллизии и для конкретной рандомизированной функции, но он должен быть сконструирован специально под эту функцию, вероятность получить такое «в быту» минимальная (как у любого другого случайного набора).
Здравствуйте, Qbit86, Вы писали:
Q>Во-первых, если верить @MT-Wizard, M — не простое число, а степень двойки в хэш-таблицах реализации Microsoft.
К обсуждению хеш-функции отношения не имеет.
Q>Во-вторых, в любом случае (хоть степень, хоть простое), для такой функции есть плохие наборы { k_i } — для которых k_i даёт одинаковый остаток при делении на M. Скажем, арифметические прогрессии с такой разностью, или просто куча разных чисел вида p_i*M + r. Q>То есть наивная identity-хэш-функция может сносно работать для случайных наборов данных и вдруг встревать на наборах с нехитрой закономерностью.
Мы хеш-функцию обсуждаем или реализацию хеш-таблицы? Как хеш-функция реализация от Майкрософт очевидно сливает и по быстродействию и по коллизиям. По хеш-таблицам же справедливо в обе стороны, алгоритм от Майкрософт тоже может споткнуться на какой-то последовательности.
Q>Теоретически может быть набор ключей, который породит коллизии и для конкретной рандомизированной функции, но он должен быть сконструирован специально под эту функцию, вероятность получить такое «в быту» минимальная (как у любого другого случайного набора).
Осталось понять стоит ли эта теоретическая вероятность такой реальной просадки быстродействия здесь и сейчас.
Здравствуйте, MTD, Вы писали:
MTD>Вообще-то это идеальная хеш-функция (такой термин есть), то есть отображает ключ в хеш без коллизий.
Важны не коллизии функции id, а коллизии при вычислении индекса корзины. Если индекс рассчитывается как k mod M, то коллизии будут при arity(k) > arity(M).
Q>>Во-первых, если верить @MT-Wizard, M — не простое число, а степень двойки в хэш-таблицах реализации Microsoft. MTD>К обсуждению хеш-функции отношения не имеет.
На практике имеет. Не принципиально (то есть те же рассуждения применимы к любому M). Но для степени двойки наглядно в битовом представлении: если брать k mod M, то хэш будет зависеть только от младших разрядов ключа, и не зависеть от старших. Это нежелательное поведение хэш-функции. Если M простое, то ещё куда ни шло.
MTD>Мы хеш-функцию обсуждаем или реализацию хеш-таблицы?
Это связанные вещи, так как хэш-функция используется в реализации хэш-таблиц. Об этом и говорит Stephan T. Lavavej, которого процитировал @MT-Wizard. (По-прежнему советую прочитать его комментарий.)
MTD>По хеш-таблицам же справедливо в обе стороны, алгоритм от Майкрософт тоже может споткнуться на какой-то последовательности.
На какой-то специально подобранной последовательности, которая в остальном выглядит как случайная. В то время как нерандомизированная хэш-функция может споткнуться на обычных данных, которые неслучайны, и время от времени бывают biased.
MTD>Осталось понять стоит ли эта теоретическая вероятность такой реальной просадки быстродействия здесь и сейчас.
При делении на степень двойки (как в хэш-таблицах Microsoft) рандомизировать, вероятно, стоит. При делении на простое число (как в других хэш-таблицах), вероятно, нет.
Здравствуйте, Qbit86, Вы писали:
MTD>>Вообще-то это идеальная хеш-функция (такой термин есть), то есть отображает ключ в хеш без коллизий.
Q>Важны не коллизии функции id, а коллизии при вычислении индекса корзины.
Это смотря, что за задача, возможно мне хеш нужен не для таблицы.
Q>Если индекс рассчитывается как k mod M, то коллизии будут при arity(k) > arity(M).
А если у тебя количество бакетов — степень двойки и номер бакета hash(k) & M коллизий не будет что-ли?
Q>>>Во-первых, если верить @MT-Wizard, M — не простое число, а степень двойки в хэш-таблицах реализации Microsoft. MTD>>К обсуждению хеш-функции отношения не имеет.
Q>На практике имеет. Не принципиально (то есть те же рассуждения применимы к любому M). Но для степени двойки наглядно в битовом представлении: если брать k mod M, то хэш будет зависеть только от младших разрядов ключа, и не зависеть от старших. Это нежелательное поведение хэш-функции. Если M простое, то ещё куда ни шло.
На какой практике? Допустим, мне просто нужен хеш, при хеш = k коллизий гарантировано нет. Что лучше чтобы считать номер бакета деление или наложение маски я не уверен, у тебя есть информация?
Q>Это связанные вещи, так как хэш-функция используется в реализации хэш-таблиц. Об этом и говорит Stephan T. Lavavej, которого процитировал @MT-Wizard. (По-прежнему советую прочитать его комментарий.)
Я комментарий прочел, он меня не убедил, я считаю, что это переусложнение с потерей производительности, в чем профит я пока не понял.
Q>На какой-то специально подобранной последовательности, которая в остальном выглядит как случайная. В то время как нерандомизированная хэш-функция может споткнуться на обычных данных, которые неслучайны, и время от времени бывают biased.
Не убедительно. Почему в одном случае надо специально подбирать, а во втором само получится?
MTD>>Осталось понять стоит ли эта теоретическая вероятность такой реальной просадки быстродействия здесь и сейчас.
Q>При делении на степень двойки (как в хэш-таблицах Microsoft) рандомизировать, вероятно, стоит. При делении на простое число (как в других хэш-таблицах), вероятно, нет.
Будут при arity(k) > arity(M). Это пример был к тому, что твоя identity — никак не «идеальная».
MTD>Допустим, мне просто нужен хеш, при хеш = k коллизий гарантировано нет.
Так и используешь k, не вызывая никаких std::hash.
MTD>Не убедительно. Почему в одном случае надо специально подбирать, а во втором само получится?
Вот скажем ты отфильтровал из базы всех пользователей-женщин, и используешь их идентификаторы как ключи. А админ базы в своё время решил при создании всем пользователям-женщинам назначать id кратный 7, мол, их всё равно в шесть раз меньше в компании; почему нет. У тебя образовалась неявная связь, не случайная. А если у тебя рандомизация, без явной закономерности, то в такие совпадения почти невозможно попасть. Нет правдоподобных сценариев.
MTD>То есть в Майкрософте сделали фигню? Ну ок.
Почему фигню, если вычислять индекс делением на степень двойки быстрее, чем делением на простое число?
Какой авторитетный источник. В стандарте тоже написано, что использовать только с хеш-контейнерами? Почему тогда не сделана внутренней?
Q>Будут при arity(k) > arity(M). Это пример был к тому, что твоя identity — никак не «идеальная».
Да, но лучше того, что сделали в Майкрософт.
MTD>>Допустим, мне просто нужен хеш, при хеш = k коллизий гарантировано нет.
Q>Так и используешь k, не вызывая никаких std::hash.
Мне нужно через std::hash — я обобщенный код пишу.
MTD>>Не убедительно. Почему в одном случае надо специально подбирать, а во втором само получится?
Q>Вот скажем ты отфильтровал из базы всех пользователей-женщин, и используешь их идентификаторы как ключи. А админ базы в своё время решил при создании всем пользователям-женщинам назначать id кратный 7, мол, их всё равно в шесть раз меньше в компании; почему нет. У тебя образовалась неявная связь, не случайная. А если у тебя рандомизация, без явной закономерности, то в такие совпадения почти невозможно попасть. Нет правдоподобных сценариев.
Совсем не убедительно.
MTD>>То есть в Майкрософте сделали фигню? Ну ок.
Q>Почему фигню, если вычислять индекс делением на степень двойки быстрее, чем делением на простое число?
А до этого в цикле 8 раз умножить и 8 раз сделать xor. Хммм, и правда быстрее
Или не только cppreference.com, но и cplusplus.com недостаточно авторитетный источник?
MTD>В стандарте тоже написано, что использовать только с хеш-контейнерами?
Не знаю, у меня нет под рукой стандарта. Я его не покупал.
MTD>Почему тогда не сделана внутренней?
Чтобы можно было специализировать?
Q>>Будут при arity(k) > arity(M). Это пример был к тому, что твоя identity — никак не «идеальная». MTD>Да, но лучше того, что сделали в Майкрософт.
Если используются просто как контрольная сумма, то конечно лучше.
MTD>Мне нужно через std::hash — я обобщенный код пишу.
Значит, тебе не нужно через std::hash, а нужно через свою хэш-функцию со специализацией для size_t.
MTD>Совсем не убедительно.
И тем не менее, случаи biased-данных, что ломают наивные сортировки или хэш-таблицы, периодически встречаются. Не у всех и не у каждого, но не исчезающе редко.
Какой авторитетный источник. В стандарте тоже написано?
Q>>>Будут при arity(k) > arity(M). Это пример был к тому, что твоя identity — никак не «идеальная». MTD>>Да, но лучше того, что сделали в Майкрософт.
Q>Если используются просто как контрольная сумма, то конечно лучше.
Контрольная сумма и хеш вещи разные, созданы для разного. Задача хеша — мапить ключ в хеш, задача контрольной суммы — проверка целостности.
MTD>>Мне нужно через std::hash — я обобщенный код пишу.
Q>Значит, тебе не нужно через std::hash, а нужно через свою хэш-функцию со специализацией для size_t.
Я не хочу переписывать стандартную библиотеку.
Q>И тем не менее, случаи biased-данных, что ломают наивные сортировки или хэш-таблицы, периодически встречаются. Не у всех и не у каждого, но не исчезающе редко.
Из практики есть пример, когда обсуждаемая хеш-функция работала плохо? Любопытно, квиксорт — наивная сортировка?
Здравствуйте, MTD, Вы писали:
MTD>Какой авторитетный источник. В стандарте тоже написано?
Увы, стандарта у меня нет, так что ответить не смогу. Так и быть, пусть уверенность в твоей правоте продолжает держаться на этой хрупкой надежде, что хоть в стандарте-то наверное и не говорится про назначение функции std::hash.
MTD>Контрольная сумма и хеш вещи разные, созданы для разного. Задача хеша — мапить ключ в хеш, задача контрольной суммы — проверка целостности.
Ведь ты так и не открыл нам секрет, зачем используешь функцию hash. Остаётся только строить догадки.
MTD>Любопытно, квиксорт — наивная сортировка?
Тот квиксорт, как он изучается в школе — конечно, наивная. Для защиты от неудачных входных массивов при выборе пивота используется медиана трёх или другие уловки с рандомизацией. Для хрестоматийного двустрочника на Хаскеле якобы быстрой сортировки «плохие» входные данные совсем тривиальны.
Здравствуйте, Qbit86, Вы писали:
Q>Увы, стандарта у меня нет, так что ответить не смогу. Так и быть, пусть уверенность в твоей правоте продолжает держаться на этой хрупкой надежде, что хоть в стандарте-то наверное и не говорится про назначение функции std::hash.
Ты какой-то смешной — для тебя спор не средство узнать что-то новое и выяснить истину, а средство самоутвердиться.
MTD>>Контрольная сумма и хеш вещи разные, созданы для разного. Задача хеша — мапить ключ в хеш, задача контрольной суммы — проверка целостности.
Q>Ведь ты так и не открыл нам секрет, зачем используешь функцию hash. Остаётся только строить догадки.
Я std::hash использую чтобы вычислить хеш.
MTD>>Любопытно, квиксорт — наивная сортировка?
Q>Тот квиксорт, как он изучается в школе — конечно, наивная. Для защиты от неудачных входных массивов при выборе пивота используется медиана трёх или другие уловки с рандомизацией.
Здравствуйте, MTD, Вы писали:
Q>>Увы, стандарта у меня нет, так что ответить не смогу. Так и быть, пусть уверенность в твоей правоте продолжает держаться на этой хрупкой надежде, что хоть в стандарте-то наверное и не говорится про назначение функции std::hash. MTD>Ты какой-то смешной
Нет, ты. Со всеми этими «неавторитетными источниками» и прочими «поубеждайте меня тут».
MTD> — для тебя спор
Для меня это не спор. Я пишу комментарии не для тебя, а для аудитории, читающей этот тред. Нет цели переубедить именно тебя; это очевидно бесполезное и неблагодарное занятие.
MTD>не средство узнать что-то новое и выяснить истину
Как это, узнал же новое. Вот, например, раньше я не знал, что в Microsoft и GCC функция std::hash() реализована по-разному. И в свете того, что сказал @MT-Wizard, это вполне имеет рациональное зерно.
MTD>Выбор опорной точки не поможет.
Как это не поможет? Качество выбора опорной точки в принципе определяет скорость алгоритма Быстрой сортировки. А именно: выбор опорной точки влияет на то, насколько сбалансированными будут ветки дерева вызовов. Если одна из веток постоянно будет вырождаться в максимально длинную, то общая скорость деградирует до квадратичной.
Конечно, конечно, это же я с ходу сказал, что оппонент не читал тему.
MTD>> — для тебя спор
Q>Нет цели переубедить именно тебя; это очевидно бесполезное и неблагодарное занятие.
И снова я начинаю, да, да.
Q>Как это, узнал же новое. Вот, например, раньше я не знал, что в Microsoft и GCC функция std::hash() реализована по-разному. И в свете того, что сказал @MT-Wizard, это вполне имеет рациональное зерно.
Еще тебе надо почитать про контрольные суммы и хеши, чтобы не путаться и про быструю сортировку, еще про стоимость операций. Не благодари.
MTD>>Выбор опорной точки не поможет.
Q>Как это не поможет?
Да вот так. На отсортированных данных как опорные точки не ставь скорость алгоритма деградирует до квадратичной.
