Хеш таблиця

Хеш-таблиця(hash table) - Структура даних, що реалізує інтерфейс асоціативного масиву, дозволяє зберігати пари ключ => значення і виконувати три операції:

Головна властивість hash table - всі операції (вставка, пошук та видалення) в середньому виконуються за O(1), середній час пошуку по ній також дорівнює O(1) і O(n) у гіршому випадку.

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

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

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

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

Відкрита індексація (або закрите хешування)

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

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

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

Рехешування

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

Основні кроки рехешування в хеш-таблицях:

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

Існує кілька стратегій розв'язання:

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

• Зменшення колізій: Рехешування дозволяє більш рівномірно розподілити елементи, зменшуючи ймовірність колізій та покращуючи продуктивність.
• Динамічна зміна розміру: Таблиця може адаптуватися до навантаження, що змінюється, збільшуючи або зменшуючи свій розмір при необхідності.

• Додаткові витрати: Розв'язання може вимагати виділення пам'яті для нової таблиці та переміщення елементів, що може бути дорогим за ресурсами.
• Тимчасова складність: Процес розв'язання може зайняти час, що може уповільнити роботу структури даних на короткий термін.

Вибір стратегії розв'язання та параметрів (наприклад, розміру нової таблиці) залежить від конкретних потреб та характеристик програми.

Хеш-таблиця C/C++: повна реалізація

Хеш-таблиця C/C++ (асоціативний масив) — це структура даних, яка зіставляє ключі зі значеннями і використовує хеш-функцію для обчислення індексів ключа.

Індекс хеш-таблиці дозволяє зберегти значення у відповідному місці.

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

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

Отже, в середньому тимчасова складність є постійним часом доступу O(1) – це називається амортизаційною тимчасовою складністю.

C++ STL (стандартна бібліотека шаблонів) використовує структуру даних std::unordered_map(), яка реалізує ці функції хеш-таблиці.

Однак вміти будувати хеш-таблиці з нуля - навичка важлива і корисна, і саме цим ми займемося в даному мануалі.

Давайте розберемося докладніше у деталях реалізації таблиць. Будь-яка реалізація хеш-таблиці складається з наступних трьох компонентів:

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

Вибір хеш-функції

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

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

У цій статті ми працюватимемо лише з рядками (або масивами символів).

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

Ви можете перевірити цю функцію для різних рядків і побачити, чи виникають колізії чи ні. Наприклад, рядки Hel і Cau будуть конфліктувати, оскільки вони мають однакове значення ASCII.

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

Визначення структури даних хеш-таблиці

Хеш-таблиця - це масив елементів, які самі по собі є парою.

Тепер визначимо структуру нашого елемента.

typedef struct Ht_item Ht_item; // Define the Hash Table Item here struct Ht_item < char* key; char* value; >;

Тепер хеш-таблиця має масив покажчиків, які самі ведуть на Ht_item, тому виходить подвійний покажчик.

Крім цього, ми також відстежуватимемо кількість елементів у хеш-таблиці за допомогою count та зберігатимемо розмір таблиці в size.

typedef struct HashTable HashTable; // Define the Hash Table має структуру HashTable < // Contains an array of pointers // to items Ht_item** items; int size; int count; >;

Створення хеш-таблиці та її елементів

Щоб створити в пам'яті нову хеш-таблицю та її елементи, нам потрібні функції.

Спочатку давайте створимо елементи. Це дуже просто робиться: нам потрібно лише виділити пам'ять для ключа та значення та повернути покажчик на елемент.

Ht_item* create_item(char* key, char* value) < // Creates pointer to a new hash table item Ht_item* item = (Ht_item*) malloc (sizeof(Ht_item)); item->key = (char*) malloc (strlen(key) + 1); item->value = (char*) malloc (strlen(value) + 1); strcpy(item->key, key); strcpy(item->value, value); return item; >

Тепер напишемо код для створення таблиці. Цей код виділяє пам'ять для структури-оболонки HashTable та встановлює для всіх її елементів значення NULL (оскільки вони не використовуються).

HashTable* create_table(int size) < // Creates a new HashTable HashTable* table = (HashTable*) malloc (sizeof(HashTable)); table->size = size; table-> count = 0; table->items = (Ht_item**) calloc (table->size, sizeof(Ht_item*)); for (int i=0; isize; i++) table->items[i] = NULL; return table; >

