Хешування

Інформатика, програмування

Міністерство Освіти РФ

Воронезький державний університет

Факультет комп'ютерних наук

Кафедра програмування та інформаційних технологій

Курсова робота з курсу « Технології програмування »на тему

« Хешування »

Виконав: студент 3его курсу

Шадчнев Євген

Перевірив: доцент каф. Пиит

Хлебостроев Віктор Григорович

Воронеж 2003

Зміст

Вступ 3

Хеш-функції 4

Метод поділу 4

Метод множення (мультиплікативний) 5

Динамічне Хешування 5

Розширюване Хешування (extendible hashing) 7

Функції, що зберігають порядок ключів (Order preserving hash functions) 8

Мінімальна ідеальне Хешування 8

Дозвіл колізій 10

Метод ланцюжків 10

Відкрита адресація 10

Лінійна адресація 11

Квадратична і довільна адресація 11

Адресація з подвійним хешування 11

Видалення елементів хеш-таблиці 12

Застосування хешування 13

Хешування паролів 13

Висновок 15

Додаток (демонстраційна програма) 15

Список літератури: 16

Введення

З хешування ми стикаємося чи не на кожному кроці: під час роботи збраузером (список 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). Ця робота привела до створення відкритої адресаціїз подвійним хешування.
Далі будуть розглянуті основні види хеш-функцій та деякі їхмодифікації, методи вирішення колізій, проблеми видалення елементів з хеш -таблиці, а також деякі варіанти застосування хешування.

Хеш-функції

Хеш-функція - це деяка функція h (K), що бере якийсь ключ K іповертає адресу, за яким здійснюється пошук в хеш-таблиці, щоботримати інформацію, пов'язану з K. Наприклад, K - це номер телефонуабонента, а шукана інформація - його ім'я. Функція в даному випадку нам точноскаже, за якою адресою знайти шукане. Приклад з телефонним довідникомілюструється демонстраційної програмою на що додається компакт-диск.
Колізія - це ситуація, коли h (K1) = h (K2), у той час як K1? K2. Уцьому випадку, очевидно, необхідно знайти нове місце для зберігання даних.
Очевидно, що кількість колізій необхідно мінімізувати. Методикадозволу колізій буде присвячено окремий розділ нижче.
Гарна хеш-функція повинна задовольняти двом вимогам:

. її обчислення повинно виконуватися дуже швидко;

. вона повинна мінімізувати кількість колізій.
Отже, перша властивість хорошої хеш-функції залежить від комп'ютера, а другий --від даних. Якби всі дані були випадковими, то хеш-функції були б дужепрості (кілька бітів ключа, наприклад). Однак на практиці випадковідані зустрічаються вкрай рідко, і доводиться створювати функцію, яказалежала б від усього ключа.
Теоретично неможливо визначити хеш-функцію так, щоб вона створювалавипадкові дані з реальних невипадкових файлів. Однак на практиці реальностворити достатньо хорошу імітацію за допомогою простих арифметичнихдій. Більш того, часто можна використовувати особливості даних длястворення хеш-функцій з мінімальним числом колізій (меншим, ніж приістинно випадкових даних) [3].
Можливо, одним з найбільш очевидних і простих способів хешування єметод середини квадрата, коли ключ зводиться в квадрат і беретьсякілька цифр у середині. Тут і далі передбачається, що ключ спочаткуприводиться до цілого числа, для здійснення з ним арифметичних операцій.
Однак такий спосіб добре працює до моменту, коли немає великогокількості нулів зліва чи справа. Численні тести показали хорошуроботу двох основних типів хешування, один з яких заснований на розподілі,а інший на примноження. Втім, це не єдині методи, якііснують, більше того, вони не завжди є оптимальними.

Метод поділу

Метод поділу дуже простий - використовується залишок від ділення на M:

h (K) = K mod M

