Изменение размера и коэффициент загрузки
Настройка производительности
«Изменение размера и коэффициент загрузки» — бесплатный урок C Academy на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения C Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс C Academy содержит 4 уроков всего.
Что такое степень заполнения
Степень заполнения — это отношение количества сохранённых элементов к количеству корзин: alpha = size / capacity. Она показывает, насколько заполнена таблица, и напрямую влияет на производительность.
Почему важна степень заполнения
По мере роста степени заполнения в корзинах образуются более длинные цепочки или кластеры проверок, поэтому операции замедляются.
- Низкое значение alpha: высокая скорость, но больше расход памяти
- Высокое значение alpha: компактность, но низкая скорость
Для метода цепочек часто выбирают целевое значение 0,75.
Вычисление степени заполнения
Вычисляйте её как отношение чисел с плавающей точкой, чтобы сравнивать результат с пороговым значением.
#include <stdio.h>
int main(void) {
unsigned size = 12, capacity = 16;
double alpha = (double)size / capacity;
printf("load factor = %.2f\n", alpha);
return 0;
}Когда изменять размер
После каждой вставки проверяйте, превышает ли степень заполнения пороговое значение. Если да, увеличьте размер таблицы, обычно вдвое, и выполните рехеширование.
#include <stdio.h>
int should_grow(unsigned size, unsigned cap) {
return (double)size / cap > 0.75;
}
int main(void) {
printf("%d\n", should_grow(13, 16)); /* 0.8125 -> 1 */
printf("%d\n", should_grow(10, 16)); /* 0.625 -> 0 */
return 0;
}Как работает рехеширование
Нельзя просто скопировать корзины, поскольку индекс каждого ключа зависит от размера таблицы. При рехешировании заново вычисляется корзина каждого ключа с учётом нового размера, после чего ключ повторно вставляется.
Функция изменения размера
Выделите новый массив корзин большего размера, просмотрите все старые узлы и переместите их в новый массив с учётом нового размера, затем замените массивы. Здесь показан основной пересчёт индекса.
#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;}
int main(void) {
const char *key = "session";
unsigned old_cap = 8, new_cap = 16;
printf("old slot = %lu\n", djb2(key) % old_cap);
printf("new slot = %lu\n", djb2(key) % new_cap);
return 0;
}Перемещение узлов без повторного выделения памяти
При использовании метода цепочек можно переместить существующие узлы в новый массив вместо создания новых. Отсоедините каждый узел, заново вычислите его корзину и добавьте его в начало списка.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node { char *key; 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;}
int main(void) {
Node *old[2] = {0};
Node *a = malloc(sizeof *a); a->key = strdup("x"); a->next = NULL; old[0] = a;
Node *new_b[4] = {0};
/* move node a */
unsigned i = djb2(a->key) % 4;
a->next = new_b[i]; new_b[i] = a;
printf("moved to slot %u\n", i);
return 0;
}Стратегия увеличения
Удвоение размера сохраняет амортизированную стоимость вставки O(1): хотя изменение размера выполняется за O(n), оно происходит достаточно редко, поэтому средняя стоимость одной вставки остаётся постоянной.
Степени двойки также позволяют использовать быструю маску AND.
#include <stdio.h>
int main(void) {
unsigned cap = 8;
for (int i = 0; i < 4; i++) {
printf("capacity = %u\n", cap);
cap *= 2;
}
return 0;
}Уменьшение размера
При желании уменьшайте размер таблицы, когда степень заполнения становится слишком низкой, например опускается ниже 0,1 после большого количества удалений. Уменьшение освобождает память, но требует дополнительных затрат на рехеширование, поэтому выполняйте его осторожно, чтобы избежать постоянных изменений размера.
Открытая адресация и степень заполнения
Таблицы с открытой адресацией гораздо чувствительнее к степени заполнения. При приближении alpha к 1 производительность резко падает, поэтому размер таких таблиц обычно изменяют при значениях от 0,5 до 0,7, то есть раньше, чем при значении 0,75 для метода цепочек.
Демонстрация амортизированной стоимости
Смоделируйте вставки, при которых размер таблицы удваивается при заполнении 0,75, и подсчитайте общий объём работы, показывая, что средняя стоимость остаётся низкой.
#include <stdio.h>
int main(void) {
unsigned cap = 4, size = 0;
long work = 0;
for (int i = 0; i < 100; i++) {
size++; work++; /* the insert */
if ((double)size / cap > 0.75) { work += size; cap *= 2; } /* rehash */
}
printf("inserts=%u total_work=%ld avg=%.2f\n", size, work, (double)work/size);
return 0;
}Быстрая проверка
Проверьте своё понимание изменения размера.
Итоги
Вы научились настраивать производительность хеш-таблиц.
- Степень заполнения = размер / вместимость
- Изменяйте размер, когда степень заполнения превышает пороговое значение, около 0,75 для метода цепочек
- Выполняйте рехеширование, поскольку индексы зависят от размера таблицы
- Удвоение размера даёт амортизированную стоимость вставок O(1)
Часто задаваемые вопросы
Урок «Изменение размера и коэффициент загрузки» бесплатный?
Да — полный текст урока «Изменение размера и коэффициент загрузки» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C Academy, подпишись на CoddyKit PRO. Курс C Academy содержит 4 уроков всего.
Чему я научусь в уроке «Изменение размера и коэффициент загрузки»?
Настройка производительности Ты практикуешь C Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать C Academy?
Предыдущий опыт не требуется. C Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Изменение размера и коэффициент загрузки»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке C Academy?
Да. Каждый урок C Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Хеш-функции
- Обработка коллизий
- Вставка, поиск и удаление
- Изменение размера и коэффициент загрузки