Поиск по сайту:

Как реализовать образец хеш-таблицы на C/C++

Введение

Хэш-таблица в C/C++ — это структура данных, которая сопоставляет ключи со значениями. Хеш-таблица использует хэш-функцию для вычисления индексов для ключа. Вы можете сохранить значение в соответствующем месте на основе индекса хеш-таблицы.

Преимущество использования хэш-таблицы заключается в очень быстром времени доступа. Как правило, временная сложность (амортизированная временная сложность) представляет собой постоянное O(1) время доступа.

Если два разных ключа получают один и тот же индекс, вам нужно будет использовать другие структуры данных (сегменты) для учета этих коллизий. Если вы выберете очень хорошую хэш-функцию, вероятность коллизии может быть незначительной.

C++ STL (Стандартная библиотека шаблонов) имеет структуру данных std::unordered_map().

В этой статье вы создадите хеш-таблицу с нуля, состоящую из:

  • Хеш-функция для сопоставления ключей со значениями.
  • Структура данных хэш-таблицы, поддерживающая операции insert, search и delete.
  • Структура данных для учета конфликта ключей.

Выбор хеш-функции

Первый шаг — выбрать достаточно хорошую хеш-функцию с низкой вероятностью коллизий. Однако для целей этого руководства будет применена плохая хэш-функция, чтобы лучше проиллюстрировать коллизии хэшей. В этом ограниченном примере также будут использоваться только строки (или массивы символов в C).

#define CAPACITY 50000 // Size of the HashTable.

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.

Этот код должен возвращать число в пределах емкости хеш-таблицы. В противном случае он может получить доступ к несвязанной ячейке памяти, что приведет к ошибке.

Определение структур данных хеш-таблицы

Хэш-таблица — это массив элементов, представляющих собой пары { ключ: значение .

Во-первых, определите структуру элемента:

// Defines the HashTable item.

typedef struct Ht_item
{
    char* key;
    char* value;
} Ht_item;

Теперь в хеш-таблице есть массив указателей, указывающих на Ht_item, так что это двойной указатель.

// Defines the HashTable.
typedef struct HashTable
{
    // Contains an array of pointers to items.
    Ht_item** items;
    int size;
    int count;
} HashTable;

Ваша хеш-таблица должна будет возвращать количество элементов в хеш-таблице с помощью count и размер хэш-таблицы с помощью size.

Создание хеш-таблицы и элементов хеш-таблицы

Далее создайте функции для выделения памяти и создания элементов.

Создайте элементы, выделив память для ключа и значения, и верните указатель на элемент:

Ht_item* create_item(char* key, char* value)
{
    // Creates a pointer to a new HashTable 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;
}

Создайте таблицу, выделив память и установив size, count и items:

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;
}

В предыдущем примере выделяется память для структуры-оболочки HashTable и присваивается всем элементам значение NULL.

Освобождение памяти — лучшая практика 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);
}

Добавьте print_table() для отображения index, key и value для каждого элемента:

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");
}

На этом основная функциональность вашей пользовательской хеш-таблицы заканчивается. Теперь вы будете писать функции вставки, поиска и удаления.

Вставка в хэш-таблицу

Создайте функцию ht_insert(), которая выполняет вставки.

Функция принимает указатель HashTable, key и value в качестве параметров:

void ht_insert(HashTable* table, char* key, char* value)
{
    ...
}