Треба ретельно вибирати цю константу. Якщо взяти її рівною 100, а ключембуде злучити рік народження, то розподіл буде дуже нерівномірним дляряду завдань (ідентифікація гравців юнацької бейсбольної ліги, наприклад).
Більш того, при парному константі значення функції буде парних при парній Kі непарних - при непарній, що призведе до небажаного результату. Щегірші справи, якщо M - це ступінь числення комп'ютера, оскільки прице результат буде залежати тільки від кількох цифр ключа справа. Точнотакож можна показати, що M не повинно бути кратне трьом, оскільки прибуквених ключах два з них, що відрізняються тільки перестановкою літер, можутьдавати числові значення з різницею, кратною трьом (див. [3], стр. 552).
Наведені міркування приводять до думки, що краще використовувати простечисло. У більшості випадків такий вибір цілком задовільний.
Інший приклад - ключ, що є символьної рядком С + +. Хеш-функціявідображає цей рядок в ціле число за допомогою підсумовування першого іостаннього символів і подальшого обчислення залишку від ділення на 101
(розмір таблиці). Ця хеш-функція призводить до колізії при однакових першихі останньому символи рядка. Наприклад, рядки «start» і «slant» будутьвідображатися в індекс 29. Так само поводиться хеш-функція, підсумовує всісимволи рядка. Рядки «bad» і «dab» перетворюються в один і той же індекс.
Кращі результати дає хеш-функція, що виробляє перемішування бітів усимволах.
На практиці, метод поділу - найпоширеніший [7].

Метод множення (мультиплікативний)

Для мультиплікативного хешування використовується така формула:

h (K) = [M * ((C * K) mod 1)]

Тут виробляється множення ключа на якусь константу С, що лежить вінтервалі [0 .. 1]. Після цього береться дрібна частина цього виразу імножиться на деяку константу M, обрану таким чином, щобрезультат не вийшов за межі хеш-таблиці. Оператор [] повертаєнайбільше ціле, яке менше аргументу.
Якщо константа З вибрана вірно, то можна досягти дуже хорошихрезультатів, однак, цей вибір не складно зробити. Дональд Кнут (див. [3], стор
553) зазначає, що множення може іноді пришвидшитися поділу.
Мультиплікативний метод добре використовує те, що реальні файлиневипадкові. Наприклад, часто безлічі ключів представляють собоюарифметичні прогресії, коли у файлі містяться ключі (K, K + d, K +
2d, ..., K + td). Наприклад, розглянемо імена типу (PART1, PART2, ..., PARTN).
Мультиплікативний метод перетворює арифметичної прогресії у наближенніарифметичної прогресії h (K), h (K + d), h (K + 2d), ... різних хеш -значень, зменшуючи кількість колізій в порівнянні з випадковою ситуацією.
Втім, справедливості заради треба помітити, що метод поділу володіє тимж властивістю.
Приватним випадком вибору константи є значення золотого перетину? = (? 5
- 1)/2? 0,6180339887. Якщо взяти послідовність (?), (2?), (3 ?},...де оператор () повертає дробову частина аргументу, то на відрізку [0 .. 1]вона буде розподілена дуже рівномірно. Іншими словами, кожен новийзначення буде потрапляти в найбільший інтервал. Це явище було впершевідмічено Я. Одерфельдом (J. Oderfeld) і доведено С. Сверчковскі (S.
? wierczkowski) (див. [8]). У доказі відіграють важливу роль числа
Фібоначчі. Стосовно до хешування це означає, що якщо якконстанти З вибрати золотий перетин, то функція буде досить добрерозсіювати ключі виду (PART1, PART2, ..., PARTN). Таке Хешуванняназивається хешування Фібоначчі. Втім, існує ряд ключів (колизміна відбувається не в останній позиції), коли Хешування Фібоначчівиявляється не самим оптимальним [3].

Динамічне Хешування

Описані вище методи хешування є статичними, тобто спочаткувиділяється якась хеш-таблиця, під її розмір підбираються константи для хеш -функції. На жаль, це не підходить для задач, у яких розмір базиданих змінюється часто і значно [9]. Із зростанням бази даних можна

