загрузка...

трусы женские
загрузка...

Хешування

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

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

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

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

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

«Хешування»

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

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

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

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

Воронеж 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] вона буде розподілена дуже рівномірно. Іншими словами, кожне нове значення буде потрапляти

Сторінки: 1 2 3 4
загрузка...
ur.co.ua

енциклопедія  з сиру  аджапсандалі  ананаси  узвар