リサイズと負荷率
パフォーマンスを調整します。
「リサイズと負荷率」はCoddyKit上の無料C Academyレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これは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;
}サイズ変更のタイミング
挿入するたびに、負荷率がしきい値を超えていないか確認します。超えていたら、テーブルを拡張し（通常は容量を2倍にして）、再ハッシュします。
#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;
}拡張戦略
容量を2倍にすると、挿入の償却計算量を O(1) に保てます。サイズ変更自体は O(n) ですが、十分にまれにしか発生しないため、挿入1回あたりの平均コストは一定に保たれます。
容量を2のべき乗にすると、高速な 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.75 より低い0.5～0.7でサイズ変更します。
償却コストのデモ
負荷率 0.75 で容量を2倍にしながら挿入をシミュレートし、合計作業量を数えて、平均コストが低く保たれることを確認します。
#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;
}確認問題
サイズ変更についての理解を確認しましょう。
まとめ
ハッシュテーブルの性能を調整する方法を学びました。
- 負荷率 = size / capacity
- しきい値を超えたらサイズを変更します（連鎖法では約 0.75）
- インデックスが容量に依存するため、再ハッシュします
- 容量を2倍にすると、挿入の償却計算量は O(1) になります
よくある質問
「リサイズと負荷率」レッスンは無料ですか？
はい。「リサイズと負荷率」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。
「リサイズと負荷率」で何を学びますか？
パフォーマンスを調整します。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
C Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「リサイズと負荷率」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このC Academyレッスンでコードを書いて実行できますか？
はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。