Здравствуйте, 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) рандомизировать, вероятно, стоит. При делении на простое число (как в других хэш-таблицах), вероятно, нет.