Обработка коллизий
Цепочки и пробирование
«Обработка коллизий» — бесплатный урок C Academy на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения C Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс C Academy содержит 4 уроков всего.
Проблема коллизий
Коллизия возникает, когда два различных ключа хешируются в одну и ту же корзину. Поскольку коллизии неизбежны, каждой хеш-таблице нужна стратегия хранения нескольких ключей в одной позиции.
Два основных семейства методов — метод цепочек и открытая адресация.
Метод цепочек
При использовании метода цепочек в каждой корзине хранится связный список элементов. При коллизии Вы просто добавляете новый элемент в начало или конец списка этой корзины.
- В корзинах хранятся указатели на первые элементы списков
- При поиске просматривается один короткий список
Структура узла цепочки
Каждый узел хранит ключ, значение и указатель next. Таблица представляет собой массив указателей на узлы.
#include <stdio.h>
typedef struct Node {
char *key;
int value;
struct Node *next;
} Node;
int main(void) {
Node *buckets[8] = {0};
printf("slots = %zu\n", sizeof buckets / sizeof buckets[0]);
return 0;
}Вставка методом цепочек
Добавление элемента в начало списка корзины выполняется за O(1). Здесь мы вручную создаём небольшую цепочку и выводим её.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int key; struct Node *next; } Node;
Node *prepend(Node *head, int key) {
Node *n = malloc(sizeof *n);
n->key = key; n->next = head;
return n;
}
int main(void) {
Node *bucket = NULL;
bucket = prepend(bucket, 10);
bucket = prepend(bucket, 26); /* same bucket as 10 mod 8 */
for (Node *p = bucket; p; p = p->next)
printf("%d ", p->key);
printf("\n");
return 0;
}Открытая адресация
При использовании открытой адресации каждый элемент хранится непосредственно в массиве корзин. При коллизии Вы просматриваете другие ячейки в поиске свободной, используя фиксированную последовательность.
Дополнительные узлы не выделяются, что эффективно с точки зрения кэширования.
Линейное пробирование
Линейное пробирование проверяет следующую ячейку, затем ещё одну и так далее, переходя в начало после конца массива: (h + i) % capacity.
Этот метод прост и эффективен с точки зрения кэширования, но страдает от кластеризации.
#include <stdio.h>
int main(void) {
int slots[8] = {0,0,1,0,0,0,0,0}; /* slot 2 taken */
unsigned h = 2, cap = 8;
for (unsigned i = 0; i < cap; i++) {
unsigned idx = (h + i) % cap;
if (!slots[idx]) { printf("insert at %u\n", idx); break; }
}
return 0;
}Квадратичное пробирование
Квадратичное пробирование использует (h + i*i) % capacity, чтобы распределить проверки и уменьшить первичную кластеризацию.
#include <stdio.h>
int main(void) {
unsigned h = 3, cap = 8;
for (unsigned i = 0; i < 4; i++)
printf("probe %u -> slot %u\n", i, (h + i*i) % cap);
return 0;
}Двойное хеширование
Двойное хеширование использует вторую хеш-функцию для определения шага: (h1 + i*h2) % capacity. Благодаря этому для каждого ключа формируется собственная последовательность проверок и достигается лучшее из трёх методов распределение.
#include <stdio.h>
int main(void) {
unsigned h1 = 3, h2 = 5, cap = 8;
for (unsigned i = 0; i < 4; i++)
printf("probe %u -> slot %u\n", i, (h1 + i*h2) % cap);
return 0;
}Удаление при открытой адресации
При открытой адресации нельзя просто очистить ячейку, поскольку это нарушит цепочки проверок для других ключей. Вместо этого пометьте её как удалённую, чтобы поиск продолжал проверять ячейки после неё.
Метод цепочек и открытая адресация
Компромиссы:
- Метод цепочек: хорошо работает при высокой степени заполнения, поддерживает простое удаление, но использует указатели и выделение памяти
- Открытая адресация: эффективна с точки зрения кэширования и не требует выделения памяти для каждого элемента, но резко теряет производительность при заполнении таблицы и требует пометок удалённых ячеек
Демонстрация количества проверок
При линейном пробировании может потребоваться несколько шагов, если ячейки образуют кластеры. Здесь мы подсчитываем количество проверок до нахождения свободной ячейки.
#include <stdio.h>
int main(void) {
int slots[8] = {1,1,1,0,0,0,0,0};
unsigned h = 0, cap = 8, probes = 0;
for (unsigned i = 0; i < cap; i++) {
probes++;
if (!slots[(h + i) % cap]) break;
}
printf("probes used = %u\n", probes);
return 0;
}Быстрая проверка
Проверьте свои знания об обработке коллизий.
Итоги
Вы изучили способы разрешения коллизий в хеш-таблицах.
- Метод цепочек хранит связный список для каждой корзины
- Открытая адресация выполняет поиск свободной ячейки
- Варианты пробирования: линейное, квадратичное и двойное хеширование
- При открытой адресации для удаления нужны пометки удалённых ячеек
Изучай C с ИИ-репетитором — бесплатно
Пиши и запускай код прямо в браузере, получай мгновенную помощь от ИИ-репетитора 24/7 и продолжи учиться на сайте или в приложении.
- Курсы
- 39
- Уроки
- 144
Часто задаваемые вопросы
Урок «Обработка коллизий» бесплатный?
Да — полный текст урока «Обработка коллизий» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C Academy, подпишись на CoddyKit PRO. Курс C Academy содержит 4 уроков всего.
Чему я научусь в уроке «Обработка коллизий»?
Цепочки и пробирование Ты практикуешь C Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать C Academy?
Предыдущий опыт не требуется. C Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «Обработка коллизий»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке C Academy?
Да. Каждый урок C Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.