Здавалка
Главная | Обратная связь

Хеш-функції і хеш-адресація



Кращих результатів можна досягнути, якщо застосовувати методи, пов'язані з використанням хеш-функцій і хеш-адресацій. Хеш-функцією h називається деяке відображення множини вхідних елементів R на множину цілих невід'ємних чисел Z:

h(r) = z , r є R , z є Z.

Множина допустимих вхідних елементів R називається областю визначення хеш-функции. Множиною значень хеш-функції F називається підмножина М множини Z ( ), що містить всі можливі значення, які можуть повертатись функцією h:

Процес відображення області визначення хеш-функції на множину значень називається хешуванням.

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

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

В ідеальному випадку для розміщення будь-якого елемента в хеш-таблиці достатньо тільки обчислити його хеш-функцію і звернутися до потрібної комірки масиву даних. Для пошуку елемента в хеш-таблиці також необхідно обчислити хеш-функцію для шуканого елемента і перевірити, чи не є задана нею комірка масиву порожньою (якщо вона не порожня - елемент знайдений, якщо порожня - не знайдений). Спочатку хеш-таблиця повинна бути заповнена інформацією, що дозволила б говорити про те, що всі її комірки є порожніми. Цей метод досить ефективний, оскільки як час розміщення елемента в хеш-таблиці, так і час його пошуку визначаються тільки часом, що витрачається на обчислення хеш-функції, що в загальному випадку значно менше часу, необхідного для багаторазових порівнянь елементів хеш-таблиці. Метод має два очевидних недоліки. Перший з них - неефективне використання об'єму пам'яті під хеш-таблицю: розмір масиву для її зберігання повинен відповідати всій області значень хеш-функції, у той час, як реально збережених у хеш-таблиці даних може бути істотно менше. Другий недолік – це необхідність відповідного розумного вибору хеш-функції. Цей недолік є настільки істотним, що не дозволяє безпосередньо використовувати хеш-адресацію для організації хеш-таблиць.

Проблема вибору хеш-функції не має універсального рішення. Хешування зазвичай відбувається за рахунок виконання над послідовністю вхідних символів деяких простих арифметичних або логічних операцій. Найпростішою хеш-функцією для одного символу є його код внутрішнього представлення в комп'ютері. Цю хеш-функцію можна використовувати і для послідовності символів, вибираючи перший символ в послідовності.