Ми майже закінчили із цією частиною. Як програміст C/C++, ви повинні звільняти виділену пам'ять з допомогою malloc(), calloc().

Давайте напишемо функції, які звільняють елемент і всю таблицю.

void free_item(Ht_item* item) < // Frees an item free(item->key); free(item->value); free(item); > void free_table(HashTable* table) < // Frees the table for (int i=0; isize; i++) < Ht_item* item = table->items[i]; if (item! = NULL) free_item (item); > free(table->items); free(table); >

Отже, ми завершили роботу над нашою функціональною хеш-таблицею. Давайте тепер почнемо писати методи insert(), search() та delete().

Вставка в хеш-таблицю

Зараз ми створимо функцію ht_insert(), яка виконає завдання за нас.

Вона приймає в якості параметрів вказівник HashTable, ключ і значення.

void ht_insert (HashTable * table, char * key, char * value);

Далі потрібно виконати певні кроки, пов'язані з функцією вставки.

Створити елемент на основі пари.

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

Про те, як обробляти колізії, ми поговоримо трохи згодом після того, як створимо вихідну модель.

Перший крок простий. Ми безпосередньо викликаємо create_item(key, value).

int index = hash_function(key);

Другий та третій кроки для отримання індексу використовують hash_function(key). Якщо ми вставляємо ключ вперше, елемент має бути NULL. В іншому випадку або точна пара "ключ: значення" вже існує, або це колізія.

У цьому випадку ми визначаємо іншу функцію handle_collision(), яка, як випливає з назви, опрацює потенційну колізію.

// Create the item Ht_item* item = create_item(key, value); // Compute index int index = hash_function(key); Ht_item* current_item = table->items[index]; if (current_item == NULL) < // Key does not exist. if (table->count == table->size) < // Hash Table Full printf("Insert Error: Hash Table is full\n"); free_item(item); return; >// Insert directly table->items[index] = item; table->count++; >

Давайте розглянемо перший сценарій, де пара «ключ: значення» вже існує (тобто такий самий елемент вже було вставлено до таблиці раніше). У цьому випадку ми лише повинні оновити значення елемента, просто привласнити йому нове значення.

if (current_item == NULL) < . >value, value); return; > else < // Scenario 2: Collision // We will handle case this a bit later handle_collision(table, item);

Отже, функція вставки (без колізій) тепер виглядає приблизно так:

void handle_collision(HashTable* table, Ht_item* item) < >void ht_insert(HashTable* table, char* key, char* value) < // Create the item Ht_item* item = create_item(key, value); ->items[index]; if (current_item == NULL) < // Key does not exist. table->count == table->size) directly table->items[index] = item; table->count++; > else < // Scenario 1: We only need to update value if (strcmp(current_item->key, key) == 0) < strcpy(table->items[index]->value, value); case this a bit later handle_collision(table, item);

Пошук елементів у хеш-таблиці

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

char * ht_search (HastTable * table, char * key);

Логіка дуже проста. Функція просто переходить до елементів, які не є NULL, і порівнює ключ.

char* ht_search(HashTable* table, char* key) < // Searches the key in the hashtable // and returns NULL if it doesn't exist int index = hash_function(key); ]; // Ensure that we move to a non NULL item if (item != NULL) < if (strcmp(item->key, key) == 0) return item->value; > return NULL;

Тестування базової моделі

Для цього ми використовуємо програму-драйвер main().

Щоб проілюструвати, як усе працює, додамо ще одну функцію print_table(), яка виводить хеш-таблицю.

В результаті ми отримаємо:

Key:1, Value:First address Key:2, Value:Second address Key:3 не існує Hash Table ------------------- Index:49, Key:1 , Value:First address Index:50, Key:2, Value:Second address -------------------

Чудово! Здається, все працює так, як ми очікували. Тепер перейдемо до обробки колізій.

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

Існують різні способи вирішення колізії. Ми розглянемо метод під назвою "метод ланцюжків", метою якого є створення незалежних ланцюжків для всіх елементів з однаковим хеш-індексом.

Ми створимо ці ланцюжки за допомогою зв'язкових списків.

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