Теперь есть определенные шаги, связанные с функцией ht_insert().

  • Создайте элемент на основе пары { key: value .
  • Вычислить индекс на основе хеш-функции.
  • Проверьте, занят ли уже индекс, сравнив key.
    • Если он не занят, вы можете напрямую вставить его в index.
    • В противном случае это коллизия, и вам нужно будет с ней справиться.

    В этом руководстве рассматривается обработка коллизий после создания исходной модели.

    Сначала создайте элемент:

    create_item(key, value)

    Затем вычислите индекс:

    int index = hash_function(key);

    При вставке ключа в первый раз элемент должен быть NULL:

    // Creates the item.
Ht_item* item = create_item(key, value);

// Computes 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)
    {
        // HashTable is full.
        printf("Insert Error: Hash Table is full\n");
        free_item(item);
        return;
    }

    // Insert directly.
    table->items[index] = item;
    table->count++;
}

    Рассмотрим сценарий, в котором пара { key: value уже существует, поскольку тот же самый элемент был вставлен в хеш-таблицу. Чтобы решить эту проблему, код должен обновить значение элемента до нового:

    if (current_item == NULL)
{
    ...
}
else {
    // Scenario 1: Update the value.
    if (strcmp(current_item->key, key) == 0)
    {
        strcpy(table->items[index] -> value, value);
        return;
    }
}

    Рассмотрим сценарий, в котором необходимо обработать коллизию. Для решения этой проблемы был добавлен заполнитель:

    void handle_collision(HashTable* table, Ht_item* item)
{
}

void ht_insert(HashTable* table, char* key, char* value)
{
    ...

    if (current_item == NULL)
    {
        ...
    }
    else {
        // Scenario 1: Update the value.
        if (strcmp(current_item->key, key) == 0)
        {
            ...
        }
        else {
            // Scenario 2: Handle the collision.
            handle_collision(table, item);
            return;
        }
    }
}

    Теперь ваша функция ht_insert() завершена.

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

    Создайте функцию ht_search(), которая проверяет, существует ли ключ, и возвращает соответствующее значение, если оно существует.

    Функция принимает указатель HashTable и key в качестве параметров:

    char* ht_search(HashTable* table, char* key)
{
    ...
}

    Найдите элемент с ключом в HashTable. Если элемент не может быть найден в HashTable, возвращается NULL.

    char* ht_search(HashTable* table, char* key)
{
    // Searches for the key in the HashTable.
    // Returns NULL if it doesn't exist.
    int index = hash_function(key);
    Ht_item* item = table->items[index];

    // Provide only non-NULL values.
    if (item != NULL)
    {
        if (strcmp(item->key, key) == 0)
            return item->value;
    }

    return NULL;
}

    Добавьте print_search() для отображения элемента, соответствующего ключу:

    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);
    }
}

    Теперь ваша функция ht_search() завершена.

    Обработка столкновений

    Существуют различные способы разрешения коллизии. В этом руководстве будет использоваться метод под названием «Разделение цепочки», целью которого является создание независимых цепочек для всех элементов с одинаковым хэш-индексом. Реализация в этом руководстве создаст эти цепочки с использованием связанных списков.

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

    Из-за того, что связанные списки имеют O(n) временную сложность для вставки, поиска и удаления, в случае коллизии у вас будет время доступа в худшем случае O(n) тоже. Преимущество этого метода в том, что это хороший выбор, если ваша хеш-таблица имеет небольшую емкость.

    Реализуйте список переполнения:

    // Defines the LinkedList.
typedef struct LinkedList {
    Ht_item* item;
    struct LinkedList* next;
} LinkedList;;

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 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 LinkedList.
    // 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);
    }
}

    Теперь добавьте эти дополнительные списки сегментов в свою HashTable. У каждого элемента будет цепочка, поэтому вся таблица представляет собой массив указателей LinkedList.

    typedef struct HashTable HashTable;

