Решение задач на тему: Массивы - предшественники хеш-структур. Линейное хеширование

Введение

С хешированием мы сталкиваемся едва ли не на каждом шагу: при работе с браузером (список Web-ссылок), текстовым редактором и переводчиком (словарь), языками скриптов (Perl, Python, PHP и др.), компилятором (таблица символов). По словам Брайана Кернигана, это "одно из величайших изобретений информатики". Заглядывая в адресную книгу, энциклопедию, алфавитный указатель, мы даже не задумываемся, что упорядочение по алфавиту является не чем иным, как хешированием.

Хеширование есть разбиение множества ключей (однозначно характеризующих элементы хранения и представленных, как правило, в виде текстовых строк или чисел) на непересекающиеся подмножества (наборы элементов), обладающие определенным свойством. Это свойство описывается функцией хеширования, или хеш-функцией, и называется хеш-адресом. Решение обратной задачи возложено на хеш-структуры (хеш-таблицы): по хеш-адресу они обеспечивают быстрый доступ к нужному элементу. В идеале для задач поиска хеш-адрес должен быть уникальным, чтобы за одно обращение получить доступ к элементу, характеризуемому заданным ключом (идеальная хеш-функция). Однако, на практике идеал приходится заменять компромиссом и исходить из того, что получающиеся наборы с одинаковым хеш-адресом содержат более одного элемента.

Термин "хеширование" (hashing) в печатных работах по программированию появился сравнительно недавно хотя сам механизм был известен и ранее. Глагол "hash" в английском языке означает "рубить, крошить". Для русского языка академиком А.П. Ершовым был предложен достаточно удачный эквивалент - "расстановка", созвучный с родственными понятиями комбинаторики, такими как "подстановка" и "перестановка". Однако он не прижился.

Как отмечает Дональд Кнут , идея хеширования впервые была высказана Г.П. Ланом при создании внутреннего меморандума IBM в январе 1953 г. с предложением использовать для разрешения коллизий хеш-адресов метод цепочек. Примерно в это же время другой сотрудник IBM - Жини Амдал - высказала идею использования открытую линейную адресацию. В открытой печати хеширование впервые было описано Арнольдом Думи (1956), указавшим, что в качестве хеш-адреса удобно использовать остаток от деления на простое число. А. Думи описывал метод цепочек для разрешения коллизий, но не говорил об открытой адресации. Подход к хешированию, отличный от метода цепочек, был предложен А.П. Ершовым (1957), который разработал и описал метод линейной открытой адресации. Среди других исследований можно отметить работу Петерсона (1957). В ней реализовывался класс методов с открытой адресацией при работе с большими файлами. Петерсон определил открытую адресацию в общем случае, проанализировал характеристики равномерного хеширования, глубоко изучил статистику использования линейной адресации на различных задачах. В 1963 г. Вернер Букхольц опубликовал наиболее основательное исследование хеш-функций.

Далее будут массивы - как предшественники хеш - структур, схемы хеширования, область их применения, а также будет проведён сравнительный анализ структур массив и линейное хеширование.

Оглавление

- Введение

- Массивы - предшественники хеш-структур

- Линейное хеширование

- Преимущества и недостатки линейного хеширования Заключение

- Список использованной литературы

Заключение

Хеширование, которое родилось еще в середине прошлого века, активно используется в наши дни везде, где требуется произвести быструю выборку данных. Появились новые методы хеширования, новые модификации алгоритмов, написанных ранее. По мнению Дональда Кнута наиболее важным открытием в области хеширования со времен 70 годов, вероятно, является линейное хеширование Витольда Литвина. Линейное хеширование, которое не имеет ничего общего с классической технологией линейной адресации, позволяет многим хеш-адресам расти и/или выступать в поли вставляемых и удаляемых элементов. Линейное хеширование может также использоваться для огромных баз данных, распределенных между разными узлами в сети.

Разумеется, методы и сферы применения хеширования не ограничиваются тем, что представлено в этой работе. Не вдаваясь в строгий анализ эффективности, были рассмотрены только базовые, наиболее известные методы. Помимо них можно отметить полиномиальное хеширование (М. Ханан и др., 1963), упорядоченное хеширование (О. Амбль, 1973), линейное хеширование (В. Литвин, 1980).

Список литературы

1. Hellerman Н., Digital Computer System Principles. McGraw-Hill, 1967.

2. Ершов А.П., Избранные труды., Новосибирск: "Наука", 1994.

3. Кнут Д., Искусство программирования, т.3. М.: Вильямс, 2000.

4. Peterson W.W., Addressing for Random-Access Storage // IBM Journal оf Research and Development, 1957. V.1, N2. Р.130-146.

5. Morris R., Scatter Storage Techniques // Communications оf the ACM, 1968. V.11, N1. Р.38-44.

7. #"#">#"#">#"#">#"#">#"#">#"#">http://www.сs.uic.edu/~i201/HashingAns.pdf

16. Т. Gunji, Е. Goto, J. Information Proc., 3 (1980), 1-12

17. Чмора А., Современная прикладная криптография., М.: Гелиос АРВ, 2001.

19. Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы: построение и анализ, М.: МЦНМО, 2001

20. Вирт Н., Алгоритмы + структуры данных = программы, М.: Мир, 1985.

21. Керниган Б., Пайк Р., Практика программирования, СПб.: Невский диалект, 2001.

22. Шень А, Программирование: теоремы и задачи. М.: МЦНМО, 1995.