Оскільки зв'язкові списки мають тимчасову складність O(n) для вставки, пошуку та видалення, при виникненні колізії час доступу у найгіршому випадку також буде O(n). Цей метод добре підходить для роботи з таблицями невеликої ємності.

Давайте приступимо до реалізації пов'язаного списку.

typedef struct LinkedList LinkedList; // Define the Linkedlist here struct LinkedList < Ht_item* item; LinkedList * next; >; LinkedList* allocate_list () < // Allocates memory for Linkedlist pointer LinkedList* list = (LinkedList*) malloc (sizeof(LinkedList)); return list; >LinkedList* linkedlist_insert(LinkedList* list, Ht_item* item) < // Inserts the item on the LinkedList if (!list) < LinkedList* head = allocate_list(); head->item = item; head->next = NULL; list = head; return list; > else if (list->next == NULL) < LinkedList* node = allocate_list(); node->item = item; node->next = NULL; list-> next = node; return list; > LinkedList * temp = list; while (temp->next->next) < temp = temp->next; > LinkedList* node = allocate_list(); node->item = item; node->next = NULL; temp-> next = node; return list; Ht_item* linkedlist_remove(LinkedList* list) < // Removes the head from the linked list // and returns the element of the popped element if (!list) return NULL; if (!list->next) return NULL; LinkedList* node = list->next; LinkedList* temp = list; temp-> next = NULL; list = node; Ht_item* it = NULL; memcpy(temp->item, it, sizeof(Ht_item)); free(temp->item->key); free(temp->item->value); free(temp->item); free(temp); return it; > void free_linkedlist(LinkedList* list) < LinkedList* temp = list; while (list) < temp = list; list = list->next; free(temp->item->key); free(temp->item->value); free(temp->item); free(temp); > >

Тепер потрібно додати ці списки переповнених бакетів у хеш-таблицю.

typedef struct HashTable; // Define the Hash Table here struct HashTable; // to items Ht_item**

Тепер, коли ми визначили overflow_buckets, давайте додамо функції для їх створення та видалення. Їх також необхідно враховувати у старих функціях create_table() та free_table().

LinkedList** create_overflow_buckets(HashTable* table) < // Create the overflow buckets; 0; isize; i++) buckets[i] = NULL; void free_overflow_buckets(HashTable* table) < // Free all the overflow bucket lists LinkedList** buckets = table->overflow_buckets; > HashTable* create_table(int size) < // Creates a new HashTable HashTable* table = (HashTable*) malloc (sizeof(HashTable)); *));for (int i=0; isize; i++) table->items[i] = NULL; table->overflow_buckets = create_overflow_buckets(table); > void free_table(HashTable* table) ; if (item != NULL) free_item(item); bucket linked linkedlist and it's items free_overflow_buckets(table);

Тепер перейдемо до функції handle_collision().

Тут є два сценарії Якщо список елемента не існує, нам потрібно створити такий список і додати до нього елемент.

В іншому випадку ми можемо просто вставити елемент у список.

void handle_collision(HashTable* table, unsigned long index, Ht_item* item) < LinkedList* head = table->overflow_buckets[index]; if (head == NULL) < // We need to create the list head = allocate_list(); head->item = item; table->overflow_buckets[index] = head; return; > else < // Insert to the list table->overflow_buckets[index] = linkedlist_insert(head, item); return; > >

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

char* ht_search(HashTable* table, char* key) < // Searches the key in the hashtable // and returns NULL if it doesn't exist int index = hash_function(key); Ht_item* item = table->items[index]; LinkedList* head = table->overflow_buckets[index]; // Ensure that we move to items which not NULL while (item != NULL) < if (strcmp(item->key, key) == 0) return item->value; if (head == NULL) return NULL; item = head->item; head = head->next; > return NULL;

Отже, ми врахували колізії у функціях insert() та search(). На даний момент наш код виглядає так:

Видалення з хеш-таблиці
Давайте подивимося на функцію видалення даних із таблиці:

void ht_delete (HashTable * table, char * key);

Ця функція працює аналогічно до вставки. Нам потрібно:

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

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

Надаємо вам робочу версію для порівняння.

