Понимание влияния распределения данных на хеширование

Question

Итак, я прочитал страницу Википедии о хэш-функциях, так как сейчас я играю с некоторыми из них. Как на этой странице, так и в других источниках, которые я читал, упоминается, что распределение данных влияет на хеш-функцию.

Несмотря на некоторые объяснения, мне все еще неясно, что это за эффекты и, возможно, почему. Итак, мой вопрос:

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

РЕДАКТИРОВАТЬ 1: Я имею в виду конкретно английский корпус Википедии против данных из более динамичного источника, например, твиты Twitter.

Answer 1

Обычно у вас не так много входных наборов данных, как у вас есть возможные входные данные. Таким образом, распределение является более вероятным, что будет выбран определенный вклад с определенными функциями. (по сути, так же, как вы сказали, но с p<1 для каждого слова вместо некоторого количества n>1) Например, если вы знаете, что первый бит ввода всегда будет равен 1, то данные распределяются неравномерно.

Если бы ваш хэш был очень прост, например. принимая только первый байт в качестве "хэша", тогда это неравномерное распределение приведет к большему количеству коллизий, чем ожидалось. (возможно только 128 значений, хотя вы ожидали получить 256 разных значений)

Большинство (криптографических) хеш-функций, которые вы можете знать по имени, достаточно хороши, так что вам не нужно об этом заботиться. Для криптографии это даже явное условие: вы не должны знать, сколько битов на входе изменилось, просто взглянув на разницу хешей. Это не значит, что это невозможно. Я смутно помню статью, в которой говорилось об увеличении частоты столкновений для md5, когда хэшировались только буквы и цифры ascii. Я не могу найти его прямо сейчас, поэтому наслаждайтесь этой информацией с осторожностью - но даже если я что-то перепутал, такой сценарий легко возможен. И неважно, является ли это md5 или каким-либо другим алгоритмом, если у вас действительно есть такое отношение, то, безусловно, ваше распределение входных наборов данных снова будет актуально.