Хеш-таблица в C/C++: полная реализация
Development | Комментировать запись
Хеш-таблица в C/C++ (ассоциативный массив) — это структура данных, которая сопоставляет ключи со значениями и использует хеш-функцию для вычисления индексов ключа.
Индекс хеш-таблицы позволяет нам сохранить значение в соответствующем месте.
Если два разных ключа получают один и тот же индекс, для учета подобных коллизий мы должны использовать другие структуры данных (сегменты).
Главное преимущество использования хеш-таблицы – очень короткое время доступа. Конфликты иногда могут возникать, но шансы практически равны нулю, если выбрать очень хорошую хэш-функцию.
Итак, в среднем временная сложность представляет собой постоянное время доступа O(1) – это называется амортизационной временной сложностью.
C++ STL (стандартная библиотека шаблонов) использует структуру данных std::unordered_map(), которая реализует все эти функции хэш-таблицы.
Однако уметь строить хеш-таблицы с нуля – навык важный и полезный, и именно этим мы займемся в данном мануале.
Давайте разберемся подробнее в деталях реализации таблиц. Любая реализация хеш-таблицы состоит из следующих трех компонентов:
- Хорошая хеш-функция для сопоставления ключей со значениями.
- Структура данных хеш-таблицы, поддерживающая операции вставки, поиска и удаления.
- Структура данных для учета конфликтов ключей
Выбор хэш-функции
Первый шаг — выбрать достаточно хорошую хеш-функцию с низкой вероятностью возникновения коллизии.
Но для иллюстрации в этом мануале мы сделаем все наоборот – выберем плохую функцию и посмотрим, что получится.
В этой статье мы будем работать только со строками (или массивами символов).
Мы будем использовать очень простую хеш-функцию, которая просто суммирует значения ASCII строки. Эта функция позволит нам продемонстрировать, как обрабатывать коллизии.
#define CAPACITY 50000 // Size of the Hash Table unsigned long hash_function(char* str) { unsigned long i = 0; for (int j=0; str[j]; j++) i += str[j]; return i % CAPACITY; }
Вы можете проверить эту функцию для разных строк и увидеть, возникают коллизии или нет. Например, строки «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 here struct HashTable { // Contains an array of pointers // to items Ht_item** items; int size; int count; };
Создание хеш-таблицы и ее элементов
Чтобы создать в памяти новую хеш-таблицу и ее элементы, нам нужны функции.
Сначала давайте создадим элементы. Это очень просто делается: нам нужно лишь выделить память для ключа и значения и вернуть указатель на элемент.
Ht_item* create_item(char* key, char* value) { // Creates a 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; i<table->size; 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; i<table->size; 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);
Далее нужно выполнить определенные шаги, связанные с функцией вставки.
Создать элемент на основе пары {ключ : значение}.
- Вычислить индекс на основе хеш-функции
- Путем сравнения ключа проверить, занят ли данный индекс или еще нет.
- Если он не занят, мы можем напрямую вставить его в index
- В противном случае возникает коллизия, и нам нужно ее обработать
О том, как обрабатывать коллизии, мы поговорим немного позже, после того, как создадим исходную модель.
Первый шаг прост. Мы напрямую вызываем 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 the 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) { .... .... }else { // Scenario 1: We only need to update value if (strcmp(current_item->key, key) == 0) { strcpy(table->items[index]->value, value); return; } else { // Scenario 2: Collision // We will handle case this a bit later handle_collision(table, item); return; } }
Итак, функция вставки (без коллизий) теперь выглядит примерно так:
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); 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"); return; } // Insert 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); return; } else { // Scenario 2: Collision // We will handle case this a bit later handle_collision(table, item); return; } } }
Поиск элементов в хеш-таблице
Если мы хотим проверить правильность вставки, мы должны определить функцию поиска, которая проверяет, существует ключ или нет, и возвращает соответствующее значение, если он существует.
char* ht_search(HastTable* table, char* key);
Логика очень проста. Функция просто переходит к элементам, котороые не являются NULL, и сравнивает ключ. В противном случае она вернет 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); Ht_item* item = table->items[index]; // 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(), которая выводит хеш-таблицу.
#include <stdio.h> #include <stdlib.h> #include <string.h> #define CAPACITY 50000 // Size of the Hash Table unsigned 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 HashTable HashTable; // Define the Hash Table here struct HashTable { // Contains an array of pointers // to items Ht_item** items; int size; int count; }; Ht_item* create_item(char* key, char* value) { // Creates a 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; i<table->size; i++) table->items[i] = NULL; 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; i<table->size; i++) { Ht_item* item = table->items[i]; if (item != NULL) free_item(item); } free(table->items); free(table); } void handle_collision(HashTable* table, unsigned long index, Ht_item* item) { } 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. if (table->count == table->size) { // Hash Table Full printf("Insert Error: Hash Table is full\n"); // Remove the create item free_item(item); return; } // Insert 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); return; } else { // Scenario 2: Collision // We will handle case this a bit later handle_collision(table, index, 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]; // Ensure that we move to a non NULL item if (item != NULL) { if (strcmp(item->key, key) == 0) return item->value; } return NULL; } void print_search(HashTable* table, char* key) { char* val; if ((val = ht_search(table, key)) == NULL) { printf("Key:%s does not exist\n", key); return; } else { printf("Key:%s, Value:%s\n", key, val); } } void print_table(HashTable* table) { printf("\nHash Table\n-------------------\n"); for (int i=0; i<table->size; i++) { if (table->items[i]) { printf("Index:%d, Key:%s, Value:%s\n", i, table->items[i]->key, table->items[i]->value); } } printf("-------------------\n\n"); } int main() { HashTable* ht = create_table(CAPACITY); ht_insert(ht, "1", "First address"); ht_insert(ht, "2", "Second address"); print_search(ht, "1"); print_search(ht, "2"); print_search(ht, "3"); print_table(ht); free_table(ht); return 0; }
В результате мы получим:
Key:1, Value:First address Key:2, Value:Second address Key:3 does not exist 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 a Linkedlist pointer LinkedList* list = (LinkedList*) malloc (sizeof(LinkedList)); return list; } LinkedList* linkedlist_insert(LinkedList* list, Ht_item* item) { // Inserts the item onto the Linked List 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 item 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); } }
Теперь нужно добавить эти списки переполненных бакетов в хеш-таблицу. У каждого элемента должна быть одна такая цепочка, поэтому для всей таблицы мы добавим массив указателей LinkedList.
typedef struct HashTable HashTable; // Define the Hash Table here struct HashTable { // Contains an array of pointers // to items Ht_item** items; LinkedList** overflow_buckets; int size; int count; };
Теперь, когда мы определили overflow_buckets, давайте добавим функции для их создания и удаления. Их также необходимо учитывать в старых функциях create_table() и free_table().
LinkedList** create_overflow_buckets(HashTable* table) { // Create the overflow buckets; an array of linkedlists LinkedList** buckets = (LinkedList**) calloc (table->size, sizeof(LinkedList*)); for (int i=0; i<table->size; i++) buckets[i] = NULL; return buckets; } void free_overflow_buckets(HashTable* table) { // Free all the overflow bucket lists LinkedList** buckets = table->overflow_buckets; for (int i=0; i<table->size; i++) free_linkedlist(buckets[i]); free(buckets); } 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; i<table->size; i++) table->items[i] = NULL; table->overflow_buckets = create_overflow_buckets(table); return table; } void free_table(HashTable* table) { // Frees the table for (int i=0; i<table->size; i++) { Ht_item* item = table->items[i]; if (item != NULL) free_item(item); } // Free the overflow bucket linked linkedlist and it's items free_overflow_buckets(table); free(table->items); free(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 are 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(). На данный момент наш код выглядит так:
#include #include #include #define CAPACITY 50000 // Size of the Hash Table unsigned 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 here struct 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 a Linkedlist pointer LinkedList* list = (LinkedList*) malloc (sizeof(LinkedList)); return list; } static LinkedList* linkedlist_insert(LinkedList* list, Ht_item* item) { // Inserts the item onto the Linked List 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 item 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); } } static LinkedList** create_overflow_buckets(HashTable* table) { // Create the overflow buckets; an 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 a 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. if (table->count == table->size) { // Hash Table Full printf("Insert Error: Hash Table is full\n"); // Remove the create item free_item(item); return; } // Insert 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); return; } else { // Scenario 2: Collision handle_collision(table, index, 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 are 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; } 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"); print_table(ht); free_table(ht); return 0; }
Удаление из хеш-таблицы
Давайте взглянем на функцию удаления данных из таблицы:
void ht_delete(HashTable* table, char* key);
Эта функция работает аналогично вставке. Нам нужно:
- Вычислить хеш-индекс и получить элемент.
- Если это NULL, нам ничего не нужно делать
- В противном случае, если для этого индекса нет цепочки коллизий, после сравнения ключей нужно просто удалить элемент из таблицы.
- Если цепочка коллизий существует, мы должны удалить этот элемент и соответствующим образом сдвинуть данные.
Мы не будем перечислять здесь слишком много подробностей, так как эта процедура включает только обновление элементов заголовка и освобождение памяти. Предлагаем вам попытаться реализовать это самостоятельно.
Предоставляем вам рабочую версию для сравнения.
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 the 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 // Size of the Hash Table unsigned 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 here struct 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 a Linkedlist pointer LinkedList* list = (LinkedList*) malloc (sizeof(LinkedList)); return list; } static LinkedList* linkedlist_insert(LinkedList* list, Ht_item* item) { // Inserts the item onto the Linked List 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 item 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); } } static LinkedList** create_overflow_buckets(HashTable* table) { // Create the overflow buckets; an 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 a 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. if (table->count == table->size) { // Hash Table Full printf("Insert Error: Hash Table is full\n"); // Remove the create item free_item(item); return; } // Insert 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); return; } else { // Scenario 2: Collision handle_collision(table, index, 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 are 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; } 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 the 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; } } } } 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 does not exist 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.
Читайте также: Сравнение строк в C++: три основных метода
Tags: C++