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

Q>Во-первых, если верить @MT-Wizard, M — не простое число, а степень двойки в хэш-таблицах реализации Microsoft.

К обсуждению хеш-функции отношения не имеет.

Q>Во-вторых, в любом случае (хоть степень, хоть простое), для такой функции есть плохие наборы { k_i } — для которых k_i даёт одинаковый остаток при делении на M. Скажем, арифметические прогрессии с такой разностью, или просто куча разных чисел вида p_i*M + r.
Q>То есть наивная identity-хэш-функция может сносно работать для случайных наборов данных и вдруг встревать на наборах с нехитрой закономерностью.

Мы хеш-функцию обсуждаем или реализацию хеш-таблицы? Как хеш-функция реализация от Майкрософт очевидно сливает и по быстродействию и по коллизиям. По хеш-таблицам же справедливо в обе стороны, алгоритм от Майкрософт тоже может споткнуться на какой-то последовательности.

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

Осталось понять стоит ли эта теоретическая вероятность такой реальной просадки быстродействия здесь и сейчас.