// Defines the HashTable.
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 lists and its 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)
    {
        // Creates 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)
{
    ...

    if (current_item == NULL)
    {
        ...
    }
    else {
        // Scenario 1: Update the value.
        if (strcmp(current_item->key, key) == 0)
        {
            ...
        }
        else {
            // Scenario 2: Handle the collision.
            handle_collision(table, index, item);
            return;
        }
    }
}

    Теперь обновите метод поиска, чтобы использовать сегменты переполнения:

    char* ht_search(HashTable* table, char* key)
{
    // Searches for the key in the HashTable.
    // Returns NULL if it doesn't exist.
    int index = hash_function(key);
    Ht_item* item = table->items[index];
    LinkedList* head = table->overflow_buckets[index];

    // Provide only non-NULL values.
    if (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;
    }
    else {
        if (head == NULL && strcmp(item->key, key) == 0)
        {
            // Collision chain does not exist.
            // Remove the item.
            // 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.
                // 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 <stdio.h>
#include <stdlib.h>
#include <string.h>

#define CAPACITY 50000 // Size of the HashTable.

unsigned long hash_function(char *str)
{
    unsigned long i = 0;

    for (int j = 0; str[j]; j++)
        i += str[j];

    return i % CAPACITY;
}

// Defines the HashTable item.
typedef struct Ht_item
{
    char *key;
    char *value;
} Ht_item;

// Defines the LinkedList.
typedef struct LinkedList
{
    Ht_item *item;
    LinkedList *next;
} LinkedList;

// Defines the HashTable.
typedef struct HashTable
{
    // Contains an array of pointers to items.
    Ht_item **items;
    LinkedList **overflow_buckets;
    int size;
    int count;
} HashTable;

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 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 LinkedList.
    // 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 **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);
}

Ht_item *create_item(char *key, char *value)
{
    // Creates a pointer to a new HashTable 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;

    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; i < table->size; i++)
    {
        Ht_item *item = table->items[i];

        if (item != NULL)
            free_item(item);
    }

    // Free the overflow bucket lists and its items.
    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)
    {
        // Creates 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)
{
    // Creates the item.
    Ht_item *item = create_item(key, value);

    // Computes 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)
        {
            // HashTable is full.
            printf("Insert Error: Hash Table is full\n");
            free_item(item);
            return;
        }

        // Insert directly.
        table->items[index] = item;
        table->count++;
    }
    else
    {
        // Scenario 1: Update the value.
        if (strcmp(current_item->key, key) == 0)
        {
            strcpy(table->items[index]->value, value);
            return;
        }
        else
        {
            // Scenario 2: Handle the collision.
            handle_collision(table, index, item);
            return;
        }
    }
}

char *ht_search(HashTable *table, char *key)
{
    // Searches for the key in the HashTable.
    // Returns NULL if it doesn't exist.
    int index = hash_function(key);
    Ht_item *item = table->items[index];
    LinkedList *head = table->overflow_buckets[index];

    // Provide only non-NULL values.
    if (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;
    }
    else
    {
        if (head == NULL && strcmp(item->key, key) == 0)
        {
            // Collision chain does not exist.
            // Remove the item.
            // 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.
                // 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("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, (char *)"1", (char *)"First address");
    ht_insert(ht, (char *)"2", (char *)"Second address");
    ht_insert(ht, (char *)"Hel", (char *)"Third address");
    ht_insert(ht, (char *)"Cau", (char *)"Fourth address");
    print_search(ht, (char *)"1");
    print_search(ht, (char *)"2");
    print_search(ht, (char *)"3");
    print_search(ht, (char *)"Hel");
    print_search(ht, (char *)"Cau"); // Collision!
    print_table(ht);
    ht_delete(ht, (char *)"1");
    ht_delete(ht, (char *)"Cau");
    print_table(ht);
    free_table(ht);
    return 0;
}

    Этот код выдаст следующий результат:

    Output
    Key:1, Value:First address
Key:2, Value:Second address
Key:3 does not exist
Key:Hel, Value:Third address
Key:Cau does not exist

Hash Table
-------------------
Index:49, Key:1, Value:First address
Index:50, Key:2, Value:Second address
Index:281, Key:Hel, Value:Third address
-------------------


Hash Table
-------------------
Index:50, Key:2, Value:Second address
Index:281, Key:Hel, Value:Third address
-------------------

    ht_insert(), ht_search() и ht_delete ведут себя так, как ожидалось.

    Заключение

    В этой статье вы реализовали хеш-таблицу с нуля на C/C++.

    Поэкспериментируйте с другими алгоритмами обработки столкновений и другими хеш-функциями. Продолжите свое обучение с помощью дополнительных руководств по C++