衝突処理
チェイニングとプロービングです。
「衝突処理」はCoddyKit上の無料C Academyレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。
衝突の問題
衝突とは、異なる2つのキーが同じバケットにハッシュされることです。衝突は避けられないため、すべてのハッシュテーブルには、1つのスロットに複数のキーを格納する戦略が必要です。
主な方式には、チェイン法とオープンアドレス法の2種類があります。
分離連鎖法
分離連鎖法では、各バケットがエントリの連結リストを保持します。衝突が発生したら、そのバケットのリストの末尾（または先頭）に追加するだけです。
- バケットにはリストの先頭を格納します
- 検索では短いリストを1つたどります
連鎖法のノード構造
各ノードには、キー、値、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;
}ダブルハッシュ法
ダブルハッシュ法では、2つ目のハッシュ値をステップ幅に使います。式は (h1 + i*h2) % capacity です。これにより、キーごとに異なるプローブ系列が生成され、3つの方式の中で最も分布がよくなります。
#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;
}確認問題
衝突処理についての知識を確認しましょう。
まとめ
ハッシュテーブルで衝突を解決する方法を学びました。
- 連鎖法では、バケットごとに連結リストを保持します
- オープンアドレス法では、空きスロットをプローブします
- プロービングには、線形、二次、ダブルハッシュの方式があります
- オープンアドレス法で削除するには墓石が必要です
よくある質問
「衝突処理」レッスンは無料ですか？
はい。「衝突処理」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。
「衝突処理」で何を学びますか？
チェイニングとプロービングです。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
C Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「衝突処理」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このC Academyレッスンでコードを書いて実行できますか？
はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。