Очевидно, що така примітивна хеш-функція буде незадовільною: при її використанні виникне проблема — двом різним словам, що починаються з однієї і тої ж букви, буде відповідати те саме значення хеш-функції. Тоді при хеш-адресації в одну і ту саму комірку хеш-таблиці повинні бути розміщені два різних слова, що явно неможливо. Така ситуація, коли двом або більше вхідним даним відповідає одне і те саме значення хеш-функції, називається колізією. Природно, що хеш-функція, що допускає колізії, не може бути використана для хеш-адресації в хеш-таблиці. Причому досить одержати хоча б один випадок колізії на всій множинаі слів, щоб такою хеш-функцією не можна було користуватися. Але чи можливо побудувати хеш-функцію, яка б повністю виключала виникнення колізій? Для повного виключення колізій хеш-функція повинна бути взаємно однозначною: кожному елементу з області визначення хеш-функції повинне відповідати одне значення з її множини значень, і навпаки - кожному значенню з множини значень цієї функції повинен відповідати тільки один елемент із її області визначення. Тоді будь-яким двом довільним елементам з області визначення хеш-функції будуть завжди відповідати два різні її значення. Теоретично таку хеш-функцію побудувати можна, тому що і область визначення хеш-функції (наприклад, всі можливі імена ідентифікаторів), і область її значень (цілі невід'ємні числа) є нескінченними зліченими множинами, тому можна організувати взаємно однозначне відображення однієї множини на іншу.

Але на практиці існує обмеження, що робить створення взаємно однозначної хеш-функції неможливим. Справа в тому, що в реальності область значень будь-який хеш-функції обмежена розміром доступного адресного простору комп'ютера. Множина адрес будь-якого комп'ютера із традиційною архітектурою може бути достатньо великою, але завжди скінченою, тобто обмеженою. Організувати взаємно однозначне відображення нескінченної множини на скінчену навіть теоретично неможливо. Можна, звичайно, врахувати те, що довжина значимої частини імені ідентифікатора в реальних компіляторах на практиці також обмежена - зазвичай вона лежить в межах від 32 до 128 символів (тобто і область визначення хеш-функції скінчена). Але і тоді кількість елементів в скінченій множині, що складає область визначення хеш-функції, буде перевищувати їх кількість в скінченій множинаі області значень (кількість всіх можливих слів більша за кількість допустимих адрес в сучасних комп'ютерах). Таким чином, створити взаємно однозначну хеш-функцію на практиці неможливо. Отже, неможливо уникнути виникнення колізій.

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

 

2.4. Хеш-таблиця з рехешуванням

Для розв'язання проблеми колізії можна використовувати багато способів. Одним з них є метод рехешування (або повторного хешування). Відповідно до цього методу, якщо для елемента key адреса z0 = h(key), що обчислена за допомогою хеш-функції h, вказує на вже зайняту комірку, то необхідно обчислити значення функції z1 = h1(key) і перевірити зайнятість комірки за адресою z1. Якщо і вона зайнята, то обчислюється значення h2(key), і так далі доти, поки або не буде знайдена вільна комірка, або чергове значення hі(key) не співпаде зі значенням h(key). В останньому випадку вважається, що хеш-таблиця заповнена і місця в ній більше немає.

Пошук елемента key в хеш-таблиці, організованій таким чином, буде виконуватися по наступному алгоритму:

1. Обчислити значення хеш-функції z = h(key) для шуканого елемента з ключем key.

2. Якщо комірка за адресою z порожня, то робиться висновок, що елемент не знайдений і алгоритм завершує свою роботу, інакше необхідно порівняти ім'я елемента в комірці z з ім'ям шуканого елемента. Якщо вони співпадають, то робиться висновок, що елемент знайдений і алгоритм завершує свою роботу, інакше змінній i надається значення 1 і переходиться до кроку 3.

3. Обчислити zі = hі(key). Якщо комірка за адресою zі порожня або z = zі , то елемент не знайдений і алгоритм завершується, інакше — порівняти ім'я елемента в комірці zі, з ім'ям шуканого елемента. Якщо вони співпадають, то елемент знайдений і алгоритм завершується, інакше і = i + 1 і повторюється крок 3.

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

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

Для організації хеш-таблиці по методу рехешування необхідно визначити всі хеш-функції hі для всіх i. Найчастіше функції hі визначають як деякі модифікації хеш-функції h. Наприклад, найпростішим методом обчислення функції hі(key) є її організація у вигляді:

hі(key) = (h(key) + pі ) mod m ,

де рі - деяке ціле число, що обчислюється, а m - максимальне значення з області значень хеш-функції h. У свою чергу, найпростішим підходом тут буде покласти pі = і. Тоді одержуємо формулу:

hі(key) = (h(key) + і ) mod m .

В цьому випадку при співпадінні значень хеш-функції для яких-небудь елементів пошук вільної комірки в хеш-таблиці продовжується послідовно, починаючи від поточної позиції, заданої хеш-функцією h(key).

Цей спосіб не можна визнати особливо вдалим тому, що при співпадінні хеш-адрес елементи в хеш-таблиці починають групуватися навколо них, що збільшує число необхідних порівнянь при пошуку і розміщенні. Але навіть такий примітивний метод рехешування є досить ефективним засобом організації хеш-таблиць при неповному заповненні хеш-таблиці. Середній час на розміщення одного елемента в хеш-таблиці і на пошук елемента в хеш-таблиці можна знизити, якщо застосувати більш досконалий метод рехешування. Одним з таких методів є використання в якості pi для функції hі(key) = (h(key) + pі) mod m послідовності псевдовипадкових цілих чисел p1, р2 , ... , рk . При гарному виборі генератора псевдовипадкових чисел довжина послідовності k = m.

Існують і інші методи організації функцій рехешування основанні на квадратичних обчисленнях або, наприклад, на обчисленні добутку по формулі:

hі(key) = (h(key) · С · i) mod m' ,

де С – константа, m' - найближче просте число, менше за m.

В цілому рехешування дозволяє досягнути непоганих результатів для ефективного пошуку елемента в хеш-таблиці (кращих, ніж бінарний пошук), але ефективність методу сильно залежить від заповненості хеш-таблиці і якості використовуваної хеш-функції — чим рідше виникають колізії, тим вище ефективність методу.

При будь-якому методі вирішення колізій необхідно обмежити довжину пошуку елемента. Якщо для пошуку елемента необхідно більше 3 - 4 порівнянь, то ефективність використання такої хеш-таблиці значно погіршується і її треба реструктуризувати (тобто знайти іншу хеш-функцію), щоб мінімізувати кількість порівнянь для пошуку елемента.

 

2.5. Хеш-таблиця з використанням методу ланцюжків

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

В комірках проміжної хеш-таблиці може зберігатися або порожнє значення, або значення вказівника на деяку область пам'яті з основної таблиці значень. Тоді хеш-функція обчислює адресу, по якій відбувається звертання спочатку до проміжної хеш-таблиці, а потім вже через неї по знайденій адресі — до основної таблиці значень. Якщо відповідна комірка таблиці значень порожня, то комірка проміжної хеш-таблиці буде містити порожнє значення. Тоді зовсім не обов'язково мати в самій хеш-таблиці комірки для кожного можливого значення хеш-функції — хеш-таблицю можна зробити динамічною, так щоб її об'єм ріс по мірі заповнення. Такий підхід дозволяє домогтися двох позитивних результатів: по-перше, немає необхідності заповнювати таблицю порожніми значеннями — це можна зробити тільки для хеш-таблиці; по-друге, кожному елементу буде відповідати строго одна комірка у таблиці значень. Порожні комірки в такому випадку будуть тільки в хеш-таблиці, і об'єм невикористовуваної пам'яті не буде залежати від обсягу інформації, збереженої для кожного вхідного елемента, — для кожного значення хеш-функції буде витрачатися тільки пам'ять, необхідна для зберігання одного вказівника на основну таблицю значень. На основі цієї схеми можна реалізувати ще один спосіб організації хеш-таблиць за допомогою хеш-функції, що називається методом ланцюжків або методом роздільних ланцюжків. У цьому випадку таблиця значень представляється як набір лінійних зв'язаних однонаправлених списків.

Наприклад, нижче на малюнку зображена хеш-таблиця, як масив з 8 елементів:

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

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

 







©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.