Почему хэш-выход фиксирован в длину?

Question

Хэш-функции всегда производят выход фиксированной длины независимо от входа (то есть MD5 >> 128 бит, SHA-256 >> 256 бит), но почему?

Я знаю, что именно так проектировал их проектировщик, но почему они спроектировали вывод равной длины? Чтобы он мог храниться в последовательном порядке? проще сравнивать? менее сложно?

Answer 1

Потому что это определение хеширования. Обратитесь к wikipedia

A хэш-функции любая функция, которая может быть использована для отображения цифровых данных произвольного размера цифровых данных фиксированного размера .

Если ваш вопрос касается того, почему это полезно для хэша, чтобы быть фиксированным размером есть несколько причин (не исчерпывающий список):

• Хэш обычно кодирует больше (часто произвольно размер) в меньшем размере, как правило, с потерями, т. е. в отличие от функций сжатия, вы не можете восстановить входные данные из хэш-значения путем «реверсирования» процесса.
• Наличие выхода фиксированного размера удобно, особенно для хешей, предназначенных для использования в качестве ключа поиска.
• Вы можете предсказуемо (предварительно) распределить память для хэш-значений и индексировать их в смежном сегменте памяти, таком как массив.
• Для хэшей "родных размеров слова", например. 16, 32 и 64 битных целочисленных значения, вы можете очень быстро выполнить сравнение равенства и упорядочения.
• Любой алгоритм, работающий с хэш-значениями, может использовать один набор операций фиксированного размера для их создания и обработки.
• Вы можете предсказуемо комбинировать хэши, созданные с различными хеш-функциями, например. a bloom filter.
• Вам не нужно тратить какое-либо пространство, чтобы закодировать, насколько велика величина хэш-функции.

Существуют специальные хеш-функции, которые могут создавать выходной хэш определенной фиксированной длины, например так называемый sponge functions.

Answer 2

Как вы можете видеть, это standard.

Кроме того, что вы хотите указано в стандарте:

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

Answer 3

Часто это потому, что вы хотите использовать хеш-значение или его часть для быстрого хранения и поиска значений в массиве фиксированного размера. (Так работает, например, не-изменяемая хэш-таблица.)

И зачем использовать массив фиксированного размера вместо какой-либо другой, растущей структуры данных (например, связанного списка или двоичного дерева)? Поскольку доступ к ним имеет тенденцию быть как теоретически, так и практически быстрым: при условии, что хеш-функция хороша, а доля занятых записей в таблице не слишком высока, вы получаете O (1) поиск (по сравнению с O (log n) поиском для дерева основанные на данных структуры или O (n) для списков) в среднем. И эти обращения на практике бывают быстрыми: после вычисления хэша, который обычно занимает линейное время в размере ключа с низкой скрытой константой, часто происходит просто сдвиг бит, бит-маска и один или два косвенных обращения к памяти в смежные блок (a) хорошо использует кеш и (b) хорошо подходит для современных процессоров, потому что требуется небольшое количество указателей.