0Pricing
C Academy · Урок

Вставка, поиск и удаление

Основные операции

«Вставка, поиск и удаление» — бесплатный урок C Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения C Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс C Academy содержит 4 уроков всего.

Три основные операции

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

Мы шаг за шагом создадим таблицу на основе метода цепочек.

Типы таблицы и узла

Мы определяем узел, содержащий скопированную строку ключа и целочисленное значение, а также структуру таблицы с массивом корзин и их количеством.

#include <stdio.h>

typedef struct Node {
    char *key;
    int value;
    struct Node *next;
} Node;

typedef struct {
    Node **buckets;
    unsigned capacity;
    unsigned size;
} HashTable;

int main(void) {
    printf("types defined\n");
    return 0;
}

Создание таблицы

Выделите память под таблицу и обнулённый массив корзин с помощью calloc, чтобы каждая корзина изначально содержала NULL.

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

typedef struct Node { char *key; int value; struct Node *next; } Node;
typedef struct { Node **buckets; unsigned capacity, size; } HashTable;

HashTable *ht_create(unsigned cap) {
    HashTable *t = malloc(sizeof *t);
    t->buckets = calloc(cap, sizeof(Node *));
    t->capacity = cap; t->size = 0;
    return t;
}

int main(void) {
    HashTable *t = ht_create(16);
    printf("capacity=%u size=%u\n", t->capacity, t->size);
    return 0;
}

Вспомогательная хеш-функция

Мы повторно используем DJB2 и преобразуем результат в индекс корзины. Эта вспомогательная функция используется всеми тремя операциями.

#include <stdio.h>

unsigned long djb2(const char *s) {
    unsigned long h = 5381; int c;
    while ((c = (unsigned char)*s++)) h = ((h << 5) + h) + c;
    return h;
}

unsigned bucket_of(const char *key, unsigned cap) {
    return (unsigned)(djb2(key) % cap);
}

int main(void) {
    printf("%u\n", bucket_of("name", 16));
    return 0;
}

Вставка: обновление или добавление в начало

При вставке сначала выполните поиск в корзине. Если ключ существует, обновите его значение. В противном случае выделите новый узел со скопированным ключом с помощью strdup и добавьте его в начало списка.

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

typedef struct Node { char *key; int value; struct Node *next; } Node;

Node *insert(Node *head, const char *key, int val) {
    for (Node *p = head; p; p = p->next)
        if (strcmp(p->key, key) == 0) { p->value = val; return head; }
    Node *n = malloc(sizeof *n);
    n->key = strdup(key); n->value = val; n->next = head;
    return n;
}

int main(void) {
    Node *b = NULL;
    b = insert(b, "a", 1);
    b = insert(b, "a", 99); /* update */
    printf("%s=%d\n", b->key, b->value);
    return 0;
}

Поиск

Операция поиска хеширует ключ, а затем просматривает список корзины, сравнивая ключи с помощью strcmp. Она возвращает указатель на значение или NULL, если ключ не найден.

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

typedef struct Node { char *key; int value; struct Node *next; } Node;

int *lookup(Node *head, const char *key) {
    for (Node *p = head; p; p = p->next)
        if (strcmp(p->key, key) == 0) return &p->value;
    return NULL;
}

int main(void) {
    Node n2 = {"y", 20, NULL};
    Node n1 = {"x", 10, &n2};
    int *v = lookup(&n1, "y");
    printf("%d\n", v ? *v : -1);
    return 0;
}

Удаление: перестроение связей списка

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

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

typedef struct Node { char *key; int value; struct Node *next; } Node;

Node *delete_key(Node *head, const char *key) {
    Node *prev = NULL, *cur = head;
    while (cur) {
        if (strcmp(cur->key, key) == 0) {
            if (prev) prev->next = cur->next; else head = cur->next;
            free(cur->key); free(cur);
            return head;
        }
        prev = cur; cur = cur->next;
    }
    return head;
}

int main(void) {
    Node *b = malloc(sizeof *b);
    b->key = strdup("a"); b->value = 1; b->next = NULL;
    b = delete_key(b, "a");
    printf("%s\n", b ? "left" : "empty");
    return 0;
}

Собираем всё вместе

Полная таблица объединяет эти операции: вычисляет корзину, а затем передаёт управление вспомогательным функциям для работы со списком. Здесь показана полностью работающая небольшая таблица.

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

typedef struct Node { char *key; int value; struct Node *next; } Node;

unsigned long djb2(const char *s){unsigned long h=5381;int c;while((c=(unsigned char)*s++))h=((h<<5)+h)+c;return h;}

#define CAP 16
Node *table[CAP];

void put(const char *k, int v) {
    unsigned i = djb2(k) % CAP;
    Node *n = malloc(sizeof *n);
    n->key = strdup(k); n->value = v; n->next = table[i];
    table[i] = n;
}
int get(const char *k) {
    for (Node *p = table[djb2(k) % CAP]; p; p = p->next)
        if (!strcmp(p->key, k)) return p->value;
    return -1;
}

int main(void) {
    put("age", 30); put("score", 95);
    printf("age=%d score=%d\n", get("age"), get("score"));
    return 0;
}

Зачем копировать ключ

Мы храним ключи с помощью strdup, чтобы таблица владела собственными копиями. Если бы мы хранили указатель, переданный вызывающим кодом, ключ мог бы измениться или быть освобождён, что привело бы к повреждению результатов поиска.

Это также означает, что при удалении необходимо вызвать free для скопированного ключа.

Временная сложность

При равномерном хешировании и степени заполнения около 0,75:

  • Вставка: в среднем O(1)
  • Поиск: в среднем O(1)
  • Удаление: в среднем O(1)

В худшем случае сложность составляет O(n), когда все ключи попадают в одну корзину.

Освобождение всей таблицы

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

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

typedef struct Node { char *key; int value; struct Node *next; } Node;

void free_bucket(Node *head) {
    while (head) { Node *nx = head->next; free(head->key); free(head); head = nx; }
}

int main(void) {
    Node *b = malloc(sizeof *b);
    b->key = strdup("k"); b->value = 1; b->next = NULL;
    free_bucket(b);
    printf("freed\n");
    return 0;
}

Быстрая проверка

Проверьте своё понимание основных операций.

Итоги

Вы реализовали три основные операции хеш-таблицы с использованием метода цепочек.

  • Вставка обновляет узел или добавляет его в начало списка
  • Поиск просматривает список корзины с помощью strcmp
  • Удаление перестраивает связи и освобождает ключ и узел
  • Используйте собственные копии ключей с strdup и освобождайте всё при уничтожении таблицы

Часто задаваемые вопросы

Урок «Вставка, поиск и удаление» бесплатный?

Да — полный текст урока «Вставка, поиск и удаление» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C Academy, подпишись на CoddyKit PRO. Курс C Academy содержит 4 уроков всего.

Чему я научусь в уроке «Вставка, поиск и удаление»?

Основные операции Ты практикуешь C Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать C Academy?

Предыдущий опыт не требуется. C Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Сколько времени занимает урок «Вставка, поиск и удаление»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке C Academy?

Да. Каждый урок C Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Хеш-функции
  2. Обработка коллизий
  3. Вставка, поиск и удаление
  4. Изменение размера и коэффициент загрузки
← Назад к C Academy