До цих пір ми розглядали методи пошуку, засновані на порівнянні цього аргументу K з наявними в таблиці ключами або на використанні його цифр для управління процесом розгалуження. Але є і третій шлях: не нишпорити навкруги, а здійснити над K деякий арифметичне обчислення і отримати функцію f (K), що вказує адресу в таблиці, де зберігається K і асоційована з ним інформація.
На жаль, знаходити подібні функції f (K) досить складно.
Функції, що дають неповторним значення, несподівано рідкісні навіть у разі досить великий таблиці. Наприклад, знаменитий парадокс днів народження стверджує, що, якщо в кімнаті присутні не менш як 23 чоловік, є хороший шанс на те, що у двох з них співпаде день народження! Іншими словами, якщо ми вибираємо випадкову функцію, що відображає 23 ключа в 365-елементну таблицю, то з імовірністю 0.4927 (менше половини) всі ключі потраплять у різні місця.
Зрозуміло, такий метод має істотний недолік, бо вміст таблиці має бути відомо заздалегідь; додавання хоча б одного ключа може все зіпсувати, і нам доведеться починати фактично на порожньому місці.
Можна отримати набагато більш гнучкий метод, якщо відкинути ідею
однозначності, допускаючи збігу значень f (K) для різних
аргументів, і використовувати особливий метод вирішення невизначеності після обчислення f (K).
Наші розгляду призводять до широко відомого класу методів, зазвичай званих хешування або розсіяною пам'яттю. Англійська
дієслово "to hash" має сенс нарізати, розкришити що-небудь або зробити з цього місиво; ідея хешування полягає в тому, щоб взяти деякі характеристики ключа і використовувати отриману часткову інформацію в якості основи пошуку. Ми обчислюємо хеш-функцію h (K) і беремо це значення як адресу початку пошуку.
Парадокс днів народження служить для нас пересторогою, що, ймовірно, знайдуться різні ключі Ki? Kj, для яких h (Ki) = h (Kj). Подібна подія називається колізією; для вирішення колізій були розроблені цікаві підходи. Щоб використовувати розсіяну таблицю, програміст повинен прийняти дві майже незалежних рішення: він повинен вибрати хеш-функцію h (K) і метод вирішення колізій. Ці два аспекти задачі пошуку ми і розглянемо по черзі.
Хеш-функції. Для визначеності будемо вважати, що хеш-функція h (K) має не більше M різних значень і, що ці значення задовольняють умові
0? h (K)
для всіх ключів K. У реальному фото багато майже однакових ключів,
тому бажано вибрати хеш-функцію, що розсіюють їх по таблиці. Це важливо для зменшення числа колізій.
Теоретично так неможливо визначити хеш-функцію, щоб вона створювала випадкові дані з невипадкових реальних файлів. Але на практиці неважко зробити досить хорошу імітацію випадковості, використовуючи прості арифметичні дії. Насправді ми можемо вступити навіть краще, виявляючи невипадкові властивості реальних даних і будуючи на їх основі хеш-функцію, що дає менше колізій; ніж коли є істинно випадкові ключі.
Розглянемо, наприклад, випадок десятизначний ключів на десятковому комп'ютері. Сам собою напрошується наступний спосіб вибору хеш-функції: покласти M рівним, скажімо, 1000, а в якості h (K) взяти три цифри, обрані приблизно з середини 20-значного твори K * K. Здавалося б, це повинно давати досить рівномірний розподіл значень між 000 і 999 з низькою ймовірністю колізій. Справді, експерименти з реальними даними показали, що такий метод "середини квадрата" непоганий за умови, що ключі не містять багато лівих чи правих нулів підряд.
З'ясувалося, однак, що існують більш надійні і прості способи способи завдання хеш-функцій.
Численні перевірки реальних файлів виявили дуже хорошу роботу двох основних типів хеш-функцій. Один з них заснований на розподілі, а інший на множенні.
Метод поділу особливо простий: використовується залишок від ділення на M
h (K) = K mod M. (2)
У цьому випадку, очевидно, деякі значення M багато краще другіх.Напрімер, якщо M - парне число, то значення h (K) буде парних при парній K і непарних інакше; часто це призводить до значних зсувів даних. Зовсім погано брати M рівною мірою основи системи числення ЕОМ, тому що тоді h (K) дає нам праві значущі цифри K (K mod M не залежить від інших цифр). Аналогічно, M не повинно бути кратно 3, бо літерні ключі, що відрізняються один від одного лише порядком букв, могли б дати значення функції, різниця між якими кратна 3. (Причина криється в тому, що 10n mod 3 = 4n mod 3 = 1.) Взагалі ми хотіли б уникнути значень M, що поділяють rk? a, де k і a-невеликі числа, а r-"основу системи числення" для безлічі використовуваних літер
(звичайно r = 64, 256 і 100), так як залишок від ділення на такі
значення M зазвичай виявляються простий суперпозицією цифр ключа.
Наші розгляду підказують, що найкраще взяти в якості M таке просте число, щоб rk? ? a (mod M) при
невеликих k і a. Практично у всіх випадках, цей вибір виявляється цілком задовільним. M = 1009 => h (K) обчислюється наступним чином
rX? K
rA? 0 (3)
rA? K mod 1009
Мультиплікативну схему хешування також легко реалізувати, але дещо важче описати, тому що треба уявити, що ми працюємо з дробами, а не з цілими числами. Нехай w є розмір машинного слова; ціле число A можна розглядати як дріб A/w, якщо подумки поставити десяткову (або двійкову) точку ліворуч від машинного слова, в якому записано A. Метод полягає в тому, щоб вибрати A взаємно простим з w і покласти
h (K) = [M (((A/w) K) mod 1)]. (4)
У двійковій системі M зазвичай беруть рівним ступеня двійки, так що h (K) складається з старших бітів правою значущої половини твори AK. У двійковому вигляді при M = 2m мультиплікативна хеш-функція обчислюється так:
rA? K.
rAX? AK. (5)
rAX? AK mod w.
Зрушення rAX на m бітів вліво.
Результат виходить в регістрі A.
Одна з привабливих рис мультиплікативної схеми полягає в тому, що в (5) не відбувається втрати інформації, ми могли б знову знайти K, знаючи лише вміст rAX після виконання інструкцій (5). Справа в тому, що A взаємно просто з w, і за допомогою алгоритму Евкліда можна знайти Константа A ': AA' mod w = 1; звідси випливає, що K = (A '(AK mod w)) mod w. Іншими словами,
K1? K2 тягне f (K1)? f (K2). (6)
Звичайно, f (K) приймає значення в діапазоні від 0 до w-1 і не є скільки-небудь підходящої хеш-функцією, але вона може бути дуже корисною як розсіює функції, а саме функції, що задовольняє (6) і зазвичай приводить до рандомізації ключів.
Гарна хеш-функція повинна задовольняти двом вимогам:
a) її обчислення повинно бути дуже швидким;
b) вона повинна мінімізувати кількість колізій.
Властивість (a) почасти залежить від особливостей машини, а властивість (b) - від характеру даних. Якби ключі були дійсно випадковими, можна було б просто виділити кілька бітів і використовувати їх для хеш-функції, але на практиці, щоб задовольнити (b), майже завжди потрібна функція, що залежить від всіх бітів.
До цих пір ми розглядали Хешування ключів, що складаються з одного слова. З ключами, що складаються з декількох слів або мають змінну довжину, можна працювати як з представленими з багаторазової точністю числами і застосувати до них розглянуті методи. Проте зазвичай виявляється достатньої більш швидка процедура, коли окремі слова спочатку комбінуються в одне, а потім здійснюється єдине множення або ділення. Для комбінування можна використовувати додавання по модулі w або операцію "виключає або" (на двійкових ЕОМ). Перевагою обох операцій є їх оборотність, тобто їх результат залежить від усіх бітів аргументів, причому "виключає або" іноді краще, тому що не може призвести до арифметичного переповнення. Зауважимо, що обидві операції комутативність, тому ключі (X, Y) і (Y, X) будуть "кинуті" за однією адресою. Щоб уникнути цього, Г.Д. Гринішин запропонував попередньо робити циклічний зсув.
З інших випробуваних методів хешування, мабуть, найбільш цікавим є спосіб, заснований на алгебраїчної теорії кодування. Ідея аналогічна методу поділу, тільки замість поділу на ціле число використовується розподіл на многочлен за модулем 2. Для пропонованого методу M повинно бути ступенем 2: M = 2m; крім того, використовується многочлен m-го ступеня
P (x) = xm + pm-1 xm-1 + ... + p0.
Двійковий ключ K = (kn-1 ... k1 k0) 2 можна розглядати як многочлен K (x) = kn-1 xn-1 + ... + k1x + k0, і обчислити залишок
K (x) mod P (x) = hm-1 xm-1 + ... + k1 x + k0,
використовуючи поліноміальних арифметику за модулем 2: h (K) = (hm-1 ... h1 h0) 2. При правильному виборі P (x) така хеш-функція дозволяє уникнути колізій, між майже рівними ключами.
Дозвіл колізій методом ланцюжків. Ми вже говорили,
що деякі адреси можуть породжуватися декількома ключами. Мабуть, найбільш очевидний спосіб вирішення проблеми полягає в тому, щоб підтримувати M пов'язаних списків, по одному на кожен можливий хеш-адреса. Усі записи повинні містити поля LINK; крім того, потрібно мати M головних вузлів списків HEAD [i], де i змінюється від 1 до M. Після хешування
HEAD [1]: [__] [TO] [] [FIRE] [? ]
HEAD [2]: [__] [SYV] [? ]
HEAD [3]: [__] [EN] [? ]
HEAD [4]: [__] [TRE] [? ]
HEAD [5]: [__] [FEM] [? ]
HEAD [6]: [_?_]
HEAD [7]: [_?_]
HEAD [8]: [_? ]
HEAD [9]: [__] [SEKS] [? ]
Рис. Окремі ланцюжка.
ключа ми просто виконуємо послідовний пошук в списку з
номером h (K) +1.
Малюнок ілюструє цей простий метод ланцюжків при M = 9 для
послідовності семи ключів
K = | EN |, | TO |, | TRE |, | FIRE |, | FEM |, | SEKS |, | SYV |
(так називаються числа від 1 до 7 по-норвезькі), що мають відповідні хеш-коди
h (K) +1 = 3, 1, 4, 1, 5, 9, 2.
Перший список містить два елементи, три списки порожні.
Метод ланцюжків є дуже швидким, оскільки списки короткі. Якщо в одній кімнаті зібрати 365 осіб, то знайдеться багато пар, що мають один і той же день народження, а ось цей день народження в середньому має лише одна людина! Взагалі, якщо є N ключів і M списків, середній розмір списку дорівнює N/M; таким чином, Хешування зменшує кількість роботи, необхідний для послідовний пошук, приблизно в M раз.
З метою економії часу бажані великі M, але в цьому випадку багато посилання будуть порожніми, так що більша частина простору, що відводиться під M головних вузлів, витратиться даремно. Для невеликих за розміром записів напрошується інший підхід: можна накласти простір для записів на простір для головних вузлів, відводячи в таблиці місце під M записів і M посилань, а не за N записів і M + N посилань.
Іноді можна зробити один прохід за даними і з'ясувати, які головні вузли будуть використовуватися, вставляючи на наступному проході "переповнюють" записи у вільні щілини. Часто, однак, це небажано або неможливо, нам хотілося б мати метод, при якому кожен запис обробляється лише один раз, при першому надходженні в систему. Наступний алгоритм, що належить Ф. Уільямса, є загальноприйнятим способом вирішення цього завдання.
alg C. (Пошук з вставкою по розсіяною таблиці з ланцюжками.) Пропонований
алгоритм дозволяє відшукати в таблиці з M елементів даний ключ K.
Якщо K немає в таблиці і вона не повна, K вставляється в неї.
Елементи таблиці позначаються через TABLE [i], 0? I? M, і можуть
бути двох різних типів: вільний і зайнятий. Зайнятий вузол
містить ключове поле KEY [i], поле посилання LINK [i] і, можливо,
інші поля.
Алгоритм використовує хеш-функцію h (K). Для полегшення пошуку вільного простору використовується допоміжна мінлива R; якщо таблиця порожня, R = M +1; в міру проведення вставок буде залишатися в силі твердження, що вузли TABLE | [j] зайняті для всіх j в діапазоні R? J? M. < br />
Умовимося, що вузол TABLE [0] завжди буде вільний.
C1. [Хешування.] Встановити i? H (K) +1. (Тепер 1? I? M.)
C2. [Список?] Якщо вузол TABLE [i] вільний, то перейти на C6.
(В іншому разі цей вузол зайнятий, і ми підемо на наявний тут
список зайнятих вузлів).
C3. [Рейтинг.] Якщо K = KEY [i], пошук завершено вдало.
C4. [Перехід до наступного.] Якщо LINK [i]? 0, встановити i? LINK [i] і повернутися на
C3.
C5. [Знайти вільний вузол.] (Пошук був невдалим, і ми хочемо знайти в
таблиці вільне місце.) Зменшувати R до тих пір, поки не буде отримано
таке значення, що вузол TABLE [R] вільний. Якщо R = 0, алгоритм
закінчується по переповнення (вільних вузлів більше немає); в іншому
випадку встановити LINK [i]? R, i? R.
C6. [Вставити новий ключ.] Позначити TABLE [i] як зайнятий вузол
З KEY [i]? K і LINK [i]? 0.
В алгоритмі допускається зрощення декількох списків, так що після вставки в таблицю запису переміщати не потрібно.
Ні
Так
K = KEY [i] R = 0
УДАЧА Переповнення
Рис. Пошук з вставкою по розсіяною таблиці з ланцюжками.
TABLE [1]: [TO] []
TABLE [2]: [SYV] [? ]
TABLE [3]: [EN] [? ]
TABLE [4]: [TRE] [? ]
TABLE [5]: [FEM] [? ]
TABLE [6]: [_? _]
TABLE [7]: [_? _]
TABLE [8]: [SEKS] [? ]
TABLE [9]: [FIRE] []
рис. Зрослися списки.
На перший погляд крок C5 може здатися неефективним, тому що в ньому пошук вільної позиції проводиться послідовно. Але в
дійсності в процесі заповнення таблиці сумарне число проб за крок C5 не перевищує кількості елементів у таблиці; отже, в середньому на кожну вставку витрачається не більше однієї такої проби!
Дозвіл колізій "відкритої адресацією". Інший спосіб вирішення проблеми колізій полягає в тому, щоб повністю відмовитися від посилань і просто переглядати один за одним різні елементи таблиці, поки не буде знайдено ключ K або вільна позиція. Не погано було б мати правило, згідно з яким кожен ключ K визначає послідовність проб, тобто послідовність позицій в таблиці, які потрібно переглядати кожного разу при вставці або пошуку K. Якщо ми, використовуючи визначається K послідовність проб, натраплю на вільну позицію, то можна зробити висновок, що K немає в таблиці, тому що та ж послідовність проб виконується кожен раз при обробці даного ключа. Цей загальний клас методів У. Петерсон назвав відкритої адресацією.
Найпростіша схема відкритої адресації, відома як лінійне
випробування, використовує циклічну послідовність
h (K), h (K) -1, ..., 0, M-1, M-2, ..., h (K) +1 (*)
і описується в такий спосіб.
alg L. (Пошук з вставкою по відкритій розсіяною таблиці.)
Алгоритм дозволяє розшукати цей ключ K в таблиці з M вузлів.
Якщо K немає в таблиці і вона не повна, ключ K вставляється.
Вузли таблиці позначаються через TABLE [i], 0? I
двох різних типів вузлів - вільних і зайнятих. Зайнятий вузол
містить ключ KEY [i] і, можливо, інші поля. Значення допоміжної змінної N дорівнює кількості зайнятих вузлів; ця змінна розглядається як частина таблиці, і при вставці нового ключа її значення збільшується на 1.
Цей алгоритм використовує хеш-функцію h (K) і лінійну
послідовність проб (*) для адресації. Модифікації цієї
послідовності обговорюються нижче.
L1. [Хешування.] Встановити i? H (K). (Тепер 0? I
L2. [Порівняти.] Якщо вузол TABLE [i] вільний, то перейти на L4. В
Інакше, якщо KEY [i] = K, алгоритм закінчується вдало.
L3. [Перейти до наступного.] Встановити i? (I-1); якщо тепер i
Встановити i? I + M. Назад на L2.
L4. [Вставити.] (Пошук був невдалим.) Якщо N = M-1, алгоритм
закінчується по переповнення. В іншому
випадку встановити N? N 1, відзначити, що вузол TABLE [i] зайнятий і
встановити KEY [i]? K.
На рис. (Див. нижче) показано, що відбувається при вставці з допомогою алгоритму ~ L семи "норвезьких" ключів, що мають коди хешування 2, 7, 1, 8, 2, 8, 1
відповідно. Останні три ключа-FEM, SEKS і SYV-зміщені по
порівнянні зі своїми початковими адресами h (K).
0 [FEM]
1 [TRE]
2 [EN]
3 []
4 []
5 [SYV]
6 [_SEKS]
7 [_ TO]
8 [FIRE]
Рис. Лінійна відкрита адресація.
Експерименти з лінійним випробуванням показують, що цей метод працює чудово, поки таблиця не надто заповнена, але врешті-решт процес сповільнюється, довгі серії проб стають все більш частими. Причину такої поведінки можна зрозуміти, розглянувши наступну гіпотетичну розсіяну таблицю (M = 19, N = 9):
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Заштриховані квадрати позначають зайняті позиції. Ключ K, який повинен бути вставлений у таблицю наступним, потрапить в одну з десяти вільних позицій, але не з рівними ймовірностями. Справді, K буде вставлений у позицію 11, якщо 11? H (K)? 15, а в позицію 8 він потрапить лише при h (K) = 8. Отже, ймовірність потрапити в
11 позицію в п'ять разів більше, ніж у позицію 8; довгі списки прагнуть стати ще довшим.
alg D. (Відкрита адресація з подвійним хешування.)
Цей алгоритм майже збігається з алгоритмом L, але використовує дещо іншу послідовність проб, обчислюючи два хеш-функції h1 (K) і h2 (K). Як звичайно, h1 (K) породжує величини від 0 до M-1 включно, та значення h2 (K) должни лежати від 1 до M-1 і бути взаємно прості з M. (Наприклад, якщо M - просте число, то h2 (K) може бути будь-який величиною від 1 до M-1 включно, або, якщо M = 2m, то h2 (K) може бути будь-яким непарним числом між 1 і 2m-1. )
D1. [Перше хешування.] Встановити i? H2 (K).
D2. [Перша проба.] Якщо вузол TABLE [i] вільний, то перейти
на D6. В іншому випадку, якщо KEY [i] = K, алгоритм
закінчується вдало.
D3. [Друге хешування.] Встановити c? H2 (K).
D4. [Перейти до наступного.] Встановити i? Ic; якщо тепер i
Встановити i? I + M.
D5. [Рейтинг.] Якщо вузол TABLE [i] вільний, то перейти
на D6. В іншому випадку, якщо KEY [i] = K, алгоритм закінчується
вдало; в іншому випадку повернутися на D4.
D6. [Вставка.] Якщо N = M-1, алгоритм закінчується по переповнення. В
Інакше встановити N? N 1, позначити вузол TABLE [i] як зайнятий
і встановити KEY [i]? K.
Для обчислення h2 (K) було запропоновано декілька способів.
Якщо M - просте число і h1 (K) = K mod M, можна покласти h2 (K) = 1 + (K mod (M-1)); але так як M-1 парних, було б краще покласти h2 (K) = 1 + (K mod (M-2)).
Це наводить на думку про такому виборі M, щоб M і M-2билі простими числами-близнюками, наприклад 1021 і 1019. Можна взяти h2 (K) = 1 + ([K/M] mod (M-2)), бо приватне [K/M] можна отримати в реєстрі як побічний продукт обчислення h1 (K).
Порівняння методів. Отже, ми знаємо багато методів пошуку;
чому ж нам керуватися при виборі найкращого з них;
для конкретного додатка? Важко в кількох словах описати все, що нам хотілося б врахувати при виборі методу пошуку, проте наступні міркування, мабуть, найбільш важливі, якщо ми зацікавлені в скороченні часу пошуку і обсягу займаної пам'яті.
Різні способи вирішення колізій призводять до різного числа проб. Але це ще не все, так як зі зміною методу змінюється час проби, що помітно позначається на часі роботи. При лінійному випробуванні частіше, ніж в інших методах, відбувається звернення до таблиці, зате цей метод простий.
Методи ланцюжків вельми економні з точки зору числа проб, але потреба в додатковому просторі пам'яті для полів посилань іноді (при невеликому розмірі записів) робить більш привабливою відкриту адресацію. Наприклад, якщо потрібно зробити вибір між таблицею з ланцюжками на 500 елементів і таблицею з відкритою адресацією на 1000 елементів, то остання, очевидно, краще, бо вона забезпечує ефективний пошук серед 500 записів і здатна вмістити в два рази більше даних. З іншого боку, часом в силу розміру записів або їх формату простір під поля посилань дістається фактично безкоштовно.
Як співвідносяться методи хешування з іншими стратегіями пошуку? Порівнюючи їх за швидкістю, можна стверджувати, що методи хешування краще, якщо кількість записів великий, оскільки середній час пошуку для методів хешування залишається обмеженим при N?? у випадку, коли таблиця не стає занадто заповненої. Більш того, бінарний пошук годиться лише для фіксованих таблиць, у той час як розсіяні таблиці допускають ефективні процедури вставки.
Таким чином, Хешування має свої переваги. З іншого боку, пошук в розсіяних таблицях все ж таки поступається вивченим раніше методів за трьома важливими пунктами.
a) Після невдалого пошуку в розсіяною таблиці ми знаємо лише те, що потрібного ключа там немає. Методи пошуку, засновані на порівняннях, завжди дають більше інформації, вони дозволяють знайти найбільший ключ? K або найменший ключ? K, що важливе у багатьох додатках
(наприклад, для інтерполяції значень функції з зберігається таблиці).
Ці ж методи можна використовувати і для знаходження всіх ключів, що лежать між двома заданими величинами K і K '. Далі, алгоритми пошуку по дереву дозволяють легко роздрукувати вміст таблиці у зростаючому порядку без спеціальної сортування, а це іноді буває потрібно.
b) Часто буває важко розподілити пам'ять для розсіяних таблиць; під хеш-таблицю потрібно відвести певну область пам'яті, а розмір її не завжди ясний. Якщо відвести занадто багато пам'яті, то така марнотратство відіб'ється на інших списках або на інших користувачів ЕОМ, але якщо відвести мало місця, таблиця переповниться! При переповненні розсіяною таблиці, мабуть, краще за все "рехешіровать" її, тобто відвести більше простору і змінити хеш-функцію, а потім вставити запису у велику таблицю. Ф. ~ Хопгуд запропонував рехешіровать таблицю, якщо коефіцієнт заповнення досягне? 0, замінюючи M на d0M.
Алгоритми пошуку зі вставкою по дереву не буяє тяжкими рехешірованіямі; дерева ростуть не більше, ніж це необхідно. При роботі з віртуальною пам'яттю потрібно, цілком ймовірно, використовувати пошук по дереву або цифровий пошук по дереву замість створення великих розсіяних таблиць, що викликають підкачки нової сторінки майже при кожному хешуванні ключа.
c) Нарешті, при використанні методів хешування треба свято вірити в теорію ймовірностей, бо вони ефективні лише в середньому, а найгірший випадок просто жахливий! Як і в ситуації з датчиками випадкових чисел, ми не можемо бути повністю впевненими в тому, що при застосуванні до нового безлічі даних хеш-функція буде працювати задовільно. Тому розсіяна пам'ять не завжди підходить для роботи в реальному масштабі часу, наприклад для управління рухом транспорту, оскільки на карту поставлені людські життя. Алгоритми збалансованого дерева набагато безпечніше, адже вони мають гарантовану верхню межу часу пошуку.
