Хеш-таблиці: теорія та практика
Оригінал: Hash Tables-Theory and Practice
Автор: Mihalis Tsoukalos
Дата публікації: 12 жовтня 2015 р.
Переклад: A.Панін
Дата перекладу: 13 жовтня 2015 р.
Вперше я дізнався про хеш-таблиці при вивченні курсу теорії компіляторів у ході навчання на бакалавра в університеті. більше і вирішив написати статтю для того, щоб усі читачі також дізналися про них.
Хеш-таблиці можуть бути реалізовані за допомогою будь-якої мови програмування, включаючи Awk. асоціативних масивів та інших механізмів та програмних продуктів. даних, що вивчаються у межах курсів комп'ютерних наук.
Постановка задачі
Завдання, яке я розглядатиму як приклад у рамках цієї статті, полягає у встановленні кількості слів з одного текстового файлу, присутніх в іншому текстовому файлі. Всі програми з цієї статті будуть використовувати один і той же текстовий файл для заповнення хеш-таблиці текстовий файл буде містити текст книги "Гордість та упередження"). буде використовуватися для тестування продуктивності хеш-таблиці. Ви можете завантажити обидва текстові файли з ресурсу Project Gutenberg.
У наступному висновку наводиться інформація про кількість слів у кожному із згаданих файлів:
$ wc AofTS.txt 9206 73845 421884 AofTS.txt $ wc PandP.txt 13426 124589 717573 PandP.txt
Як бачите, обидва текстові файли мають відносно великий розмір, що позитивно позначиться на коректності тестів. У реальному житті ваші хеш-таблиці не повинні містити такий самий великий обсяг даних. Для того, щоб видалити різні керуючі символи, а також символи пунктуації та числа, обидва текстові файли повинні бути піддані додаткової обробки:
$strings PandP.txt > temp.INPUT $awk '' temp.INPUT > new.INPUT $cat new.INPUT | tr -cd '![a-zA-Z]\n' > INPUT $ strings AofTS.txt > temp.CHECK $ awk '' temp.CHECK > new.CHECK $ cat new.CHECK | tr -cd '![a-zA-Z]\n' > empty.CHECK $ sed '/!/d' empty.CHECK > temp.CHECK $ sed '/^\s*$/d' temp.CHECK > CHECK
Причина спрощення вмісту обох фалів полягає в тому, що в разі недостатньо обробки деякі керуючі символи можуть призводити до аварійного завершення програм, створених з використанням мови програмування C. Зважаючи на те, що метою цієї статті є демонстрація прийомів розробки та використання хеш-таблиць, я вирішив спростити вхідні дані, а не витрачати час на пошук причини аварійного завершення програми та модифікацію коду мовою C.
Після створення хеш-таблиці з даними першого файлу (з ім'ям INPUT) дані з другого файлу (з ім'ям CHECK) будуть використовуватися для тестування хеш-таблиці. Саме таким чином хеш-таблиці найчастіше використовуються на практиці.
Теоретична інформація
Дозвольте мені почати з визначення хеш-таблиці.Хеш-таблиця - це структура даних, яка містить одну або більше пар ключ-значення. Хеш-таблиця може містити ключі будь-якого типу.
Хеш-таблиця використовує хеш-функцію для обчислення індексу в рамках масиву кошиків або слотів, в якому може бути знайдено коректне значення. В ідеальному випадку хеш-функція розміщуватиме кожен ключ в окремому кошику. На жаль, таке трапляється вкрай рідко. На практиці хеш-функції працюють таким чином, що в одному кошику розміщується більше одного ключа. Найбільш важливою характеристикою хеш-таблиці є кількість кошиків. Кількість кошиків враховується хеш-функцією. Другою найбільш важливою характеристикою хеш-таблиці є хеш-функція, що використовується. Ключовим завданням хеш-функції є генерація рівномірно розподілених хеш-значень.
На основі вищесказаного ви можете зробити висновок про те, що час пошуку значення в хеш-таблиці масштабуватиметься за формулою O(n/k), де n є кількістю ключів, а k - розміром масиву хеш-таблиці. Незважаючи на те, що на перший погляд скорочення часу пошуку значень здається незначним, ви повинні розуміти, що у разі використання хеш-таблиці з масивом із 20 кошиків час пошуку значення зменшиться у 20 разів.
Важливо, щоб хеш-функція демонструвала сталість поведінки та генерувала однакові хеш-значення для ідентичних ключів. Колізія відбувається тоді, коли для двох ключів генерується те саме значення - і це не є чимось незвичайним. Існує багато способів обробки колізій.
Хорошим рішенням є використання окремих ланцюжків. Хеш-таблиця за своєю суттю є масивом із покажчиків, кожен з яких вказує на наступний ключ з тим самим хеш-значенням.У разі колізії ключ буде додано протягом короткого постійного проміжку часу на початок пов'язаного списку. знадобитися обхід всього пов'язаного списку - це головна причина, через яку пов'язаний список не повинен бути дуже великим, виходячи з чого можна зробити висновок про необхідність створення великої кількості кошик.
Як ви можете припустити, дозвіл колізій пов'язане з використанням будь-якого алгоритму лінійного пошуку; виходячи з цього, вам знадобиться хеш-функція, яка мінімізує кількість колізій настільки, наскільки це можливо. використання двох різних хеш-функцій.
- У хеш-таблиці з коректною кількістю кошиків середня ціна кожної операції пошуку значення не залежить від кількості елементів таблиці.
- Хеш-таблиці особливо ефективні у тому випадку, якщо максимальна кількість елементів може бути передбачено заздалегідь, завдяки чому фрагмент пам'яті для зберігання масиву кошиків оптимального розміру може резервуватися одноразово без подальших операцій повторного резервування.
- У тому випадку, якщо набір пар ключ-значення є фіксованим і відомим заздалегідь (відповідно, операції додавання та видалення елементів не будуть дозволені), ви можете скоротити середню ціну операції пошуку значення, вибравши коректні хеш-функцію, розмір таблиці та тип внутрішніх структур даних .
Хеш-таблиці також мають деякі недоліки:
- Вони не призначені для зберігання відсортованих даних. Використання хеш-таблиці для сортування даних не є продуктивним.
- Хеш-таблиці не ефективні в тому випадку, якщо кількість елементів дуже мала, адже, незважаючи на те, що операції з хеш-таблицями виконуються протягом у середньому рівних проміжків часу, ціна операції хешування з використанням якісної хеш-функції може бути значно вищою, ніж ціна операції пошуку на основі алгоритму пошуку у списку або дереві.
- При реалізації певних програм для обробки рядків, таких, як програми для перевірки орфографії, хеш-таблиці можуть бути менш ефективними, ніж дерева або кінцеві автомати.
- Незважаючи на те, що середня ціна операції є постійною і малою, ціна окремої операції може виявитися досить великою. Зокрема, якщо хеш-таблиця використовує механізм динамічного зміни розміру масиву, для однієї з операцій видалення або додавання ключа може знадобитися час, пропорційний кількості елементів таблиці. Ця особливість може перетворитися на серйозний недолік у додатках, які мають виводити результати без зволікання.
- Хеш-таблиці працюють досить неефективно за наявності багатьох колізій.
Як ви, напевно, зрозуміли, не кожне завдання може бути вирішене за допомогою хеш-таблиць однаково ефективно. У будь-якому випадку, ви повинні розглядати та досліджувати всі доступні структури для зберігання даних перед тим, як ухвалити рішення про те, які з них слід використовувати.
На малюнку 1 схематично зображена проста хеш-таблиця з ключами та значеннями.Як хеш-функція використовується функція обчислення залишку при розподілі на 10; виходячи з цього, знадобляться десять кошиків, так як при розподілі на 10 залишок може бути представлений лише 10 значеннями. Використання десяти кошиків не є достатньо гарною ідеєю, особливо в тому випадку, якщо таблицю буде додаватися велика кількість елементів, але для ілюстрації принципу роботи хеш-таблиці використання такої кількості кошиків цілком допустимо.
Малюнок 1. Проста хеш-таблиця
Підсумовуючи, можна сказати, що при створенні хеш-таблиці необхідно дотримуватися наступних принципів:
- Не слід створювати надто велику кількість кошиків; слід створювати рівно стільки кошиків, скільки потрібно.
- Хеш-функція повинна обробляти настільки великий обсяг інформації про ключ, наскільки це можливо. Це не таке вже тривіальне завдання.
- Хеш-функція повинна генерувати різні значення для подібних ключів.
- Кожен кошик повинен містити одну і ту ж кількість ключів або, принаймні, їх сумісні кількості (це дуже бажана властивість).
- За дотримання деяких принципів можна знизити ймовірність виникнення колізій. По-перше, кількість кошиків має бути представлена простим числом. По-друге, чим більший розмір масиву, тим менша ймовірність виникнення колізій. Нарешті, ви повинні переконатися в тому, що хеш-функція є достатньо опрацьованою для розподілу значень, що повертаються, настільки рівномірно, наскільки це можливо.
Додавання, видалення та пошук елементів
Основними операціями, що виконуються з хеш-таблицями є додавання, видалення та пошук елементів.Ви можете використовувати значення, яке генерується хеш-функцією, для встановлення того, де в рамках хеш-таблиці слід зберегти ключ. Згодом ця ж хеш-функція може використовуватися для встановлення того, де в рамках хеш-таблиці слід шукати значення ключа.
Після заповнення хеш-таблиці пошук елементів може здійснюватися за аналогією додаванням. Спочатку хеш-функція застосовується до значення ключа, після чого здійснюється перехід до заданої позиції в масиві, обхід відповідного зв'язаного списку та встановлення наявності в ньому ключа, що цікавить. Кількість кроків у цьому випадку буде постійним O(1). У найгіршому випадку час пошуку елемента в хеш-таблиці може досягати O(n) тоді, коли всі ключі зберігаються в одному кошику. Тим не менш, ймовірність такого результату настільки мала, що в загальному випадку, як в ідеальному випадку, можна вважати кількість кроків постійним O(1).
Ви можете знайти безліч реалізацій хеш-таблиць в мережі Інтернет або в книгах, присвячених темі, що розглядається. Найбільш складним аспектом використання хеш-таблиць є вибір відповідної кількості кошиків, а також вибір ефективної хеш-функції, яка розподілятиме значення настільки рівномірно, наскільки це можливо. Нерівномірний розподіл значень призведе до збільшення кількості колізій та, відповідно, до збільшення ціни їхнього розв'язання.
Реалізація мовою програмування C
Код першої реалізації хеш-таблиці буде збережено у файлі з ім'ям ht1.c. Реалізація використовує окремі ланцюжки, тому що їх наявність цілком обґрунтована. Для простоти імена двох файлів задані на рівні коду програми.Після введення даних та створення хеш-таблиці програма починає послідовне читання слів з другого файлу з перевіркою наявності кожного з цих слів у хеш-таблиці.
У Лістингу 1 показано вихідний код програми мовою C з файлу ht1.c.
Лістинг 1. ht1.c
#include #include #include #include #define TABLESIZE 5 // Пов'язаний список typedef struct node < char *data; struct node *next; >node; // Хеш-функція: значення, що повертається буде залишком від поділу різниці між // значенням першого символу рядка і значенням першого рядкового символу // таблиці ASCII на передане значення розміру таблиці.unsigned int hash (const char * str, int tablesize) < int value; // Отримання значення першого символу рядка value = toupper(str[0]) - 'A'; return value % tablesize; >static int lookup(node *table[], const char *key) < unsigned index = hash(key, TABLESIZE); const node *it=table[index]; // Спроба встановити наявність відповідного ключа у зв'язаному списку while(it != NULL && strcmp(it->data, key) != 0) < it = it->next; > return it! = NULL; > int insert(node *table[], char *key) < if( !lookup(table, key) ) < // Пошук необхідного зв'язаного списку unsigned index = hash(key, TABLESIZE); node * new_node = malloc (sizeof * new_node); if(new_node == NULL) return 0; new_node->data = malloc(strlen(key)+1); if(new_node->data == NULL) return 0; // Додавання нового ключа та оновлення покажчика початку пов'язаного списку strcpy(new_node->data, key); new_node->next=table[index]; table[index] = new_node; return 1; > return 0; > // Заповнення хеш-таблиці // Перший параметр: Змінна хеш-таблиці // Другий параметр: Структура файлу зі словами int populate_hash(node *table[], FILE *file) < char word[50]; char c; do <c = fscanf(file, "%s", word); // Важливо: слід видалити символ переходу наступного рядка size_t ln = strlen (word) - 1; if (word[ln] == '\n') word[ln] = '\0'; insert(table, word); >while (c! = EOF); return 1; > int main(int argc, char **argv) < char word[50]; char c; int found = 0; // Ініціалізація хеш-таблиці node *table[TABLESIZE] =; FILE *INPUT; INPUT = fopen("INPUT", "r"); // Заповнення хеш-таблиці populate_hash(table, INPUT); fclose(INPUT); printf("Хеш-таблиця заповнена!\n"); int line = 0; FILE * CHECK; CHECK = fopen("CHECK", "r"); do <c = fscanf(CHECK, "%s", слово); // Важливо: слід видалити символ переходу нанаступний рядок size_t ln = strlen (word) – 1; if (word[ln] == '\n') word[ln] = '\0'; line++; if(lookup(table, word)) < found++; >> while (c! = EOF); printf("У хеш-таблиці виявлено %d слів!\n", found); fclose(CHECK); return 0; >
Більш вдала реалізація хеш-таблиці мовою програмування C
Код другої реалізації хеш-таблиці буде збережено у файлі з ім'ям ht2.c. У цій реалізації також застосовуються окремі ланцюжки. Більшість коду мовою C цієї реалізації повністю ідентична коду з файлу з ім'ям ht1.c, крім коду хеш-функции. Код модифікованої хеш-функції виглядає так:
int hash (const char * str, int tablesize) < int sum = 0; // Чи є рядок коректним? if(str == NULL) < return -1; >// Обчислення суми значень всіх символів рядка for( ; *str; str++) < sum += *str; >// Повернення залишку від розподілу обчисленого значення суми на передане значення розміру таблиці return (sum % tablesize); >
Ця функція має перевагу перед функцією з минулого прикладу, яка полягає в тому, що враховуються значення всіх символів рядка, а не лише першого символу. Виходячи з цього, число, що генерується, відповідне позиції ключа в хеш-таблиці, буде більше, що передбачає можливість використання переваг хеш-таблиці з великою кількістю кошиків.
Тестування продуктивності
Представлені тести продуктивності далекі від точних та наукових тестів. Вони лише ілюструють кращі та гірші, а також коректні та некоректні параметри хеш-таблиць. Пам'ятайте, що встановити оптимальний розмір хеш-таблиці не завжди просто.
Усі програми компілюються за допомогою наступної команди:
Надійна утиліта time вивела наступну інформацію після чотириразового виконання програми ht1 з використанням чотирьох різних розмірів хеш-таблиці:
$ grep define ht1.c #define TABLESIZE 101 $ time ./ht1 Хеш-таблиця заповнена! У хеш-таблиці виявлено 59 843 слів! real 0m0.401s user 0m0.395s sys 0m0.004s $ grep define ht1.c #define TABLESIZE 10 $ time ./ht1 Хеш-таблиця заповнена! У хеш-таблиці виявлено 59 843 слів! real 0m0.794s user 0m0.788s sys 0m0.004s $ grep define ht1.c #define TABLESIZE 1001 $ time ./ht1 Хеш-таблиця заповнена! У хеш-таблиці виявлено 59 843 слів! real 0m0.410s user 0m0.404s sys 0m0.004s $ grep define ht1.c #define TABLESIZE 5 $ time ./ht1 Хеш-таблиця заповнена! У хеш-таблиці виявлено 59 843 слів! real 0m1.454s user 0m1.447s sys 0m0.004s
На малюнку 2 представлений графік часу виконання програми на основі вихідного коду з файлу ht1.c з чотирма різними значеннями константи TABLESIZE. Проблема реалізації хеш-таблиці з файлу ht1.c полягає в тому, що продуктивність хеш-таблиці з 101 кошиком практично дорівнює продуктивності хеш-таблиці з 1001 кошиком!
Рисунок 2. Час виконання програми на основі вихідного коду з файлу ht1.c під час використання чотирьох різних значень константи TABLESIZE
А це результати виконання програми на основі вихідного коду з файлу ht2.c:
$ grep define ht2.c #define TABLESIZE 19 $ time ./ht2 INPUT CHECK Хеш-таблиця заповнена! У хеш-таблиці виявлено 59 843 слів! real 0m0.439s user 0m0.434s sys 0m0.003s $ grep define ht2.c #define TABLESIZE 97 $ time ./ht2 INPUT CHECK Хеш-таблиця заповнена! У хеш-таблиці виявлено 59 843 слів! real 0m0.116s user 0m0.111s sys 0m0.003s $ grep define ht2.c #define TABLESIZE 277 $ time ./ht2 INPUT CHECK Хеш-таблиця заповнена! У хеш-таблиці виявлено 59 843 слів! real 0m0.072s user 0m0.067s sys 0m0.003s $ grep define ht2.c #define TABLESIZE 997 $ time ./ht2 INPUT CHECK Хеш-таблиця заповнена! У хеш-таблиці виявлено 59 843 слів! real 0m0.051s user 0m0.044s sys 0m0.003s $ grep define ht2.c #define TABLESIZE 22397 $ time ./ht2 INPUT CHECK Хеш-таблиця заповнена! У хеш-таблиці виявлено 59 843 слів! real 0m0.049s user 0m0.044s sys 0m0.003s
На малюнку 3 показаний графік часу виконання програми на основі вихідного коду з файлу ht2.c при використанні п'яти різних значень константи TABLESIZE. Усі значення розміру хеш-таблиці є простими числами. Причина використання простих чисел полягає в тому, що вони найкраще підходять для виконання операцій поділу із залишком. Це тим, що просте число немає позитивних дільників крім одиниці і себе. В результаті добуток простого числа та іншого цілого числа матиме менше позитивних дільників, ніж добуток не є простим числа та іншого цілого числа.
Малюнок 3. Графік часу виконання програми на основі вихідного коду з файлу ht2.c під час використання п'яти різних значень константи TABLESIZE
Як ви бачите, нова хеш-функція працює набагато продуктивніше за хеш-функцію з файлу вихідного коду ht1.c.Внаслідок використання більшої кількості кошиків значно зростає продуктивність хеш-таблиці. Тим не менш, тому що кількість слів у текстових файлах обмежена, немає сенсу використовувати кількість кошиків, що перевищує кількість унікальних слів у вхідному файлі.
Крім того, корисно дослідити розподіл ключів у реалізації хеш-таблиці з вихідного файлу коду ht2.c при використанні двох різних кількостей кошиків. Наступна функція мови програмування C виводить кількість ключів у кожному з кошиків:
void printHashTable(node *table[], const unsigned int tablesize) < node *e; int i; int length = tablesize; printf("Виведення інформації про хеш-таблиці з %d кошиками.\n", length); for(i = 0; ielse < while( e != NULL ) < n++; e = e->next; > > printf("Кошик %d містить %d ключів\n", i, n); > >
На Малюнку 4 показано кількість ключів у кожному кошику двох хеш-таблиць: з 97 кошиками та з 997 кошиками. Хеш-таблиця з 997 кошиками відповідає вимогам до рівномірного заповнення кошиків, тоді як у хеш-таблиці з 97 кошиками спостерігається ще більш рівномірний розподіл ключів. Тим не менш, у кожному з кошиків хеш-таблиць більшого розміру завжди розміщується менша кількість ключів, що передбачає розміщення меншої кількості ключів у кожному зі зв'язаних списків, яке позитивно впливає на час пошуку ключів.
Малюнок 4. Кількість ключів у кожному кошику двох хеш-таблиць з різною кількістю кошиків
Висновок
Хеш-таблиці є важливою частиною курсів комп'ютерних наук і можуть використовуватися продуктивно при розробці програмних продуктів. Я сподіваюся, що ця стаття допоможе вам оцінити їх важливість та зрозуміти особливості їх створення та використання.
Хеш-таблиці. Що це таке та як працюють
Ми продовжуємо курс щодо структур даних, і на цьому занятті йтиметься про нову структуру під назвою хеш-таблиця. Вона має воістину вражаючі характеристики. Для стандартних операцій вставки, читання та видалення даних вона, в середньому, виконується за константний час O(1), тобто, швидко та незалежно від розміру таблиці (обсягу даних):
І в цьому вона перевершує подібні до неї структури: динамічні масиви і зв'язкові списки. Виходить, що хеш-таблиця може повністю їх замінити? Але не поспішайте й у всьому докладно розберемося. Насамперед розглянемо принцип роботи хеш-таблиць.
Припустимо, у продуктовому магазині необхідно зберігати товари та видавати ціну за їх назвами.
Як це зробити? З того, що ми знаємо зараз, цілком підійшов би зв'язковий перелік, т.к. у нього досить швидко можна додавати нові товари та видаляти непотрібні. Щоправда, пошук виконуватиметься лінійний час O(n). І це нас дуже влаштовує, т.к. товарів у магазині може бути дуже багато і нам хотілося б мати швидший доступ до ціни товару за його назвою. Тому зробимо дещо інакше. Єдина з усіх розглянутих структур, що надає швидкий доступ до елемента за час O(1) – це масиви (і динамічні масиви).
Але тут на нас чекають відразу дві проблеми: по-перше, ми знаємо назви, але не індекси елементів, а значить, пошук потрібного товару займе O(n) часу, і, по-друге, операції додавання та видалення товару також вимагатимуть O(n) ) часу. Виходить досить невдалий вибір структури даних. Але не поспішайте з висновками. Давайте підемо на невелику хитрість.Придумаємо алгоритм, який би переводив назви товарів в індекси, і тоді ми отримаємо можливість відразу звертатися до потрібного осередку таблиці (масиву), щоб записати його туди, прочитати звідти, або видалити, коли це потрібно:
Так ось, алгоритм перетворення деякого рядка в індекс масиву отримав назву хеш-функція, а процес його роботи – хешування. Звідси походить назва хеш-таблиця.
- для одного і того ж ключа (назви товару) повинна видавати те саме значення (властивість послідовності);
- для різних ключів (назв товарів) видавати різні значення (індекси);
- формовані значення мають у діапазоні від 0 до N-1, де N – розмір масиву, тобто. індекси мають бути дійсними для використовуваної таблиці;
- можливі ключі (назви) повинні рівномірно записуватися до осередків таблиці.
Додавання елементів до хеш-таблиці
Давайте припустимо, що ми хотіли б за англійськими буквами отримувати відповідні аналоги російських букв. Наприклад:
Причому нам наперед невідомо, скільки саме букв зберігатиметься у хеш-таблиці. Тому, щоб даремно не витрачати пам'ять, початковий розмір таблиці матиме m=5 елементів. Самі осередки таблиці зберігатимуть адреси на об'єкти з даними. Якщо даних немає, то покажчики набувають значення NULL. Далі, у нас є хеш-функція, яка для кожної літери латинського алфавіту обчислює індекс у масиві T. Припустимо, ми хочемо за ключом b записати значення б. На вхід хеш-функції подається символ b. На виході отримуємо індекс масиву, яким цей ключ повинен розташовуватися в таблиці. Нехай це буде індекс 1: Потім у пам'яті створюється новий об'єкт з ключем b і значенням б, і адреса цього об'єкта зберігається в другому елементі таблиці.Тобто масив зберігає не самі дані, а посилання на об'єкти з даними. Це найчастіша реалізація хеш-таблиць. В результаті ми додали новий ключ b та його значення б у хеш-таблицю. На рівні мов програмування ця операція часто записується як:
Зрозуміло, якщо T – це хеш-таблиця. За аналогією можна додати ще кілька ключів та значень. Наприклад, ключі f, d, u: І наш масив майже заповнений! Теоретично хеш-таблиць ступінь їх заповненості визначається коефіцієнтом: α = n / m де n – кількість збережених ключів (у прикладі 4); m – розмір масиву (у прикладі 5). Отримуємо значення ступеня заповнення таблиці: α = 4 / 5 = 0,8 Тобто, поки цей коефіцієнт менше одиниці, в масиві є вільні елементи, куди теоретично ще можна додати нові ключі. Якщо α = 1, масив заповнений повністю. Якщо ж > 1, то число ключів перевищує розмір хеш-таблиці. (Як таке може бути, ми ще говоритимемо.) Отже, зараз коефіцієнт α = 0,8, отже, масив майже заповнений. Що робити далі? Вихід тільки один: збільшити розмір таблиці, тобто розглядати масив як динамічний і, наприклад, при близької до 1 збільшувати його розмір в 2 рази. Давайте так і зробимо. Спочатку ми повинні в пам'яті створити новий масив завдовжки в 2 рази більший за попередній. Після цього хеш-функція вже видаватиме новий діапазон індексів [0; 9]. Тому елементи повинні не просто копіюватися в новий масив, а знову проганяти через нову хеш-функцію. Отримаємо (наприклад): Тільки після цього ми сюди можемо додавати нові ключі. Ось загальний принцип роботи алгоритму додавання ключів та значень у хеш-таблиці. У середньому ця операція виконується за фіксований час O(1).
Дозвіл колізій у хеш-таблицях
T["b"] = б T["ba"] = ба T["d"] = д T["f"] = ф T["bb"] = бб T["fa"] = фа
І хеш-функція для ключів з однаковими першими літерами видає одні й самі індекси таблиці. Тоді, щоб зберегти кілька різних ключів по тому самому індексу, формується двозв'язний список, початку якого веде покажчик ptr. В елементах цього двозв'язкового списку зберігаються пари ключ-значення. Це і є принцип дозволу колізій методом ланцюжків. Таке рішення має позитивні та негативні сторони. До позитивних можна віднести простоту реалізації. Сформувати двозв'язкові списки там, де необхідно зберігати кілька ключів, не складає особливих труднощів. Також відносно швидко відбувається вставка нових ключів та видалення існуючих у таких списках (ланцюжках). А основним недоліком є можливість появи довгих ланцюжків у хеш-таблицях. Тоді пошук потрібного ключа може зайняти тривалий час і переваги хеш-таблиць будуть зведені нанівець. Очевидно, щоб уникнути такого несприятливого випадку (утворення довгих ланцюжків), потрібно правильно вибирати хеш-функцію, яка рівномірно розподіляла б можливі ключі за індексами таблиці. Добре, що існують підходи, що дозволяють створювати такі функції, але про це ми ще говоритимемо. А зараз подивимося, як у хеш-таблицях зі списками виконується пошук та видалення ключів.
Алгоритм пошуку ключів
Припустимо, що у нас є раніше сформована хеш-таблиця з ланцюжками і в ній потрібно взяти значення за певним ключем. Нехай це буде ключ "ba", тобто потрібно виконати операцію:
Для цього ми подаємо ключ «ba» на вхід хеш-функції, отримуємо значення індексу 1 таблиці і бачимо тут двозв'язковий список. На початок цього переліку веде покажчик ptr. Сформуємо часовий покажчик:
який також посилатиметься на початок цього списку. Далі, ми послідовно проходимо елементами цього списку і порівнюємо в них ключі на рівність заданого ключа «ba». Цей ключ ми знаходимо у другому елементі списку. На цьому пошук зупиняється та повертається значення "ба" цього ключа. Якщо ми вказуємо не існуючий ключ, наприклад, «t», або потрапимо в порожню комірку таблиці, або знайдемо цей ключ у списку. Ось так, досить просто реалізується алгоритм пошуку ключів у хеш-таблиці з ланцюжками.
Алгоритм видалення ключів
Давайте подивимося, як можна виконувати видалення існуючих ключів з хеш-таблиці з ланцюжками. У нас, як і раніше, буде та сама таблиця і ми хочемо видалити з неї ключ «ba»:
Спочатку також подаємо цей ключ на вхід хеш-функції та отримуємо індекс 1 у таблиці. За цим індексом зберігається кілька ключів у списку. За допомогою тимчасового покажчика p знаходимо елемент із ключем «ba». Це другий елемент. І видаляємо його. (Як видаляти елементи у двозв'язкових списках ми з вами вже говорили на попередніх заняттях). Все, ключ видалено з хеш-таблиці. Якщо відбувається видалення єдиного ключа в комірці, наприклад, ключа "d", то перевіряється, що в єдиному елементі дійсно зберігається ключ "d", якщо так, то об'єкт видаляється і комірка набуває значення NULL. Нарешті, якщо намагаємося видалити ключ, що не існує в таблиці, наприклад, «s», то або відразу потрапляємо в комірку зі значенням NULL, або на ланцюжок з ключів, в якій ключ «s» буде відсутній. У будь-якому випадку, за відсутності ключа жодних дій з таблицею не виконується і вона залишається у незмінному вигляді.
Що таке: Хеш-таблиця
Хеш-таблиця - це структура даних, що реалізує асоціативний масив.Анотація тип даних, структура, яка може зіставляти ключі зі значеннями. Він використовує хеш-функцію для обчислення індексу масиві контейнерів або слотів, з якого можна знайти бажане значення. Ефективність хеш-таблиці полягає у її здатності надавати швидкий доступ до даних, що робить її популярним вибором для реалізації словників та наборів.
Заголовок оголошення
Опис оголошення. Lorem ipsum dolor sit amet, consectetur adipiscing elit.
Як працює хеш-таблиця?
Основний механізм хеш-таблиці включає хеш-функцію, яка перетворює заданий ключ в індекс. Цей індекс визначає, де в таблиці зберігається відповідне значення масив, що лежить в основі. При додаванні пари ключ-значення хеш-функція обчислює індекс, значення зберігається в цій позиції. При вилученні значення та ж хеш-функція застосовується до ключа, що призводить до того ж індексу, що забезпечує швидкий доступ.
Пояснення хеш-функцій
Функція хешування має вирішальне значення для продуктивності хеш-таблиці. Вона повинна рівномірно розподіляти ключі масиву, щоб мінімізувати колізії, які виникають, коли два ключі хешуються в один і той же індекс. Хороша функція хешування є детермінованою, тобто вона завжди видаватиме однаковий висновок для того самого введення, і вона повинна бути ефективною для обчислень. Поширені функції хешування включають методи поділу-залишку та множення.
Методи вирішення зіткнень
Коли два ключі хешуються в той самий індекс, відбувається колізія, і хеш-таблиця повинна її обробити. Існує кілька стратегій дозволу колізій, включаючи ланцюжок та відкриту адресацію.Ланцюжок передбачає зберігання декількох елементів в одному індексі з використанням зв'язаного списку, в той час як відкрита адресація знаходить доступний наступний слот в масиві. Кожен метод має свої переваги та компроміси щодо продуктивності та використання пам'яті.
Коефіцієнт навантаження та зміна розміру
Коефіцієнт завантаження хеш-таблиці визначається як кількість записів, поділена на кількість сегментів. Високий коефіцієнт завантаження може призвести до збільшення колізій та зниження продуктивності. Для підтримки ефективності багато хеш-таблиці автоматично змінюють свій розмір, коли коефіцієнт завантаження перевищує певний поріг, зазвичай шляхом створення більшого масиву та повторного хешування існуючих записів новий масив.
Заголовок оголошення
Опис оголошення. Lorem ipsum dolor sit amet, consectetur adipiscing elit.