. користуватися початкової хеш-функцією, втрачаючи продуктивність через зростання колізій;

. вибрати хеш-функцію «із запасом», що спричинить невиправдані втрати дискового простору;

. періодично змінювати функцію, перераховувати всі адреси. Це забирає дуже багато ресурсів і виводить з ладу базу на деякий час.
Існує техніка, що дозволяє динамічно змінювати розмір хеш-структури
[10]. Це - динамічний хешування. Хеш-функція генерує так званийпсевдоключ ( "pseudokey"), який використовується лише частково для доступу доелементу. Іншими словами, генерується досить довга бітовапослідовність, яка має бути достатньою для адресації всіхпотенційно можливих елементів. У той час, як при статичномухешуванні потрібна була б дуже велика таблиця (яка зазвичай зберігаєтьсяв оперативній пам'яті для прискорення доступу), тут розмір використаної пам'ятіпрямо пропорційний кількості елементів в базі даних. Кожен запис втаблиці зберігається не окремо, а в якомусь блоці ( "bucket"). Ці блокизбігаються з фізичними блоками на пристрої зберігання даних. Якщо в блоцінемає більше місця, щоб вмістити запис, то блок ділиться на два, а на йогомісце ставиться покажчик на два нових блоку.
Завдання полягає в тому, щоб побудувати бінарне дерево, на кінцях гілокякого були б покажчики на блоки, а навігація здійснювалася б наоснові псевдоключа. Вузли дерева можуть бути двох видів: вузли, якіпоказують на інші сайти або вузли, які показують на блоки. Наприклад,хай вузол має такий вигляд, якщо він показує на блок:

Якщо ж він буде показувати на два інших вузла, то він буде мати такийвигляд:

Спочатку є тільки покажчик на динамічно виділений порожній блок. Придодавання елемента обчислюється псевдоключ, і його біти по черзівикористовуються для визначення місця розташування блоку. Наприклад (див. малюнок),елементи з псевдоключамі 00 ... будуть поміщені в блок A, а 01 ... - в блок B.
Коли А буде переповнений, він буде розбито таким чином, що елементи 000 ...і 001 ... будуть розміщені в різних блоках.

Розширюване Хешування (extendible hashing)

Розширюване Хешування близько до динамічного. Цей метод такожпередбачає зміну розмірів блоків по зростанням бази даних, але цекомпенсується оптимальним використанням місця. Оскільки за один разрозбивається не більше одного блоку, накладні витрати досить малі [9].
Замість бінарного дерева розширюване Хешування передбачає список,елементи якого посилаються на блоки. Самі ж елементи адресуються задеякій кількості i бітів псевдоключа (див. рис). При пошуку береться iбітів псевдоключа і через список (directory) знаходиться адреса шуканогоблоку. Додавання елементів проводиться складніше. Спочатку виконуєтьсяпроцедура, аналогічна пошуку. Якщо блок неповна, додається запис у ньогоі в базу даних. Якщо блок заповнений, він розбивається на два, записиперерозподіляються за описаним вище алгоритмом. У цьому випадку можливезбільшення числа біт, необхідних для адресації. У цьому випадку розмірсписку подвоюється і кожному новоствореному елементу присвоюєтьсяпокажчик, який містить його батько. Таким чином, можлива ситуація,коли кілька елементів показують на один і той же блок. Слідпомітити, що за одну операцію вставки перераховуються значення не більше,ніж одного блоку. Видалення здійснюється за таким же алгоритмом, тількинавпаки. Блоки, відповідно, можуть бути склеєні, а список - зменшений удва рази.

Отже, основною перевагою розширюваного хешування є високаефективність, яка не падає при збільшенні розміру бази даних. Крімцього, розумно витрачається місце на пристрої зберігання даних, тому що блокивиділяються тільки під реально існуючі дані, а список покажчиків наблоки має розміри, мінімально необхідні для адресації даногокількості блоків. За ці переваги розробник розплачуєтьсядодатковим ускладненням програмного коду.

Функції, що зберігають порядок ключів (Order preserving hash functions)

Існує клас хеш-функцій, які зберігають порядок ключів [11].
Іншими словами, виконується

Ці функції корисні для сортування, яка не потребує ніякоїдодаткової роботи. Іншими словами, ми уникнемо безлічі порівнянь,тому що для того, щоб відсортувати об'єкти за зростанням досить простолінійно просканувати хеш-таблицю.
У принципі, завжди можна створити таку функцію, за умови, що хеш -таблиця більше, ніж простір ключів. Однак, завдання пошуку правильноїхеш-функції нетривіальні. Зрозуміло, вона дуже сильно залежить відконкретного завдання. Крім того, подібне обмеження на хеш-функцію можезгубно позначитися на її продуктивності. Тому часто вдаються доіндексуванню замість пошуку подібної хеш-функції, якщо тільки заздалегідь невідомо, що операція послідовної вибірки буде частою.

Мінімальна ідеальне Хешування

Як уже згадувалося вище, ідеальна хеш-функція повинна швидко працювати імінімізувати кількість колізій. Назвемо таку функцію ідеальною (perfecthash function) [12]. З такою функцією можна було б не користуватисямеханізмом вирішення колізій, тому що кожен запит був би вдалим. Але можнанакласти ще одна умова: хеш-функція повинна заповнювати хеш-таблицю безпробілів. Така функція буде називатися мінімальний?? ідеальної хеш -функцією. Це ідеальний випадок з точки зору споживання пам'яті та швидкостіроботи. Очевидно, що пошук таких функцій - дуже нетривіальне завдання.
Один з алгоритмів для пошуку ідеальних хеш-функцій був запропонований Р.
Чічеллі [13]. Розглянемо набір деяких слів, для яких треба скластимінімальну ідеальну хеш-функцію. Нехай це будуть деякі ключові словамови С + +. Нехай це буде якась функція, яка залежить від якогосьчисельного коду кожного символу, його позиції та довжини. Тоді завдання створенняфункції зведеться до створення таблиці кодів символів, таких, щоб функціябула мінімальною і ідеальною. Алгоритм дуже простий, але займає дуже багаточасу для роботи. Проводиться повний перебір всіх значень в таблиці звідкотом тому в разі необхідності, з метою підібрати всі значення так,щоб не було колізій. Якщо взяти для простоти функцію, яка складаєкоди першого і останнього символу з довжиною слова (так, серед слів навмиснонемає таких, які дають колізію), то алгоритм дає такий результат:

| Auto | 21 | Double | 0 | Int | 15 | Struct | 23 |
| Break | 28 | Else | 12 | Long | 26 | Switch | 17 |
| Case | 1 | Enum | 4 | Register | 18 | Typedef | 29 |
| Char | 2 | Extern | 9 | Return | 10 | Union | 30 |
| Const | 8 | Float | 27 | Short | 22 | Unsigned | 24 |
| Continue | 5 | For | 20 | Signed | 3 | Void | 13 |
| Default | 7 | Goto | 19 | Sizeof | 25 | Volatile | 31 |
| Do | 14 | If | 16 | Static | 6 | While | 11 |

Докладний аналіз алгоритму, а також реалізацію на С + + можна знайти за адресою
[12]. Там же описуються методи вирішення колізій. На жаль, ця темавиходить за рамки цієї роботи.

Дозвіл колізій

Складання хеш-функції - це не вся робота, яку належить виконатипрограмісту, реалізує пошук на основі хешування. Крім цього,необхідно реалізувати механізм вирішення колізій. Як і з хеш-функціямиіснує кілька можливих варіантів, які мають свої переваги інедоліки.

Метод ланцюжків

Метод ланцюжків - найочевидніший шлях вирішення проблеми. У випадку, колиелемент таблиці з індексом, який повернула хеш-функція, вже використано, до ньогоприєднується зв'язний список. Таким чином, якщо для декількох різнихзначень ключа повертається однакове значення хеш-функції, то з цьогоадресою знаходиться вказівник на зв'язаний список, який містить всізначення. Пошук в цьому списку здійснюється простим перебором, тому що приграмотному виборі хеш-функції будь-якої зі списків виявляється доситькоротким. Але навіть тут можлива додаткова оптимізація. Дональд Кнут
([3], стр. 558) відзначає, що можлива сортування списків за часомзвернення до елементів. З іншого боку, для підвищення швидкодіїбажані великі розміри таблиці, але це призведе до непотрібної витраті пам'ятіна свідомо порожні елементи. На малюнку нижче показана структура хеш-таблиціта освіта ланцюжків при виникненні колізій.

Прекрасна наочна ілюстрація цієї схеми дозволу колізій у вигляді Java -аплету разом з вихідним кодом на C + + представлена за адресою [14].

Відкрита адресація

Інший шлях вирішення проблеми, пов'язаної з колізіями, полягає в тому, щобповністю відмовитися від посилань, просто переглядаючи різні записитаблиці по порядку до тих пір, поки не буде знайдений ключ K або порожняпозиція [3]. Ідея полягає у формулюванні правила, згідно з якимпо даному ключу визначається «пробна послідовність», тобтопослідовність позицій таблиці, які повинні бути переглянуті привставці або пошуку ключа K. Якщо при пошуку зустрічається порожня клітинка, томожна зробити висновок, що K в таблиці відсутній, бо ця клітинка була бзайнята при вставці, тому що алгоритм проходив ту ж саму ланцюжок. Цей загальнийклас методів названий відкритої адресацією [4].

Лінійна адресація

Найпростіша схема відкритої адресації, відома як лінійна адресація
(лінійне дослідження, linear probing) використовує циклічнупослідовність перевірок

h (K), h (K - 1), ..., 0, M - 1, M - 2, ..., h (K) + 1

і описується наступним алгоритмом ([3], стр. 562). Він виконує пошукключа K в таблиці з M елементів. Якщо таблиця не повна, а ключвідсутній, він додається.
Стовпчики таблиці позначаються як TABLE [i], де 0? i

1. Встановити i = h (K)

2. Якщо TABLE [i] порожній, то перейти до кроку 4, інакше, якщо за цією адресою шуканий, алгоритм завершується.

3. Встановити i = i - 1, якщо i <0, то i = i + M. Назад до кроку 2.

4. Вставка, тому що пошук виявився невдалим. Якщо N = M - 1, то алгоритм завершується за переповнення. Інакше збільшити N, позначити клітинку

TABLE [i] як зайняту і встановити в неї значення ключа K.

Досліди показують ([3], стр. 564), що алгоритм добре працює на початкузаповнення таблиці, проте у міру заповнення процес сповільнюється, адовгі серії проб стають все більш частими.

Квадратична і довільна адресація

Замість постійної зміни на одиницю, як у випадку з лінійноюадресацією, можна скористатися наступною формулою [15]

h = h + a2,

де a - це номер спроби. Цей вид адресації досить швидкий іпередбачуваний (він проходить завжди один і той же шлях по зсувів 1, 4, 9,
16, 25, 36 і т.д.). Чим більше колізій в таблиці, тим довше цей шлях. Зодного боку, цей метод дає хороший розподіл по таблиці, а з іншогозаймає більше часу для прорахунку.
Довільна адресація використовує заздалегідь згенерований список випадковихчисел для отримання послідовності [15]. Це дає виграш у швидкості,але дещо ускладнює завдання програміста.

Адресація з подвійним хешування

Цей алгоритм вибору ланцюжка дуже схожий на алгоритм для лінійноїадресації, але він перевіряє таблицю трохи інакше, використовуючи два хеш -функції h1 (K) і h2 (K). Остання повинна породжувати значення в інтервалі від 1до M - 1, взаємно прості з М.

1. Встановити i = h1 (K)

2. Якщо TABLE [i] порожній, то перейти до кроку 6, інакше, якщо за цією адресою шуканий, алгоритм завершується.

3. Встановити c = h2 (K)

4. Встановити i = i - c, якщо i <0, то i = i + M.

5. Якщо TABLE [i] порожній, то перехід на крок 6. Якщо шукане розташоване за цією адресою, то алгоритм завершується, інакше повертається на крок 4.

6. Вставка. Якщо N = M - 1, то алгоритм завершується за переповнення.

Інакше збільшити N, позначити клітинку TABLE [i] як зайняту і встановити в неї значення ключа K.

Очевидно, що цей варіант буде давати значно гарнерозподіл і незалежні один від одного ланцюжка. Однак, він кількаповільніше через введення додаткової функції.
Дональд Кнут ([3], стр. 566) пропонує кілька різних варіантіввибору додаткова функція. Якщо M - просте число і h1 (K) = K mod M,можна покласти h2 (K) = 1 + (K mod (M - 1)); однак, якщо M - 1 парному
(іншими словами, M непарній, що завжди виконується для простих чисел),було б краще покласти h2 (K) = 1 + (K mod (M - 2)).
Тут обидві функції достатньо незалежні. Гарі Гринішин (Gary Knott) в 1968запропонував при простому M використовувати наступну функцію:

h2 (K) = 1, якщо h1 (K) = 0 і h2 (K) = M - h1 (K) в іншому випадку (тобто h1 (K)> 0).

Цей метод виконується швидше повторного поділу, але призводить до збільшеннячисла проб через підвищення ймовірності того, що дві або кілька ключівпідуть за одним і тим же шляхом.

Видалення елементів хеш-таблиці

Багато програмістів настільки сліпо вірять в алгоритми, що навіть не намагаютьсязамислюватися над тим, як вони працюють. Для них неприємним сюрпризомстає те, що очевидний спосіб видалення записів з хеш-таблиці непрацює. Наприклад, якщо видалити ключ, який знаходиться в ланцюжку, заякої йде алгоритм пошуку, що використовує відкриту адресацію, то всенаступні елементи будуть втрачені, тому що алгоритм здійснює пошук доперший незайнятого елементу.
Взагалі кажучи, обробляти видалення можна, позначаючи елемент як віддалений,а не як порожній. Таким чином, кожна клітинка в таблиці міститиме вжеодне з трьох значень: порожня, зайнята, віддалена. При пошуку віддаленіелементи будуть трактуватися як зайняті, а при вставці - як порожні,відповідно.
Проте, очевидно, що такий метод можна використовувати лише коли рідкісних видалення,оскільки одного разу зайнята позиція більше ніколи не зможе стати вільною,а, значить, після довгої послідовності вставок і вилучень всівільні позиції зникнуть, а при невдалому пошуку буде вимагатися Мперевірок (де М, нагадаємо, розмір хеш-таблиці). Це буде достатньо довгийпроцес, тому що на кожному кроці № 4 алгоритму пошуку (див. розділ Адресація зподвійним хешування) буде перевірятися значення змінної i.

Розглянемо алгоритм видалення елемента i при лінійної адресації.

1. Позначити TABLE [i] як порожню комірку і встановити j = i

2. i = i - 1 або i = i + M, якщо i стало негативним

3. Якщо TABLE [i] порожній, алгоритм завершується, тому що немає більше елементів, про доступ до яких слід дбати. В іншому випадку ми встановлюємо r = h (KEY [i]), де KEY [i] - ключ, який зберігається в

TABLE [i]. Це нам дасть його первісний хеш-адреса. Якщо i? r

4. Треба перемістити запис TABLE [j] = TABLE [i] і повернутися на перший крок.

Можна показати ([3], стр. 570), що цей алгоритм не викликає зниженняпродуктивності. Однак, коректність алгоритму сильно залежить від тогофакту, що використовується лінійне дослідження хеш-таблиці, томуаналогічний алгоритм для подвійного хешування відсутній.
Цей алгоритм дозволяє переміщати деякі елементи таблиці, що можевиявитися небажано (наприклад, якщо є посилання ззовні на елементи хеш -таблиці). Інший підхід до проблеми видалення грунтується на адаптуваннядеяких ідей, що використовуються при збірці сміття: можна зберігати кількістьпосилань з кожним ключем, який говоритиме про те, як багато інших ключівстикається з ним. Тоді при обнулення лічильника можна перетворюватитакі осередки у порожні. Деякі інші методи видалення, що дозволяютьуникнути переміщення в таблиці і працюють з будь-якою хеш-технологією, булизапропоновані в [16].

Застосування хешування

Одна з побічних застосувань хешування полягає в тому, що воно створюєсвого роду зліпок, «відбиток пальця» для повідомлення, текстового рядка,області пам'яті і т. п. Такий «відбиток пальця» може прагнути як до
«Унікальності», так і до «схожості» (яскравий приклад зліпка - контрольнасума CRC). У цій якості однієї з найважливіших областей застосування єкриптографія. Тут вимоги до хеш-функцій мають свої особливості.
Крім швидкості обчислення хеш-функції потрібно значно ускладнитивідновлення повідомлення (ключа) по хеш-адресою. Відповідно необхідноускладнити знаходження іншого повідомлення з тим же хеш-адресою. Припобудові хеш-функції однонаправленої характеру зазвичай використовуютьфункцію стиснення (видає значення довжини n при вхідних даних більше довжини m іпрацює з кількома вхідними блоками). При хешуванні враховується довжинаповідомлення, щоб виключити проблему появи однакових хеш-адрес дляповідомлень різної довжини. Найбільшу популярність мають наступні хеш-функції
[17]: MD4, MD5, RIPEMD-128 (128 біт), RIPEMD-160, SHA (160 біт). Уросійському стандарті цифрового підпису використовується розробленавітчизняними криптографами хеш-функція (256 біт) стандарту ГОСТ Р
34.11-94.

Хешування паролів

Нижче передбачається, що для шифрування використовується 128-бітний ключ.
Зрозуміло, це не більше, ніж конкретний приклад. Хешування паролів --метод, що дозволяє користувачам запам'ятовувати не 128 байт, тобто 256шістнадцяткові цифр ключа, а деякий осмислений вираз, слово абопослідовність символів, що називається паролем. Дійсно, прирозробці будь-якого криптоалгоритму слід враховувати, що в половині випадківкінцевим користувачем системи є людина, а не автоматичнасистема. Це ставить питання про те, зручно, і взагалі чи реально людинізапам'ятати 128-бітний ключ (32 шістнадцяткові цифри). Насправдімежа запоминаемости лежить на кордоні 8-12 подібних символів, а,отже, якщо ми будемо примушувати користувача оперувати самеключем, тим самим ми практично змусимо його до запису ключа на якому-небудьлистку паперу або електронному носії, наприклад, в текстовому файлі. Це,природно, різко знижує захищеність системи.
Для вирішення цієї проблеми були розроблені методи, які перетворюютьговорилось осмислену рядок довільної довжини - пароль, у зазначенийключ заздалегідь заданої довжини. У переважній більшості випадків для цієїоперації використовуються так звані хеш-функції. Хеш-функцією в даномувипадку називається таке математичне або алгоритмічне перетвореннязаданого блоку даних, що має такі властивості:

1. хеш-функція має нескінченну область визначення,

2. хеш-функція має кінцеву область значень,

3. вона незворотна,

4. зміна вхідного потоку інформації на один біт міняє близько половини всіх біт вихідного потоку, тобто результату хеш-функції.
Ці властивості дозволяють подавати на вхід хеш-функції паролі, тобтотекстові рядки довільної довжини на будь-якому національному мовою і,обмеживши область значень функції діапазоном 0 .. 2N-1, де N - довжина ключав бітах, отримувати на виході досить рівномірно розподілені по областізначення блоки інформації - ключі.

Висновок

Хешування, яка народилася ще в середині минулого століття, активновикористовується в наші дні скрізь, де потрібно зробити швидку вибіркуданих. З'явилися нові методи хешування, нові модифікації алгоритмів,написаних раніше. На думку Дональда Кнута ([3], стр. 586), найбільш важливимвідкриттям в області хешування з часів 70 років, ймовірно, єлінійне Хешування Вітольда Литвина [18]. Лінійне хешування, якене має нічого спільного з класичною технологією лінійної адресації,дозволяє багатьом хеш-адресами рости і/або виступати в полі вставляються івидаляються елементів. Лінійне Хешування може також використовуватися длявеличезних баз даних, розподілених між різними вузлами в мережі.
Зрозуміло, методи та сфери застосування хешування не обмежуються тим,що представлено в цій роботі. Не вдаючись в строгий аналіз ефективності,були розглянуті тільки базові, найбільш відомі методи. Крім нихможна відзначити поліноміальною Хешування (М. Ханан та ін, 1963),впорядковане Хешування (О. Амбль, 1973), лінійне Хешування (В.
Литвин, 1980). Детальніше про методи хешування див. [3, 6, 7, 19-22].

Додаток (демонстраційна програма)

У рамках виконання даної роботи була написана демонстраційна програма,яка, використовуючи методи ділення, множення і хешування Фібоначчі,створює хеш-таблицю і здійснює пошук по ній. Програма підраховує іпоказує час, витрачений на кожну операцію, веде протокол всіхдій, що дозволяє порівняти різні алгоритми за швидкодією. Уякості вихідної бази даних використовується файл data.ans, що містить 11495записів телефонної книги одного з районів м. Воронежа зі змінениминомерами телефонів.
Програма призначена виключно для демонстрації застосування деякихалгоритмів хешування. Мова реалізації - С + +, середовище розробки - Visual
C + + 6.0. Програма розташована на що додається компакт-диску в директорії
Hashing Demo. Вихідний код розташований в каталозі Hashing Source. Вихіднабаза даних зберігається в текстовому форматі, що дає можливістьскористатися нею для отримання номерів, яким відповідають деякізаписи в базі даних, що знадобиться при тестуванні програми.

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

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

2. Єршов А.П., Вибрані праці., Новосибирск: «Наука», 1994.

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

4. Peterson WW, Addressing for Random-Access Storage// IBM Journal of

Research and Development, 1957. V.1, N2. Р.130-146.

5. Morris R., Scatter Storage Techniques// Communications of the ACM,

1968. V.11, N1. Р.38-44.

6. Buchholz W., IBM Systems J., 2 (1963), 86-111
7. http://www.optim.ru/cs/2000/4/bintree_htm/hash.asp
8. Fundamenta Math. 46 (1958), 187-189
9. http://www.cs.sfu.ca/CC/354/zaiane/material/notes/Chapter11/node20.html
10. http://www.ecst.csuchico.edu/ ~ melody/courses/csci151_live/Dynamic_hash_no tes.htm
11. http://planetmath.org/encyclopedia/Hashing.html
12. http://www.eptacom.net/pubblicazioni/pub_eng/mphash.html
13. R. Cichelli, Minimal Perfect Hashing Made Simple, Comm. ACM Vol. 23 No.

1, Jan. 1980.
14. http://www2.ics.hawaii.edu/ ~ richardy/project/hash/applet.html
15. http://www.cs.uic.edu/ ~ i201/HashingAns.pdf
16. T. Gunji, E. Goto, J. Information Proc., 3 (1980), 1-12
17. Чмора А., Сучасна прикладна криптографія., М.: Геліос АРВ, 2001.
18. Litwin W., Proc. 6th International Conf. on Very Large Databases

(1980), 212-223
19. Кормен Т., Лейзерсон Ч., Рівестом Р., Алгоритми: побудова й аналіз, М.:

МЦНМО, 2001
20. Вірт Н., Алгоритми + структури даних = програми, М.: Світ, 1985.
21. Доерніган Б., Пайк Р., Практика програмування, СПб.: Невский діалект,

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