История.
Хеширование
Рисунок 1.1 — Пример коллизии При открытой адресации в каждой ячейке хеш-таблицы хранится только один элемент. Тогда при добавлении, если ячейка свободна, мы просто записываем добавляемый элемент в эту ячейку. Однако если эта ячейка занята — необходимо поместить добавляемый элемент в какую-нибудь другую свободную ячейку. Такие ситуации нередки, так как невозможно использовать хеш-функцию… Читать ещё >
История. Хеширование (реферат, курсовая, диплом, контрольная)
Дональд Кнут относит первую систематическую идею хеширования к сотруднику IBM Хансу Петеру Луну, предложившему хеш-кодирование в январе 1953 года.
В 1956 году Арнольд Думи в своей работе «Computers and automation» первым представил концепцию хеширования таковой, какой её знает большинство программистов сейчас. Думи рассматривал хеширование, как решение «Проблемы словаря», а также предложил использовать в качестве хеш-адреса остаток деления на простое число.
Первой серьёзной работой, связанной с поиском в больших файлах, была статья Уэсли Питерсона в IBM Journal of Research and Development 1957 года, в которой он определил открытую адресацию, а также указал на ухудшение производительности при удалении. Спустя шесть лет была опубликована работа Вернера Бухгольца, в которой проведено обширное исследование хеш-функций. В течение нескольких последующих лет хеширование широко использовалось, однако не было опубликовано никаких значимых работ.
В 1967 году хеширование в современном значении упомянуто в книге Херберта Хеллермана «Принципы цифровых вычислительных систем». В 1968 году Роберт Моррис опубликовал в Communications of the ACM большой обзор по хешированию, эта работа считается ключевой публикацией, вводящей понятие о хешировании в научный оборот и закрепившей ранее применявшийся только в жаргоне специалистов термин «хеш».
Разрешение коллизий
Разрешение коллизий в хеш-таблице, задача, решаемая несколькими способами. Можно использовать списки, а можно открытую адресацию (рисунок 1.1).
Рисунок 1.1 — Пример коллизии При открытой адресации в каждой ячейке хеш-таблицы хранится только один элемент. Тогда при добавлении, если ячейка свободна, мы просто записываем добавляемый элемент в эту ячейку. Однако если эта ячейка занята — необходимо поместить добавляемый элемент в какую-нибудь другую свободную ячейку. Такие ситуации нередки, так как невозможно использовать хеш-функцию, не дающую коллизий, а каждой ячейке таблицы соответствует одно значение хеш-функции. Далее мы рассмотрим несколько стратегий поиска свободного места в данном случае.