Хеш‑функции. Часть 1: Основы

[Dhwtj]

В каком-то смысле перейти от O(n) к О(ln n) а в некоторых задачах к О(1) это алгоритмическое чудо хешмапы, под которым мощные математические основы теории информации.

[PXI]

И всю эту красоту и быстроту ломают коллизии

[Dhwtj]

В среднем ок

[rukhi7]

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

[Dhwtj]

Ну, если поискать, то в основе хешмапы принцип Дирихле: сжатие влечёт коллизии. Там же рядом фильтр Блума про частоту этих ошибок и там же про необходимое количество памяти.

Это самое близкое к Котельникову: бюджет битов против точности, как частота дискретизации против полосы.

[rukhi7]

В противном случае все ваши входные варианты будет несложно захешировать и перебором разгадать ваши исходные данные по дайджесту.

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

[PXI]

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