Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 47
Текст из файла (страница 47)
1пЬп) при написании внутреннего меморандума 1ВМ в январе 1953 года с предложением использовать метод цепочек, В этом меморандуме фактически впервые преддагалось использовать связанные линейные списки при решении практических задач. Он указал, что для внешнего поиска желательно использовать блоки, содержащие более одного элемента. Вскоре после этого Э. Д. Лин (А, Р. Е!и) развил теорию Лана и предложил технологию для обработки переполнений с помощью "вырожденных адресов"; например, при переполнении первичного блока 2748 переполняющих записей попадают во вторичный блок 274; переполнения из этого блока попадают в третичный блок 27 и т. д. (в предположении, что имеется 10000 первичных блоков, 1000 вторичных, 100 третичных и т.
д.). Хеш-функция., предложенная Ланом, по своей природе была буквенно-цифровой, например комбинировались соседние пары цифр ключа при помощи суммирования по модулю 10, так что 31415926 упаковывалось до 4 548. Примерно в то же время идея хеширования независимо возникла и у другой группы сотрудников 1ВМ: Жини М. Амдал (Севе М.
Апи1эЫ), Элейн М. Воэм (Е!а!пе М. ВоеЬше), Н. Рочестера (Н. НосЬеэгег) и Артура Л. Сэмюэла (АгсЬпг 1. лапше!). Оии создавали программу на ассемблере для 1ВМ 701. Для разрешения проблемы, связанной с коллизиями, Жини Амдал предложила использовать открытую адресацию с линейным исследованием. В открытой печати хеширование впервые было описано Арнольдом И. Думи (Агпо!6 1. Вншеу) [Сошригегэ апд Аигошабоп 5, 12 (ОегешЬег, 1956), 6-91, Он был первым, кто упомянул идею деления на простое число и использование остатка в качестве хеш-адреса. В интересной статье Думи упоминает цепочки, на открытой адресации в ней нет.
Советский математик А. П. Ершов в 1957 году независимо разработал метод линейной открытой адресации (ДАН СССР 118 (1958), 427-430]; он опубликовал эмпирические результаты по количеству проб, справедливо предположив, что среднее количество проб для успешного поиска < 2 при Х/М < 2/3. Классическая статья тт'. %'. Решгвоп, 1ВМ Х Неэеагсй Хс Веге!ортепг 1 (1957), 130-146, была первой важной работой, посвященной поиску в больших файлах. Петерсон определил открытую адресацию в общем случае, проанализировал производительность равномерного исследования и привел многочисленные эмпирические статистические данные о поведении линейной открытой адресации с блоками различных размеров, указав на ухудшение производительности при удалении элементов. Другой всесторонний обзор предмета был опубликован шестью годами позже Вернером Букхольцем (ьтегпег Вцсййо!и) [!ВМ Яуэ!ешз Х 2 (1963), 86-.1П). В его рабате особый упор сделан на исследовании хеш-функций.
Корректный анализ алгоритма 1, был впервые опубликован А. Г. Конхеймом (А. О. КопЬепп) и Б. Вейссом (В. %е!ээ) (В!АМ Х Арр!. Ма(Ь. 14 (1966), 1266-1274), а также В. Поддерюгиным (Ъ!г(ээепзсЬаХГ!!сйе Хейлсйп!с с(ег Тесйшэсйеп (7л!уегэ(тай Огеее7еп 17 (1968), 1087-1089). К этому времени линейное исследование было единственным тином схемы открытой адресации, описанной в литературе, хотя несколькими исследователями независимо была разработана другая схема, основанная на неоднократном случайном применении независимых хеш-функций (см. упр.
48). В течение нескольких последующих лет хеширование стало широко использоваться, хотя не было опубликовано никаких новых работ. Затеи Роберт Моррис (Набег! Могпэ) написал обзор по хешированию (САСМ 11 (1968), 38-44), оказавший впоследствии большое влияние на работы в этом направлении. В обзоре вперные появилась идея случайного исследования с вторичной кластеризацией.
Статья Морриса оказалась наброском дальнейших исгзедований в этой области, которые завершились созданием алгоритма П и его усовершенствованных версий. Интересно отметить, что слово "хеширование" (Ьвпйпй), по-видимому, ии разу не появилось в печати (в его современном значении) до 60-х годов, хотя к тому времени оно прочно заняло место в компьютерном жаргоне во всем мире. Впервые это слово, вероятно, было использовано в книге Н. НеИеппап, В!8!га! Сашригег Яуагеш Рппар!еэ (Кеи Уаг)г: МсСгаи-Н!!1, 1967), 152.
При работе над этим разделом автор изучил около 60 относящихся к хешированию документов, однако более раннее упоминание данного термина встретилось лишь адин раз в неопубликованном меморандуме В. В. Петерсона, датированном 1967 годом. Получилось так, что, хотя глагол Яхешироватьв (со ЬааЬ) стал стандартным термином в средине 60-х годов, никто не решался использовать в печати столь недостойное слово до 1967 года.'* ' Становление нового термина — процесс непростой, и, пожалуй, уместно вспомнить, что еше совсем недавно вместо слова компьютер'" в нашей литературе использовалось в лучшем случае ЭВМ, вместо "внмчестер" — НЖМД (для тек.
кто не помнит зтот термин, напомним, что он означает "накопитель на жестком магнитном диске" ), вместо "дискета" — ГМД (гибкий магнитный диск)... — Прим. перев. Последние разработки. Са времени первой публикации этой главы в 1972 году в области теории и практики хеширования было сделано немало новых достижений, хотя основные идеи остались полезными для использования в обычных приложениях. Например, в книге д.
8. У111ег апб 'гг'.-С. СЬев, Пемба влд Апа)ув1в о1 Сап)евсее( НввЫпб (Хе~ч Уогйп Ох(огд Вщг. Ргеде, 1987) рассмотрены и проанализированы различные поучительные варианты алгоритма С. С практической точки зрения наиболее важным открытием в области технологии хеширования са времен 70-х годов, вероятно, является метод Витольда Литвина (%'11ой 1дгибп), называемый линейным хешированием [Ргос. 6ЬЬ 1пгегпаНопв1 Сапб ап Ъегу 1,агбе ОясаЬажв (1980), 212-223).
Линейное хеширование, которое не имеет ничего общего с классической технологией линейного исследования, позволяет многим хеш-адресам расти и/или выступать в роли вставляемых и удаляемых элементов. Превосходное обсуждение линейного хеширования, включая сравнение с другими методами, можно найти в работах Рег-АЬе Ьагеоп, САСМ 31 (1988), 446- 457, %.
С. СПяшоМ апб С. М. Тачгпееаб, Баугшаге РгасВсе 1г Ехр. 23 (1993), 351-367 (в последней работе рассмотрены усоверпденствования метода для одновременного использования множества больших и/или маленьких таблиц). Линейное хеширование может также использоваться для огромных баз данных, распределенных между многими узлами в сети [см.
Ь1гк1п, Меппа1, апб 8сЬпеи1ег, АСМ Тгапв, )уагаЬаяе Буек 21 (1996), 480-525). Альтернативная схема, называемая росигирлемым хешированием (ея1епй51е Ьад51пу) и имеющая то свойство, что для выборки любой записи требуется не более двух ссылок на внешние страницы, была предложена в то же время в работе Н. Ра81п, З..ч!ечегбе1ц Х, Р1ррепбег, апб Н. Н. 81гопб (АСМ Тгапв.
ЙагаЬаде Бува 4 (1979), 315-344). Как линейное, так и расширяемое хеширования предпочтительнее использования В-деревьев (см, раздел 6.2.4) в том глучае, когда порядок ключей не имеет значения. В области теоретической были разработаны более сложные методы, которые могут гарантировать максимальное время доступа 0(1) са средним временем на вставку и удаление 0(1) независимо от ключа.
Более того, общее количество пространства, требуемого для работы алгоритма, ограничено некоторой константой, умноженной на количество элементов, имекицихся в настоящий момент в наличии, плюс некоторая другая константае. Этот результат, основанный на идеях Фредмана (Ргейпап), Комлеса (Когп!бв) и Семереди (Бяешег611) [1АСМ 31 (1984), 538-544], получен в работе 01есв(е!Ь~пйег, Квг!ш, МеЫЬогп, Меуег ап1 с(ег НеМе, ВоЬпегг, апс$ Тат)ап [81СОМР 23 (1994), 738-761). УПРАЖНЕНИЯ 1, [20) Несколько малб и насколько велико может быть содержимое г11 во достижении команды Эц, приведенной я табл.
1, в предположении, что каждый из байтов 1, 2, 3 ключа К содержат символы с кодами, меньшими 307 2. [20) Найдите довольно известное английское слово, которого нег в шбл. 1 и которое может быть добавлено в нее без изменения программы. Я Ияече говоря, яе мудрствуя, можно ядяясдгь, что требуемая ляя хреяемяя память составляет С~ Лч Е Сд. — Прим. иерее. 3. [ЯЯ] Обьясните, почему программу, приведенную в табл, 1, нельзя заменить более простой программой, которая начинается с пяти следующих ниже команд, ни при какой константе а, с учетом того, что разные ключи не могут иметь одинаковые хеш-адреса? 101 К(1:1) нли 1013 К(1:1) Ы2 К(2:2) илн 1023 К(2:2) 1301 а,2 Ы2 К(3:3) 122 9У 4. (МВВ) Сколько гостей следует пригласить на вечеринку, чтобы вероятность появления шрех человек с одним н.тем же днем рождения была не менее -'? 5, (15) Мистер Ламер писал компилятор КОКТКЛХ с использованием десятичного компьютера И1Х, н ему понадобилась таблица символов для хранения имен переменных в программе во время компиляции.
Эти имена имеют ограниченную длину — не более десяти символов. Ламер решил использовать хеш-табдицу с М = 100, а для скорости работы использовал хеш-функцию Ь(/»') = крайний левый байи» К. Насколько хороша его идея? 6. (15) Насколько разумно заменить две первые команды из (3) командами (3)А К; ЕИ?К О? 7. (ПМУВ) (Полиномиальнос хеширование.) Назначение этого упражнения — рассмотреть построение полиномоэ Р(х), как в (10), которые преобразуют и-битовые ключи в т-битовые адреса так, что различные ключи, отличахлциеся не более чем 1 бит, будут иметь различные хеш-адреса. По заданным значениям я и 1 < п, и по данному целому А, такому, что и делит 2" — 1, построим полинам степени т, где эл является функцией п, 1 н А.
(Обычно при необходимости и увеличивается, так что й может быть выбрано достаточно малым.) Пусть  — минимальное множество целых чисел, таких, что (1,2,...,1) С Я и (21) шос( п Е Я для всех / б 5. Например, при н = 15, А = 4 и 1 = б имеем Я = (1, 2, 34 5, 6,3,10,12,9). Теперь определим полинам Р(х) = П э(х — а)), где ц — элемент порядка и конечного поля Ог(2"), а коэффициенты Р(х) вычисляются в этом поле. Степень и» полннома Р(х) равна числу элементов в В. Поскотину, если ау — корень Р(х), то и а »в корень Р(х), отсюда следует, что коэффициенты рэ полинома Р(х) удовлетворяют условию рэ = р,, т.
е. они представляют собой 0 или 1. Докажите, что если Л(х) = г„-»х» ' + ° + г»х + гс представляет собой некоторый ненулевой многочлен по модулю 2 с не более чем 1 ненулевыми козффвшяентами, то В(х) не кратен Р(х) по модулю 2. (Отсюда следует, что соответствующая хеш-функция ведет себя, как и было обещано».) 8. (МУ4) (Теорема о трке длинах.) Пусть  — иррациональное число мекслу 0 и 1, представление которого а виде регулярной непрерывной дроби в обозначениях раздела 4.5.3 есть В = //ам аз,аз,...//.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
