挿入、検索、削除
基本操作です。
「挿入、検索、削除」はCoddyKit上の無料C Academyレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。
3つの基本操作
すべてのハッシュテーブルは、挿入、検索、削除という3つの操作をサポートします。適切なハッシュ関数と妥当な負荷率を使えば、3つとも平均 O(1) 時間で実行できます。
ここでは、連鎖法によるテーブルを順を追って構築します。
テーブルとノードの型
コピーしたキー文字列と整数値を保持するノードを定義し、さらにバケット配列とその容量を保持するテーブル構造体を定義します。
#include <stdio.h>
typedef struct Node {
char *key;
int value;
struct Node *next;
} Node;
typedef struct {
Node **buckets;
unsigned capacity;
unsigned size;
} HashTable;
int main(void) {
printf("types defined\n");
return 0;
}テーブルの作成
callocを使ってテーブルとゼロ初期化されたバケット配列を確保します。これにより、すべてのバケットが最初からNULLになります。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { char *key; int value; struct Node *next; } Node;
typedef struct { Node **buckets; unsigned capacity, size; } HashTable;
HashTable *ht_create(unsigned cap) {
HashTable *t = malloc(sizeof *t);
t->buckets = calloc(cap, sizeof(Node *));
t->capacity = cap; t->size = 0;
return t;
}
int main(void) {
HashTable *t = ht_create(16);
printf("capacity=%u size=%u\n", t->capacity, t->size);
return 0;
}ハッシュヘルパー
DJB2を再利用し、その値をバケットのインデックスに変換します。このヘルパーは3つの操作すべてで使用します。
#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;
}
unsigned bucket_of(const char *key, unsigned cap) {
return (unsigned)(djb2(key) % cap);
}
int main(void) {
printf("%u\n", bucket_of("name", 16));
return 0;
}挿入：更新または先頭への追加
挿入時は、まずバケットを検索します。キーが存在する場合は値を更新します。存在しない場合は、新しいノードを確保し（strdupでキーをコピーして）、リストの先頭に追加します。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node { char *key; int value; struct Node *next; } Node;
Node *insert(Node *head, const char *key, int val) {
for (Node *p = head; p; p = p->next)
if (strcmp(p->key, key) == 0) { p->value = val; return head; }
Node *n = malloc(sizeof *n);
n->key = strdup(key); n->value = val; n->next = head;
return n;
}
int main(void) {
Node *b = NULL;
b = insert(b, "a", 1);
b = insert(b, "a", 99); /* update */
printf("%s=%d\n", b->key, b->value);
return 0;
}検索
検索ではキーをハッシュ化し、バケットのリストをたどりながらstrcmpでキーを比較します。値へのポインターを返し、キーが存在しない場合は NULL を返します。
#include <stdio.h>
#include <string.h>
typedef struct Node { char *key; int value; struct Node *next; } Node;
int *lookup(Node *head, const char *key) {
for (Node *p = head; p; p = p->next)
if (strcmp(p->key, key) == 0) return &p->value;
return NULL;
}
int main(void) {
Node n2 = {"y", 20, NULL};
Node n1 = {"x", 10, &n2};
int *v = lookup(&n1, "y");
printf("%d\n", v ? *v : -1);
return 0;
}削除：リストをつなぎ直す
削除では、前のノードへのポインターを保持しながらバケットをたどります。その後、対象ノードを飛ばすようにリンクをつなぎ直し、コピーしたキーとノードの両方を解放します。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node { char *key; int value; struct Node *next; } Node;
Node *delete_key(Node *head, const char *key) {
Node *prev = NULL, *cur = head;
while (cur) {
if (strcmp(cur->key, key) == 0) {
if (prev) prev->next = cur->next; else head = cur->next;
free(cur->key); free(cur);
return head;
}
prev = cur; cur = cur->next;
}
return head;
}
int main(void) {
Node *b = malloc(sizeof *b);
b->key = strdup("a"); b->value = 1; b->next = NULL;
b = delete_key(b, "a");
printf("%s\n", b ? "left" : "empty");
return 0;
}全体を組み合わせる
完全なテーブルでは、バケットを計算してからリスト用ヘルパーに処理を委譲することで、これらの操作をまとめます。ここでは、小さな完全なテーブルの動作を確認します。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node { char *key; int value; 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;}
#define CAP 16
Node *table[CAP];
void put(const char *k, int v) {
unsigned i = djb2(k) % CAP;
Node *n = malloc(sizeof *n);
n->key = strdup(k); n->value = v; n->next = table[i];
table[i] = n;
}
int get(const char *k) {
for (Node *p = table[djb2(k) % CAP]; p; p = p->next)
if (!strcmp(p->key, k)) return p->value;
return -1;
}
int main(void) {
put("age", 30); put("score", 95);
printf("age=%d score=%d\n", get("age"), get("score"));
return 0;
}キーをコピーする理由
strdupを使ってキーを保存し、テーブルが独自のコピーを所有するようにします。呼び出し元のポインターをそのまま保存すると、キーが変更されたり、こちらが使っている間に解放されたりして、検索が壊れる可能性があります。
そのため、削除時にはコピーしたキーをfreeする必要もあります。
時間計算量
ハッシュが均一で、負荷率を 0.75 前後に保つ場合：
- 挿入：平均 O(1)
- 検索：平均 O(1)
- 削除：平均 O(1)
すべてのキーが1つのバケットで衝突すると、最悪の場合は O(n) になります。
テーブル全体の解放
メモリリークを防ぐには、すべてのバケット内の全ノードを解放し、次にバケット配列、最後にテーブル構造体を解放します。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node { char *key; int value; struct Node *next; } Node;
void free_bucket(Node *head) {
while (head) { Node *nx = head->next; free(head->key); free(head); head = nx; }
}
int main(void) {
Node *b = malloc(sizeof *b);
b->key = strdup("k"); b->value = 1; b->next = NULL;
free_bucket(b);
printf("freed\n");
return 0;
}確認問題
基本操作についての理解を確認しましょう。
まとめ
連鎖法を使って、ハッシュテーブルの3つの基本操作を実装しました。
- 挿入では、ノードを更新するか先頭に追加します
- 検索では、
strcmpを使ってバケットのリストをたどります - 削除では、リンクをつなぎ直し、キーとノードの両方を解放します
strdupでキーを所有し、終了時にすべてを解放します
よくある質問
「挿入、検索、削除」レッスンは無料ですか？
はい。「挿入、検索、削除」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。
「挿入、検索、削除」で何を学びますか？
基本操作です。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
C Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「挿入、検索、削除」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このC Academyレッスンでコードを書いて実行できますか？
はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。