void ht_delete(HashTable* table, char* key) < // Deletes an item from the table int index = hash_function(key); Ht_item* item = table->items[index]; LinkedList* head = table->overflow_buckets[index]; if (item == NULL) < // Does not exist. Return return; >else < if (head == NULL && strcmp(item->key, key) == 0) < // No collision chain. Remove the item // and set table index to NULL table->items[index] = NULL; free_item(item); table->count--; return; > else if (head != NULL) < // Collision Chain exists if (strcmp(item->key, key) == 0) < // Remove this item and set head of the list // as the new item free_item (Item); LinkedList * node = head; head = head->next; node->next = NULL; table->items[index] = create_item(node->item->key, node->item->value); free_linkedlist(node); table->overflow_buckets[index] = head; return; > LinkedList * curr = head; LinkedList* prev = NULL; while (curr) < if (strcmp(curr->item->key, key) == 0) < if (prev == NULL) < // First element of the chain. Remove the chain free_linkedlist(head); table->overflow_buckets[index] = NULL; return; > else < / / This is somewhere in the chain prev->next = curr->next; curr->next = NULL; free_linkedlist(curr); table->overflow_buckets[index] = head; return; > > curr = curr->next; prev = curr; > > > >

Повний код
Нарешті ми можемо подивитися на повний код програми хеш-таблиці.

