Zmiana rozmiaru i współczynnik zapełnienia
Dostrajanie wydajności
Zmiana rozmiaru i współczynnik zapełnienia to bezpłatna lekcja C Academy na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej C Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs C Academy zawiera 4 lekcji w sumie.
Czym jest współczynnik zapełnienia
Współczynnik zapełnienia to stosunek liczby przechowywanych wpisów do liczby kubełków: alpha = size / capacity. Mierzy stopień zapełnienia tablicy i bezpośrednio wpływa na wydajność.
Dlaczego współczynnik zapełnienia ma znaczenie
Wraz ze wzrostem współczynnika zapełnienia kubełki zawierają dłuższe łańcuchy (lub sondowania są bardziej zgrupowane), więc operacje zwalniają.
- Niskie alpha: szybko, ale kosztem zmarnowanej pamięci
- Wysokie alpha: oszczędnie pod względem pamięci, ale wolno
Typową wartością docelową dla łańcuchowania jest 0.75.
Obliczanie współczynnika zapełnienia
Oblicz go jako stosunek zmiennoprzecinkowy, aby móc porównać go z wartością progową.
#include <stdio.h>
int main(void) {
unsigned size = 12, capacity = 16;
double alpha = (double)size / capacity;
printf("load factor = %.2f\n", alpha);
return 0;
}Kiedy zmieniać rozmiar
Po każdym wstawieniu sprawdź, czy współczynnik zapełnienia przekracza wartość progową. Jeśli tak, powiększ tablicę (zwykle podwajając jej pojemność) i ponownie oblicz skróty.
#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;
}Wyjaśnienie ponownego haszowania
Nie można bezpośrednio skopiować kubełków, ponieważ indeks każdego klucza zależy od pojemności tablicy. Ponowne haszowanie oblicza kubełek każdego klucza względem nowej pojemności i ponownie go wstawia.
Funkcja zmiany rozmiaru
Alokujemy nową, większą tablicę kubełków; przechodzimy przez każdy stary węzeł i przenosimy go do nowej tablicy, korzystając z nowej pojemności; następnie zamieniamy tablice. Oto kluczowy fragment ponownego obliczania indeksu.
#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;
}Przenoszenie węzłów bez ponownej alokacji
W przypadku łańcuchowania można przenieść istniejące węzły do nowej tablicy zamiast alokować nowe. Odłącz każdy węzeł, oblicz ponownie jego kubełek i dodaj go na początku listy.
#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;
}Strategia zwiększania rozmiaru
Podwajanie pojemności utrzymuje zamortyzowany koszt wstawiania na poziomie O(1): chociaż zmiana rozmiaru ma złożoność O(n), występuje na tyle rzadko, że średni koszt pojedynczego wstawienia pozostaje stały.
Potęgi dwójki pozwalają również używać szybkiej maski 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;
}Zmniejszanie rozmiaru
Opcjonalnie zmniejsz tablicę, gdy współczynnik zapełnienia spadnie zbyt nisko (na przykład poniżej 0.1) po wielu usunięciach. Zmniejszanie odzyskuje pamięć, ale wiąże się z kosztem ponownego haszowania, dlatego należy stosować je ostrożnie, aby uniknąć ciągłych zmian rozmiaru.
Adresowanie otwarte a współczynnik zapełnienia
Tablice z adresowaniem otwartym są znacznie bardziej wrażliwe na współczynnik zapełnienia. Wydajność gwałtownie spada, gdy alpha zbliża się do 1, dlatego zwykle zmieniają rozmiar przy wartości od 0.5 do 0.7, niższej niż 0.75 stosowane w łańcuchowaniu.
Przykład kosztu zamortyzowanego
Symulujemy wstawienia, które przy współczynniku 0.75 podwajają pojemność, i zliczamy całkowity nakład pracy, pokazując, że średnia pozostaje niska.
#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;
}Szybkie sprawdzenie
Sprawdź swoje rozumienie zmiany rozmiaru.
Podsumowanie
Nauczyłeś(-aś) się dostrajać wydajność tablic haszujących.
- Współczynnik zapełnienia = rozmiar / pojemność
- Zmieniaj rozmiar po przekroczeniu wartości progowej (około 0.75 w przypadku łańcuchowania)
- Wykonuj ponowne haszowanie, ponieważ indeksy zależą od pojemności
- Podwajanie zapewnia zamortyzowany koszt wstawiania O(1)
Ucz się C dzięki korepetycjom AI — za darmo
Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.
- Kursy
- 39
- Lekcje
- 144
Często zadawane pytania
Czy lekcja „Zmiana rozmiaru i współczynnik zapełnienia” jest bezpłatna?
Tak — pełny tekst „Zmiana rozmiaru i współczynnik zapełnienia” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu C Academy, przejdź na CoddyKit PRO. Kurs C Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Zmiana rozmiaru i współczynnik zapełnienia”?
Dostrajanie wydajności Ćwiczysz C Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć C Academy?
Nie wymagamy żadnego doświadczenia. C Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Zmiana rozmiaru i współczynnik zapełnienia”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji C Academy?
Tak. Każda lekcja C Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Funkcje haszujące
- Obsługa kolizji
- Wstawianie, wyszukiwanie i usuwanie
- Zmiana rozmiaru i współczynnik zapełnienia