djb2ハッシュアルゴリズムの解説と実装

はじめに

ハッシュ関数は、データを一意のハッシュ値に変換するための重要なツールです。この記事では、ダニエル・J・バーンスタイン（Daniel J. Bernstein）によって提案された有名なハッシュアルゴリズム「djb2」について解説します。具体的な実装例として、C言語での実装を見ていきます。

djb2アルゴリズムとは

djb2アルゴリズムは、そのシンプルさと効果的なハッシュ値生成能力から広く使用されています。このアルゴリズムは、文字列を入力として受け取り、一意のハッシュ値を生成します。アルゴリズムの核心は、各文字の値に基づいてハッシュ値を更新するビット操作にあります。

実装例

以下に、djb2アルゴリズムを実装したC言語の関数 passHash を示します。この関数は、文字列 str を入力として受け取り、対応するハッシュ値を返します。

unsigned long passHash(const char *str) {
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

実装の詳細

関数の宣言

unsigned long passHash(const char *str)

• unsigned long: 関数が返すデータ型。32ビットまたは64ビットの非負整数です（システムによって異なります）。
• *const char str: 入力として受け取る文字列。const 修飾子が付いているため、関数内部で文字列の内容を変更することはできません。

変数の初期化

unsigned long hash = 5381;
int c;

• hash: ハッシュ値を格納する変数。初期値は 5381 に設定されています。これは、djb2アルゴリズムの初期値として推奨されています。
• c: 現在の文字を格納するための変数。

ハッシュ計算ループ

while (c = *str++)
    hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

• while (c = *str++): ポインタ str が指す文字を変数 c に代入し、str を次の文字に進めます。文字列の終端に達する（NULL文字になる）までループが続きます。ここでは代入演算子 = が使われています。
• hash = ((hash << 5) + hash) + c;: 現在のハッシュ値 hash を更新します。具体的には、hash を左に5ビットシフト（hash << 5）し、それに元の hash を足し、さらに現在の文字 c を加えます。これは hash * 33 + c と等価です。

ハッシュ値の返却

return hash;

• 最終的に計算されたハッシュ値を返します。

ハッシュ計算の詳細

djb2アルゴリズムのハッシュ計算は次のように行われます：

1. 初期値 5381 からスタートします。
2. 各文字に対して、現在のハッシュ値を左に5ビットシフトし、元のハッシュ値を足し、さらに文字の値を加えます。このシフトと加算は、ハッシュ値を生成するためのビット操作です。

以下に、このアルゴリズムの流れを追った具体例を示します：

例：文字列 "abc" の場合

1. 初期値：hash = 5381
2. 'a' を処理:
   • c = 'a' (ASCII値 97)
   • hash = ((5381 << 5) + 5381) + 97
   • hash = (172192 + 5381) + 97
   • hash = 177670
3. 'b' を処理:
   • c = 'b' (ASCII値 98)
   • hash = ((177670 << 5) + 177670) + 98
   • hash = (5687040 + 177670) + 98
   • hash = 5863208
4. 'c' を処理:
   • c = 'c' (ASCII値 99)
   • hash = ((5863208 << 5) + 5863208) + 99
   • hash = (187622656 + 5863208) + 99
   • hash = 193485963
5. 結果のハッシュ値：193485963

このようにして、文字列 "abc" のハッシュ値は 193485963 となります。

まとめ

djb2ハッシュアルゴリズムは、そのシンプルさと効果的なハッシュ値生成能力から、多くの用途で使用されています。特に文字列のハッシュ値を計算する場合に非常に便利です。このアルゴリズムの実装は簡潔でありながら、強力なハッシュ関数を提供します。