Информация Быстрый поиск по хеш-таблицы в Си

[X-Shar]

Всем привет!

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

Вот встаёт всегда вопрос обработки таких данных, если вы можете работать с такими штуками как питон или C#, то там как правило уже есть готовые библиотеки, такие как dict, например в питоне, или в C# Dictionary по моему называется, достаточно ознакомится с документацией и применять в своей задаче.

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

Но всё-же предлагаю в этой статье попробовать самим написать оптимизированный поиск по хеш-таблицам.

Итак начнем:

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

Основная идея в том, что по какому-то хешу сразу получить адрес элемента массива, исключив перебор по всему массиву.

Принципы работы хеш-таблицы​

1. Хеш-функция​

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

Пример: для строки "example" функция может вернуть хеш 12345, который затем преобразуется в индекс через операцию:

Скопировать в буфер обмена

index=hash%table_size

2. Разрешение коллизий​

Если два ключа дают один и тот же индекс, возникает коллизия. Хеш-таблицы используют методы её разрешения:

• Линейное пробирование: ищем следующую свободную ячейку.
• Цепочки: каждый индекс таблицы указывает на список всех элементов с этим хешем.
• Двойное хеширование: используется дополнительная хеш-функция для поиска следующей позиции.

---

Как создать хеш-таблицу​

Рассмотрим создание хеш-таблицы с методами:

• Вставка
• Поиск
• Удаление

Универсальный код хеш-таблицы:
Обратите внимание на алгоритм быстрого подсчета хеша - Хеш-функция (FNV-1a).

Скопировать в буфер обмена

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 101  // Размер таблицы (лучше использовать простое число, уменьшает вероятность коллизии)

// Структура для элемента хеш-таблицы
typedef struct HashNode {
    char* key;
    char* value;
    struct HashNode* next;  // Для разрешения коллизий через цепочки
} HashNode;

// Хеш-таблица
typedef struct HashTable {
    HashNode** table;
    size_t size;
} HashTable;

// Хеш-функция (FNV-1a)
unsigned int hash_function(const char* key) {
    unsigned int hash = 2166136261u;
    while (*key) {
        hash ^= (unsigned char)(*key++);
        hash *= 16777619u;
    }
    return hash;
}

// Создание новой хеш-таблицы
HashTable* create_table(size_t size) {
    HashTable* hash_table = malloc(sizeof(HashTable));
    if (!hash_table) {
        perror("Failed to allocate hash table");
        return NULL;
    }
    hash_table->table = calloc(size, sizeof(HashNode*));
    if (!hash_table->table) {
        perror("Failed to allocate table entries");
        free(hash_table);
        return NULL;
    }
    hash_table->size = size;
    return hash_table;
}

// Создание нового узла
HashNode* create_node(const char* key, const char* value) {
    HashNode* node = malloc(sizeof(HashNode));
    if (!node) {
        perror("Failed to allocate node");
        return NULL;
    }
    node->key = strdup(key);
    node->value = strdup(value);
    node->next = NULL;
    return node;
}

// Вставка в хеш-таблицу
void insert(HashTable* hash_table, const char* key, const char* value) {
    unsigned int index = hash_function(key) % hash_table->size;
    HashNode* node = hash_table->table[index];

    // Проверяем, есть ли уже ключ
    while (node) {
        if (strcmp(node->key, key) == 0) {
            free(node->value);
            node->value = strdup(value);
            return;
        }
        node = node->next;
    }

    // Новый узел
    node = create_node(key, value);
    node->next = hash_table->table[index];
    hash_table->table[index] = node;
}

// Поиск в хеш-таблице
char* search(HashTable* hash_table, const char* key) {
    unsigned int index = hash_function(key) % hash_table->size;
    HashNode* node = hash_table->table[index];

    while (node) {
        if (strcmp(node->key, key) == 0) {
            return node->value;
        }
        node = node->next;
    }
    return NULL;  // Не найдено
}

// Удаление из хеш-таблицы
void delete(HashTable* hash_table, const char* key) {
    unsigned int index = hash_function(key) % hash_table->size;
    HashNode* node = hash_table->table[index];
    HashNode* prev = NULL;

    while (node) {
        if (strcmp(node->key, key) == 0) {
            if (prev) {
                prev->next = node->next;
            } else {
                hash_table->table[index] = node->next;
            }
            free(node->key);
            free(node->value);
            free(node);
            return;
        }
        prev = node;
        node = node->next;
    }
}

// Освобождение памяти
void free_table(HashTable* hash_table) {
    for (size_t i = 0; i < hash_table->size; i++) {
        HashNode* node = hash_table->table[i];
        while (node) {
            HashNode* temp = node;
            node = node->next;
            free(temp->key);
            free(temp->value);
            free(temp);
        }
    }
    free(hash_table->table);
    free(hash_table);
}

Пример использования:

Скопировать в буфер обмена

int main() {
    HashTable* hash_table = create_table(TABLE_SIZE);

    // Вставка
    insert(hash_table, "name", "Alice");
    insert(hash_table, "age", "25");
    insert(hash_table, "city", "New York");

    // Поиск
    printf("Name: %s\n", search(hash_table, "name")); // Alice
    printf("Age: %s\n", search(hash_table, "age"));   // 25
    printf("City: %s\n", search(hash_table, "city")); // New York

    // Удаление
    delete(hash_table, "age");
    printf("Age after deletion: %s\n", search(hash_table, "age")); // NULL

    // Освобождение памяти
    free_table(hash_table);
    return 0;
}