Введение - Динамическое хеширование
С хешированием мы сталкиваемся едва ли не на каждом шагу: при работе с браузером (список Web-ссылок), текстовым редактором и переводчиком (словарь), языками скриптов (Perl, Python, PHP и др.), компилятором (таблица символов). По словам Брайана Кернигана, это "одно из величайших изобретений информатики". Заглядывая в адресную книгу, энциклопедию, алфавитный указатель, мы даже не задумываемся, что упорядочение по алфавиту является не чем иным, как хешированием.
Хеширование есть разбиение множества ключей (однозначно характеризующих элементы хранения и представленных, как правило, в виде текстовых строк или чисел) на непересекающиеся подмножества (наборы элементов), обладающие определенным свойством. Это свойство описывается функцией хеширования, или хеш-функцией, и называется хеш-адресом. Решение обратной задачи возложено на хеш-структуры (хеш-таблицы): по хеш-адресу они обеспечивают быстрый доступ к нужному элементу. В идеале для задач поиска хеш-адрес должен быть уникальным, чтобы за одно обращение получить доступ к элементу, характеризуемому заданным ключом (идеальная хеш-функция). Однако, на практике идеал приходится заменять компромиссом и исходить из того, что получающиеся наборы с одинаковым хеш-адресом содержат более одного элемента.
Термин "хеширование" (hashing) в печатных работах по программированию появился сравнительно недавно (1967 г., [1]), хотя сам механизм был известен и ранее. Глагол "hash" в английском языке означает "рубить, крошить". Для русского языка академиком А. П. Ершовым [2] был предложен достаточно удачный эквивалент -- "расстановка", созвучный с родственными понятиями комбинаторики, такими как "подстановка" и "перестановка". Однако он не прижился.
Как отмечает Дональд Кнут [3], идея хеширования впервые была высказана Г. П. Ланом при создании внутреннего меморандума IBM в январе 1953 г. с предложением использовать для разрешения коллизий хеш-адресов метод цепочек. Примерно в это же время другой сотрудник IBM - Жини Амдал - высказала идею использования открытую линейную адресацию. В открытой печати хеширование впервые было описано Арнольдом Думи (1956), указавшим, что в качестве хеш-адреса удобно использовать остаток от деления на простое число. А. Думи описывал метод цепочек для разрешения коллизий, но не говорил об открытой адресации. Подход к хешированию, отличный от метода цепочек, был предложен А. П. Ершовым (1957, [2]), который разработал и описал метод линейной открытой адресации. Среди других исследований можно отметить работу Петерсона (1957, [4]). В ней реализовывался класс методов с открытой адресацией при работе с большими файлами. Петерсон определил открытую адресацию в общем случае, проанализировал характеристики равномерного хеширования, глубоко изучил статистику использования линейной адресации на различных задачах. В 1963 г. Вернер Букхольц [6] опубликовал наиболее основательное исследование хеш-функций. хеширование ключ адресация петерсон
К концу шестидесятых годов прошлого века линейная адресация была единственным типом схемы открытой адресации, описанной в литературе, хотя несколькими исследователями независимо была разработана другая схема, основанная на неоднократном случайном применении независимых хеш-функции ([3], стр. 585). В течение нескольких последующих лет хеширование стало широко использоваться, хотя не было опубликовано никаких новых работ. Затем Роберт Моррис [5] обширный обзор по хешированию и ввел термин "рассеянная память" (scatter storage). Эта работа привела к созданию открытой адресации с двойным хешированием.
Далее будут рассмотрены основные виды хеш-функций и некоторые их модификации, методы разрешения коллизий, проблемы удаления элементов из хеш-таблицы, а также некоторые варианты применения хеширования.
Похожие статьи
-
Введение - Программное обеспечение расчета конструкций
Метод конечных элементов является одним из наиболее распространенных методов решения задач математической физики. Это связано с большой универсальностью...
-
Введение - Разработка веб-редактора для описания лексико-семантических шаблонов на визуальном языке
Объем неупорядоченной и неструктурированной текстовой информации неуклонно растет, поэтому задача ее быстрой и качественной обработки актуальна сегодня...
-
Введение - Объектно-ориентированный подход и диаграммы классов в UML
Психологи уже давно показали, что средний человек может одновременно воспринимать адекватно в пределах десятка единиц информации. Таким образом, при...
-
Введение - Функциональные модели универсального нейрокомпьютера
Общая характеристика работы Актуальность темы. В 80-е годы развитие информатики и средств вычислительной техники во многом определялось программой "Пятое...
-
Введение - Линейное программирование
Линейное программирование - это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой...
-
Введение - Алгоритмы компьютерного моделирования
В современном мире все чаще возникает необходимость предсказать поведение физической, химической, биологической и других систем. Одним из способов...
-
ВВЕДЕНИЕ - Разработка программы на языке C++, реализующей игру "Морской бой"
Данная курсовая работа направлена на изучение принципов объектно-ориентированного программирования. Разработать программу на языке C++, реализующую игру...
-
В нашей курсовой работе была поставлена задача создания обучающей программы по информатике, с помощью которой студенты смогут проверить свои знания в...
-
В данной выпускной квалификационной работе разработан прототип умного почтового ящика, удаленного сетевого устройства для контроля почтовой...
-
Введение - Карманный персональный компьютер
Данная тема работы была выбрана мной из-за стремительного развития карманных компьютеров. Наверняка все стали замечать, что рынок карманных компьютеров...
-
Введение - База данных "Определение факультативов для студентов"
Система баз данных -- это, по сути, не что иное, как компьютеризированная система хранения однотипных записей. Саму же базу данных можно рассматривать...
-
На сегодняшний день существует проблема в отсутствии определенного исполнения специализированных отечественных программируемых микросхем для...
-
Метод конечных элементов (МКЭ) жесткости возник в аэрокосмической отрасли. Исследователи рассматривали различные подходы к анализу сложных частей...
-
Введение - Транспортная задача линейного проектирования
В настоящее время оптимизация находит применение в науке, технике и в любой другой области человеческой деятельности. Оптимизация - целенаправленная...
-
Введение - Один алгоритм сжатия изображения
Сжатие цифровых изображений -- одна из задач цифровой обработки изображений, наряду с сегментацией, морфологической обработкой, распознаванием образов и...
-
Введение - Виды и возможности СУБД
База данных, говоря коротко -- это средство для реляционного и эффективного хранения информации. Иными словами, такая база обеспечивает надежную защиту...
-
Введение - Использование методов линейного программирования
Линейное программирование -- область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся...
-
Введение - Основные понятия политики информационной безопасности
Говоря об информационной безопасности, в настоящее время имеют в виду, собственно говоря, безопасность компьютерную. Действительно, информация,...
-
Введение, Понятие растровой графики - Растровая графика
Компьютерная графика на данный момент используется очень широко. Существует два вида графики: векторная и растровая. На данный момент она используется...
-
Использование муравьиных алгоритмов для решения задачи поиска оптимального маршрута в графе Цель работы Изучить метод муравьиных колоний. Научиться...
-
В современном мире ни одна сфера жизни не обходится без использования информационных технологий (ИТ) и их составляющих. Сегодня повсеместно применяются...
-
Введение - Обьекто-ориентированное программирование
Объектно-ориентированное программирование (ООП) позволяет разложить проблему на составные части, каждая из которых становится самостоятельным объектом....
-
Введение - Создание аналога системной утилиты "Диспетчер задач"
В настоящее время существует большое количество полезных программ, предназначенных для улучшения работы вашего персонального компьютера. К выбору утилит...
-
Введение - Анализ НМ-сети с разнотипными заявками в нестационарном режиме и ее применение
ПОСТАНОВКА ЗАДАЧИ. Моделирование - один из наиболее распространенных методов исследования процессов функционирования сложных систем. Известно достаточно...
-
Введение - Создание приложения
Японский упражнение лингвистический приложение Темой данной работы является разработка приложения под управлением операционной системы Android для...
-
Введение, Ядро Parasolid - Ядро Parasolid
ANSYS -- универсальная программная система конечно-элементного (МКЭ) анализа, существующая и развивающаяся на протяжении последних 30 лет, является...
-
Введение, Постановка задачи - Бизнес-процесс проведения капитального ремонта в цехе предприятия
Модели бизнес-процессов используются для обоснования функций информационной системы, направленных на внедрение информационной технологии для управления...
-
Введение - Пользовательский контент
Мы живем в информационную эру -- эпоху, когда информация и знания представляют высшую ценность в обществе, а также, которая отличается практически...
-
В курсовой работе в соответствии с заданием на проектирование решается задача разработки программы вычисления определенных интегралов численными...
-
Введение - Разработка справочной информационной системы "Рецепты"
Задание курсовой работы. Разработать и отладить информационную справочную систему "Рецепты", которая будет позволять хранить, выводить на экран,...
-
Введение. - Архитектура персонального компьютера. Характеристика основных устройств
Актуальность, цели и задачи настоящего реферата будут определены следующими реалиями и положениями. Появление в 1975 г. в США первого серийного...
-
На сегодняшний день невозможно представить себе жизнь без компьютера и огромного набора преимуществ, которые несет в себе его мощная вычислительная...
-
Введение - Создание таблиц в Microsoft Excel
Электронный таблица еxcel интерфейс Цель данной контрольной работы: получение начальных навыков работы c электронными таблицами Microsoft Excel 2010,...
-
Введение - Исследование алгоритмов
С недавнего времени такая область кибернетики, как создание искусственных систем распознавания образов, стала представлять особый интерес. Потребность в...
-
Введение - Автоматизация теплицы
С каждым годом в тепличных предприятиях все большее внимание уделяется качественному поддержанию микроклимата. Правильно выбранная технология поддержания...
-
Введение - Построение локальной компьютерной сети
Информационные технологии давно вошли в нашу повседневную жизнь. Одним из таких аспектов является наличие персональных компьютеров, что в свою очередь...
-
Введение, Этапы разработки программы - Разработка программы "Будильник"
Внедрение электронно-вычислительных машин, современных средств переработки и передачи информации послужило началом нового процесса, называемым...
-
Введение - Система циклового программного управления
Система циклового программного управления исполнительными механизмами (ИМ) технологического оборудования в машиностроении является одной из типовых,...
-
Введение - Электронный учебник по предмету "Основы алгоритмизации и программирования"
В настоящее время, в условиях активного проникновения информационных технологий в систему образования и накопления образовательных ресурсов в сети...
-
Введение - Модели серверов баз данных
Какая бы сфера человеческой деятельности не была затронута: торговля, медицина, образование, промышленность, сфера развлечений или управления, везде...
Введение - Динамическое хеширование