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

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

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


algorithm hash message-digest
person Alvida    schedule 13.04.2015    source источник
comment
хэш представляет собой сжатую (с потерями) версию исходных данных. Было бы мало данных для хеширования, меньших размера хэша. Если бы он был меньше, то вы, вероятно, могли бы его восстановить....   -  person Mitch Wheat    schedule 13.04.2015
comment
даже хеширование больших данных дает тот же размер, не так ли? Мой вопрос в том, почему дизайнер спроектировал его таким, хотя...   -  person Alvida    schedule 13.04.2015
comment
Разный размер, по-видимому, дал бы некоторые подсказки к исходной композиции (?)   -  person Mitch Wheat    schedule 13.04.2015
comment
Это звучит тоже возможно, @MitchWheat: D Это также из-за проблемы с памятью, как описано j_random_hacker, я думаю: D   -  person Alvida    schedule 14.04.2015

Ответы (3)


arrow_upward
5
arrow_downward

Потому что это определение хэша. См. википедию.

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

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

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

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

person Alex    schedule 13.04.2015

arrow_upward
1
arrow_downward

Как видите, это стандарт.

Также то, что вы хотите, указано в стандарте:

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

person Lrrr    schedule 13.04.2015

arrow_upward
1
arrow_downward

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

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

person j_random_hacker    schedule 13.04.2015