ハッシュ関数
キーをバケットに割り当てます。
「ハッシュ関数」はCoddyKit上の無料C Academyレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。
ハッシュ関数とは
ハッシュ関数はキーを受け取り、バケット配列の整数インデックスを生成します。ハッシュテーブルの中心となる仕組みで、文字列のような任意のキーを高速な配列位置に変換します。
- 入力：キー（文字列、整数など）
- 出力：
[0, capacity)の範囲のバケットインデックス
良いハッシュの性質
良いハッシュ関数は、決定的で、高速であり、キーをバケット全体に均一に分散させます。
- 同じキーからは常に同じインデックスが得られる
- キーが少し変わるだけでインデックスが大きく変化する（アバランチ効果）
- 一般的なデータでは衝突が少ない
バケットに割り当てる
生のハッシュ値を計算したら、剰余演算子を使ってテーブル内の位置に変換します。index = hash % capacity
剰余が負のインデックスを生成しないよう、unsigned型を使います。
#include <stdio.h>
int main(void) {
unsigned long hash = 123456789UL;
unsigned capacity = 16;
unsigned index = (unsigned)(hash % capacity);
printf("bucket = %u\n", index);
return 0;
}単純な加算ハッシュ
最も単純な文字列ハッシュは、文字の値を合計します。簡単ですが、アナグラムが衝突するため、分散性能は低くなります。
実行して、異なる2つの文字列が近い値にハッシュされる様子を確認しましょう。
#include <stdio.h>
unsigned long sum_hash(const char *s) {
unsigned long h = 0;
while (*s) h += (unsigned char)*s++;
return h;
}
int main(void) {
printf("%lu\n", sum_hash("abc"));
printf("%lu\n", sum_hash("cba"));
return 0;
}DJB2ハッシュ
DJB2は、Daniel J. Bernsteinによる古典的で分散性能の高い文字列ハッシュです。5381から始め、hash * 33 + cを使います。
乗算と加算による混合は、単純な合計よりもビットをはるかによく分散させます。
#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; /* h * 33 + c */
return h;
}
int main(void) {
printf("%lu\n", djb2("hello"));
printf("%lu\n", djb2("world"));
return 0;
}FNV-1aハッシュ
FNV-1aは各バイトにXORを適用してから、素数を掛けます。単純で高速なため、広く使われています。
順序は、まずXORを適用し、その後に乗算します。これが1aバリアントです。
#include <stdio.h>
unsigned long fnv1a(const char *s) {
unsigned long h = 1469598103934665603UL;
while (*s) {
h ^= (unsigned char)*s++;
h *= 1099511628211UL;
}
return h;
}
int main(void) {
printf("%lu\n", fnv1a("key1"));
printf("%lu\n", fnv1a("key2"));
return 0;
}整数をハッシュする
整数キーにも混合処理が必要です。x % capacityだけでは、キーに共通するパターンがあると偏りが生じるためです。乗法による混合（Knuth法）でビットを分散させます。
#include <stdio.h>
unsigned hash_int(unsigned x, unsigned cap) {
x *= 2654435761u; /* Knuth multiplicative */
return x % cap;
}
int main(void) {
for (unsigned i = 0; i < 5; i++)
printf("%u -> %u\n", i, hash_int(i, 8));
return 0;
}2のべき乗の容量
容量が2のべき乗の場合、% capacityを高速なビットANDであるhash & (capacity - 1)に置き換えられます。
2のべき乗から1を引いた値の下位ビットが、完全なビットマスクを形成するためにのみ、この方法が機能します。
#include <stdio.h>
int main(void) {
unsigned long hash = 123456789UL;
unsigned capacity = 16; /* power of two */
unsigned index = (unsigned)(hash & (capacity - 1));
printf("bucket = %u\n", index);
return 0;
}剰余が遅くなる理由
%演算子は除算命令にコンパイルされるため、ANDより低速です。タイトなループでは、この違いが重要になります。
- 容量が2のべき乗のテーブル：ANDマスクを使う
- 素数サイズのテーブル：剰余を使う（弱いハッシュでも分散が良くなる）
衝突は避けられない
鳩の巣原理により、多数のキーをより少ないバケットに割り当てると、必ず衝突が発生します。良いハッシュは衝突を最小限にできますが、なくすことはできません。
次のレッスンでは、衝突を解決する方法を扱います。
分布のデモ
DJB2がいくつかのキーを8個のバケットにどのように分散させるかを数えてみましょう。良いハッシュは、キーをほぼ均等に分散させます。
#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 *keys[] = {"apple", "banana", "cherry", "date"};
int counts[8] = {0};
for (int i = 0; i < 4; i++)
counts[djb2(keys[i]) % 8]++;
for (int i = 0; i < 8; i++)
printf("bucket %d: %d\n", i, counts[i]);
return 0;
}クイックチェック
ハッシュ関数の基本についての理解度を確認しましょう。
まとめ
ハッシュ関数の役割と、キーをバケットに割り当てる方法を学びました。
- 良いハッシュは決定的で、高速かつ均一です
- DJB2とFNV-1aは、優れた文字列ハッシュです
% capacityで割り当てます。容量が2のべき乗の場合は& (capacity-1)も使えます- 符号なし型を使います。衝突は避けられません
よくある質問
「ハッシュ関数」レッスンは無料ですか？
はい。「ハッシュ関数」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。
「ハッシュ関数」で何を学びますか？
キーをバケットに割り当てます。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
C Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「ハッシュ関数」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このC Academyレッスンでコードを書いて実行できますか？
はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。