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