#include #include #include #define CAPACITY 50000 // Розмір шахівного столу незначний long hash_function(char* str) < unsigned long i = 0; for (int j = 0; str [j]; j ++) i + = str [j]; return i % CAPACITY; >typedef struct Ht_item Ht_item; // Define the Hash Table Item here struct Ht_item < char* key; char* value; >; typedef struct LinkedList LinkedList; // Define the Linkedlist here struct LinkedList < Ht_item* item; LinkedList * next; >; typedef struct HashTable HashTable; // Define the Hash Table має структуру HashTable < // Contains an array of pointers // to items Ht_item** items; LinkedList** overflow_buckets; int size; int count; >; static LinkedList* allocate_list () < // Allocates memory for Linkedlist pointer LinkedList* list = (LinkedList*) malloc (sizeof(LinkedList)); return list; >static LinkedList* linkedlist_insert(LinkedList* list, Ht_item* item) < // Inserts the item on the LinkedList if (!list) < LinkedList* head = allocate_list(); head->item = item; head->next = NULL; list = head; return list; > else if (list->next == NULL) < LinkedList* node = allocate_list(); node->item = item; node->next = NULL; list-> next = node; return list; > LinkedList * temp = list; while (temp->next->next) < temp = temp->next; > LinkedList* node = allocate_list(); node->item = item; node->next = NULL; temp-> next = node; return list; > static Ht_item* linkedlist_remove(LinkedList* list) < // Removes the head from the linked list // and returns the element of the popped element if (!list) return NULL; if (!list->next) return NULL; LinkedList* node = list->next; LinkedList* temp = list; temp-> next = NULL; list = node; Ht_item* it = NULL; memcpy(temp->item, it, sizeof(Ht_item)); free(temp->item->key); free(temp->item->value); free(temp->item); free(temp); return it; > static void free_linkedlist(LinkedList* list) < LinkedList* temp = list; while (list) < temp = list; list = list->next; free(temp->item->key); free(temp->item->value); free(temp->item); free(temp); > > staticLinkedList** create_overflow_buckets(HashTable* table) < // Create the overflow buckets; array of linkedlists LinkedList** buckets = (LinkedList**) calloc (table->size, sizeof(LinkedList*)); for (int i=0; isize; i++) buckets[i] = NULL; return buckets; > static void free_overflow_buckets(HashTable* table) < // Free all the overflow bucket lists LinkedList** buckets = table->overflow_buckets; for (int i=0; isize; i++) free_linkedlist(buckets[i]); free(buckets); > Ht_item* create_item(char* key, char* value) < // Creates pointer to a new hash table item Ht_item* item = (Ht_item*) malloc (sizeof(Ht_item)); item->key = (char*) malloc (strlen(key) + 1); item->value = (char*) malloc (strlen(value) + 1); strcpy(item->key, key); strcpy(item->value, value); return item; > HashTable* create_table(int size) < // Creates a new HashTable HashTable* table = (HashTable*) malloc (sizeof(HashTable)); table->size = size; table-> count = 0; table->items = (Ht_item**) calloc (table->size, sizeof(Ht_item*)); for (int i=0; isize; i++) table->items[i] = NULL; table->overflow_buckets = create_overflow_buckets(table); return table; > void free_item(Ht_item* item) < // Frees an item free(item->key); free(item->value); free(item); > void free_table(HashTable* table) < // Frees the table for (int i=0; isize; i++) < Ht_item* item = table->items[i]; if (item! = NULL) free_item (item); > free_overflow_buckets(table); free(table->items); free(table); > void handle_collision(HashTable* table, unsigned long index, Ht_item* item) < LinkedList* head = table->overflow_buckets[index]; if (head == NULL) < // We need to create the list head = allocate_list(); head->item = item; table->overflow_buckets[index] = head; return; > else < // Insert to the list table->overflow_buckets[index] = linkedlist_insert(head, item); return; > > void ht_insert(HashTable* table, char* key, char* value) < // Create the item Ht_item* item = create_item(key, value); // Compute the index unsigned long index =hash_function(key); Ht_item* current_item=table->items[index]; if (current_item == NULL) < // Key does not exist. Full printf("Insert Error: Hash Table is full\n"); // Remove the create item free_item(item); return; key) == 0) strcpy(table->items[index]->value, value); return; > else < // Scenario 2: Collision handle_collision(table, index, item); NULL if it doesn't exist int index = hash_function(key); table->items[index]; LinkedList* head = table->overflow_buckets[index]; ) == 0) return item->value; return NULL; item = head->item; head = head->next; > return NULL; Ht_item* item = table->items[index]; table->overflow_buckets[index]; if (item == NULL) < // Does not exist. / No collision chain.Remove the item // and set table index to NULL table->items[index] = NULL; if (strcmp(item->key, key) == 0) < // Remove this item and set the head of the list // as the new item free_item(item); LinkedList* node = head; ->item->value); free_linkedlist(node); return; > LinkedList* curr = head; LinkedList* prev = NULL; element of the chain.Remove the chain free_linkedlist(head); table->overflow_buckets[index] = NULL; return; > else < / / This is somewhere in the chain prev->next = curr->next; curr->next = NULL; free_linkedlist(curr); table->overflow_buckets[index] = head; return; > > curr = curr->next; prev = curr; > > > > void print_search(HashTable* table, char* key) < char* val; if ((val = ht_search(table, key)) == NULL) < printf("%s does not exist\n", key); return; >else < printf("Key:%s, Value:%s\n", key, val); >> void print_table(HashTable* table) < printf("\n-----------------------n"); for (int i=0; isize; i++) < if (table->items[i]) < printf("Index:%d, Key:%s, Value:%s", i, table->items[i ]->key, table->items[i]->value); if (table->overflow_buckets[i]) < printf(" =>Overflow Bucket => "); LinkedList* head = table->overflow_buckets[i]; while (head) < printf("Key:%s, Value:%s ", head->item->key, head->item->value); head = head->next; > > printf("\n"); > > printf("-------------------\n"); > int main() < HashTable* ht = create_table(CAPACITY); ht_insert(ht, "1", "First address"); ht_insert(ht, "2", "Second address"); ht_insert(ht, "Hel", "Third address"); ht_insert(ht, "Cau", "Fourth address"); print_search(ht, "1"); print_search(ht, "2"); print_search(ht, "3"); print_search(ht, "Hel"); print_search(ht, "Cau"); // Collision! print_table(ht); ht_delete(ht, "1"); ht_delete(ht, "Cau"); print_table(ht); free_table(ht); return 0; >Результат виглядає так: Key:1, Value:First address Key:2, Value:Second address 3 не існує Key:Hel, Value:Third address Key:Cau, Value:Fourth address --------- ---------- Index:49, Key:1, Value:First address Index:50, Key:2, Value:Second address Index:281, Key:Hel, Value:Third address => Overflow Bucket => Key:Cau, Value:Fourth address ---------------- --- ------------------- Index:50, Key:2, Value:Second address Index:281, Key:Hel, Value:Third address -------------------

Висновок

Сподіваємося, ви зрозуміли, як можна продати хеш-таблицю з нуля на C/C++.Можливо, вам вдалося реалізувати її самостійно.

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

Завантажити код, який ми розглянули у цьому посібнику, можна на Github Gist.