Здравствуйте, MTD, Вы писали:

MTD>Читал

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

Для того и нужна «рандомизация», она страхует от плохих наборов. Не требует «случайности» исходных данных, а сама её «генерирует». Теоретически может быть набор ключей, который породит коллизии и для конкретной рандомизированной функции, но он должен быть сконструирован специально под эту функцию, вероятность получить такое «в быту» минимальная (как у любого другого случайного набора).

Здравствуйте, MTD, Вы писали:

MTD>Читал

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

Для того и нужна «рандомизация», она страхует от плохих наборов. Не требует «случайности» исходных данных, а сама её «генерирует». Теоретически может быть набор ключей, который породит коллизии и для конкретной рандомизированной функции, но он должен быть сконструирован специально под эту функцию, вероятность получить такое «в быту» минимальная (как у любого другого случайного набора).