AOP_Tom3 (1021738), страница 158
Текст из файла (страница 158)
Не)!егшап, П!я!га! Сошрнгег ЯзяГеш Ргшс!р!ек (1чеш Ъог)с: МсСгаш-Н111, 1967), 152. При работе над этим разделом автор изучил около 60 относящихся к хешированию документов, однако более раннее упоминание данного термина встретилось лишь один раз в неопубликованном меморандуме В. В. Петерсона, датированном 1967 годом. Получилось так, что, хотя глагол нхешироватьв (1о ЬазЬ) стал стандартным термином в средине 60-х годов, никто не решался использовать в печати столь недостойное слово до 1967 года!* е Становление нового термина — процесс непростой. и, пожалуй, уместно вспомнитгь что еще совсем недавно вместо слона "компьютер" в нашей литературе использовалось в лучшем случае ЗВМ, вместо "винчестер" -- НЖЯД (дзн тех, кто не поьгнит этот термин, напомним, что он означает "накопитель на жестком магнитном диске" ), вместо "дискета" — ГМД (гибкий магнитный диск)...
†- Йрпхс нерее. Последние разработки. Со времени первой публикации этой главы в 1972 году в области теории и практики хеширования было сделано немало новых достижений, хотя основные идеи остались полезными для использования в обычных приложениях. Например, в книг 1. Б. Уйсег апь! 1ь!?.-С. СЬеп, Оев!яп апь! Апа!ув!в оГ Сов!евсее! Няя!ь!пк (!чеьу Уог!ь: Ох(огь! Бпнл Ргевв, 1987) рассмотрены и проанализированы различные поучительные варианты алгоритма С.
С практической точки зрения наиболее важным открытием в области технологии хеширования со времен 70-х годов, вероятно, является метод Витольда Литвина (%!го!ь! Ь!!ьу!и), называемый линейным хешированием [Ргос. 665 1пгегььаг!ьопа! СопГ. оп 1егу Ьагяе 17аваЬавев (1980), 212.-223[, Линейное хецьирование, которое не имеет ничего общего с классической технологией линейного исследования, позволяет многим хсш-адресам расти и?илье выступать в роли вставляемых и удаляельььх элементов. Превосходное обсуждение линейного хеширования, включая сравнение с другими методами, можно найти в работах Рььг-А!ье Ьагвоп, САСМ 31 (1988), 446- 457, %. О.
Сг!вас!6 апй С. М. Тоипяепь), Бойжаге Ргасбсе 4е Ехр, 23 (1993), 351 — 367 (в последней работе рассмотрены усовершенствования метода для одновременного использования множества больших и/или маленьких таблиц). Линейное хеширование может также использоваться для огромных баз данных, распределенных между многими узлами в сети [см, 1.!!ьу!п, Хеппас, апь! БсЬпе!ь!ег, АСМ Тгапв. ОагаЬаве Буль 21 (1996), 480-525[. Альшрнативная схема, называемая расширяемым хеширпааььием (ехгепь!!5!е Ьавй!гьд) и имеющая то свойство, что для выборки любой записи требуется не более двух ссылок на внешние страницы, была предложена в то же время в работе В.. Раб!и, 3, Х!еуегбе)ц Ь?.
Р!ррепбег, апь) Н. В. Бггопб [АСМ Тгапв. ВагаЬаве Бувг,. 4 (1979), 315 — 344!. Как линейное, так и расширяемое хеширования предпочтительнее использования В-деревьев (см. раздел 6.2.4) в том случае, когда порядок ключей не имеет значения. В области теоретической были разработаны более сложные методы, которые могут гарантировать максимальное время доступа 0(1) со средним временем на вставку и удаление 0(1) независимо от ключа.
Более того, общее количество пространства, требуемого для работы алгоритма, ограничено некоторой константой, умноженной на количество элементов, имеющихся в настоящий момент в наличии, плюс некоторая другая константа*, Этот результат, основанный на идеях Фредмана (Ргейпап), Комлеса (Когп!бв) и Семереди (Бхешегбс(!) [,1АСМ 31 (1984), 538-544[, получен в работе В!ест(е1Ъ!пкег, Квг1ш, МеЬ!Ьогп, Меуег ац1 с1ег Не!ь!е, ВоЬпегс, апь1 Тат)ап [Б1СОМР 23 (1994), 738 — 761), УПРАЖНЕНИЯ 1.
[Н0) Насколько малб и насколько велико может быть содержимое г11 по достижении команды 9Н, приведенной в табл. 1, в предположении, чтп каждый нз байтов 1, 2, 3 ключа К содержат символы с кодами, меньшими 30? 2. [вО) Найдите довольно известное английское гчпво, которого пвт в табл. 1 и которое может быть добавлено в иее без изменения программы. * Иначе говори, пе мудрствуя, мажип записать, что требуемая дли хранения память составляет Сь Ьх м Сз.
— Прим. перев. 3. [ЯУ] Объясните, почему программу, приведенную в табл. 1, нельзя заменить более простой программой, которая начинается с пити следующих ниже команд, ни при какой константе а, с учетом того, что разные ключи не могут иметь одинаковые хеш-адреса? 101 К(1:1) или Ы13 К(1".1) Х02 К(2:2) или 1026 К(2:2) 1301 а,2 Ы]2 К(3:3) 122 йр 4. [Муо] Сколько гостей следует пригласить на вечеринку, чтобы вероятность появления трех человек с одним и тем же днем рождения была не менее -'? б. [13] Мистер Ламер писал компилятор ГОКТКА)з с использованием десятячного компьютера И1Х, и ему понадобилась таблица символов для хранения имен переменных в программе во время компиляции. Эти имона имеют ограниченную длину - . не более десяти символов. Ламер рва~ил использовать хеш-таблицу с М = 100, а для скорости работы использовал хеш-функцию Н(Н') = крайний левый байт К.
Насколько хороша его идея? 6. [15] Насколько разумно заменить две первые команды нз (3) кома~дами ЫА К; ККТХ О? 7. [ПМУО] (Полиномиальное хеширование.) Назначение этого упражнения — рассмотреть построение полиномов Р(х), как в (10), которые преобразуют п-битовые ключи в т-битовые адреса так, что различные ключи, отличающиеся не более чем 1 бит, будут иметь различные хеш-адреса. По заданным значениям и и 1 < и, н по данному целому к, такому, что п делит 2" — 1, построим полинам степени т, где т является функцией п, 1 и к.
(Обычно при необходимости и увеличивается, так что 1' может быть выбрано достаточно малым.) Пу.сть 5 — минимальное множество целых чисел, таких, что (1,2,...,1) С 5 н (21) пзоб и й 5 для всех 1' й 5. Например, нри и = 13, х = 4 и г = б имеем 5 = (1, 2, 3, 4, б, 6,8,10,12тй).
Теперь определим полинам Р(х) = ][ з(х — а'), где о — элемент порядка и конечного поля Сг(2 ), а коэффициенты Р(х) вычисляются в этом поле. Степень т полинома Р(х) равна числу элементов в 5. Поскольку, если пг — корень Р(х), то и оз)— корень Р(х), отсюда следует, что коэффициенты р, полинома Р(х) удовлетворяют условию рз = р,, т. е. они представляют собой 0 или 1. Докажите, что если Н(х) = г„~х" ' + + г~х+ ге представляет собой некоторый ненулевой многочлен ио модулю 2 с не более чем 1 ненулевыми коэффициентами, то 1?(х) не кратен Р(х) по модулю 2. (Отсюда следует, что соответствующая хеш-функция ведет себя, как н было обещаноб) 8.
[МУ4] (Теорема а трех дланах.) Пусть д — иррациональное чигло между 0 и 1, представление которого в виде регулярной непрерывной дроби в обозначениях раздела 4.3.3 есть 9 = //ацамаз,...// Пусть до = О, ре = 1; В = 1, р~ = О и йь+~ = аьйь + йь-м рь.е~ = аьрь+рь-~ при?с > 1. Пусть [х) означает хшос(1 = х — [х), а (х)+ — х— [х] + 1. Перенумеруем отрезки, получающиеся в результате последовательной вставки точек (д), (20), (36),... в интервал [О ..
Ц, в порядке их появления, причем первому отрезку присваивается номер О. Докажите справедливость следующих утверждений. Интервал номер з длиной [10), где 1 = где + дь н 0 < г < аы й четно и 0 < л < дю имеет левую границу (еа) и правую границу ((в + 1)9)~. Интервал номер з длиной 1 — (го), где 1 = * Взгляните с этой точки зрения на аоливомы х~е+х~э+хе+1 и хзз+хее . 'хзз+хш+х~е+х~з+ х +хш+х +к~+с~ к~+я~+к х1, определяющие СС1ТТ СКС16 и СКС 32 соответственно, в рассмотрите возможность использования СКС в качестве хеш-фулкцин.
— Прим. верее. туз + уз-и О < с < оь, Ь нечетно и О < з < ую имеет левую границу ((з+ 1) В) и правую границу (з0) '. Любое положительное целое число и может быть единственшям образом представлено в ниде и = туз + уь ~ ж з при Ь > 1, 1 < г < аз и О < з < уы В этих обозначениях перед вставкой точки (иВ) имеется и интервалов: первые з интервалов (с номерами О,, з — 1) длиной (( — 1) (туз + уь ~)0); первые и — уз интервалов (с номерами О, ..., и — уь — 1) длиной (( — 1) ~ уьВ): последние ус -ь ннтервшюв (с номерами в,, уь — 1) длиной ((-1) ((г — Цув+уз-~)0)+.
Операция вставки (иВ) приводит к удалению интервала номер з третьего типа и его преобразованию в интервал номер з первого типа и номер и — уь второго типа. 9. (М80) При последовательной вставке точек (В), (20), ... в отрезок (О .1] теорема Б утверждает, что каждая новая точка всегда разбивает один из наибольших имеющихся интервалов. Егли интервал (а. с) разбит такам образом на две части, (а..Ь) и (Ь..с), назовем разбиение плохим, если одна из частей более чем в два раза больше другой, т, е, если Ь вЂ” а > 2(с — Ь) или с — Ь > 2(Ь вЂ” а). Докажите, что при некотором и точка (и0) дает плохое разбиение, за исключением с.тучаев В шос) 1 = 4 ' и 0 шос) 1 = сэ т, при которых никогда не бывает плохих разбиений.
10. (М88) (Р. Л. Грэхем (В. 1.. Сгайага).) Докажите, что если В.аы..,,аг — действительные числа, причем а~ = О, если и,,..., иг — голожительные целые числа и если точхи (и0+ аг) вставлены в интервал (О., Ц при О < и < и, и 1 < 0 < д, то ис + + иг получающихся интервалов (возможно, пустых) имеют ие более Зс( различных длин.
11. (16) Как правило, поиск чаще завершаатся успешно, чем неудачно. Исходя из этого, насколько разумно заманить строки 12-13 программы С строками 10 — 112 ь 12. (81] Покажите. что программа С люжет быть переписана так, что во внутреннем цикле останется только один условный переход. Сравните время работы модифицированной и исходной программ. ь 13. (24) (Сокращенные ключи.) Пусть й(К) представляет собой хеш-функцню, а у(К)— функцию от К.
такую, что К можно определить по данным А(К) и у(К). Например, в ~ эучае хешнроьания путем деления лсожно положить й(К) = К шос) М, а у(К) = (К(М); при мультсшликативном же хешировании в качестве й(К) можно взять старшие биты (тПс/ш) шос) 1, а в качеств" у(К) остальные биты. Покажите, что при использовании цепочек без списков перекрытий достаточно хранить значение у(К) вместо К для каждой записи. (Это позволяет сэкономить пространство, необходимое для полей ссылок.) Измените алгоритм С, чтобы оп позволял работать с такими сокращенными ключами и можно было избежать использования списков верехрытий и вспомогательной памяти для хранения переполняющих записей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
