Вы слышали о Луне, верно? Ганс Петер Лун? Чувак, кто изобрел алгоритм хеширования? Что ж, для тех из вас, кто не обратил внимание на CompSci 101 в самом начале, в IEEE Spectrum есть отличная статья о его наследии.
В начале 1953 года Лун написал внутреннюю записку IBM, в которой предлагал размещать информацию в «сегментах», чтобы ускорить поиск. Допустим, вы хотели найти телефонный номер в базе данных и узнать, кому он принадлежит. Учитывая 10-значное число 314–159–2652, компьютер может просто искать в списке по одному номеру за раз, пока не найдет соответствующую запись. Однако в базе данных с миллионами номеров это может занять некоторое время.
Идея Луна заключалась в том, чтобы назначить каждой записи пронумерованное ведро следующим образом: цифры телефонного номера были сгруппированы в пары (в данном случае 31, 41, 59, 26, 52). Затем парные цифры складывались вместе (4, 5, 14, 8, 7), из которых генерировалось новое число, состоящее из каждого однозначного результата или, в случае двузначного результата, только из последней цифры. (получив 45487). Исходный номер телефона и соответствующее ему имя или адрес будут помещены в корзину с пометкой 45487.
Поиск записи по номеру телефона включал быстрое вычисление номера корзины с помощью метода Луна, а затем извлечение информации из этой корзины. Даже если в каждом сегменте было несколько записей, последовательный поиск в одном сегменте был намного быстрее, чем во всем списке.
На протяжении десятилетий специалисты по информатике и программисты совершенствовали методы Луна и применяли их по-новому. Но основная идея осталась прежней: используйте математическую задачу, чтобы организовать данные в сегменты, которые легко найти. Поскольку организация и поиск данных являются широко распространенными проблемами в вычислительной технике, алгоритмы хэширования стали критически важными для криптографии, графики, телекоммуникаций и биологии. Каждый раз, когда вы отправляете номер кредитной карты через Интернет или пользуетесь словарем текстового процессора, работают хеш-функции.
Прочитайте остальное на https://spectrum.ieee.org/tech-history/silicon-revolution/hans-peter-luhn-and-the-birth-of-the-hashing-algorithm
