はじめての C

C programming note*1

ハッシュは データ構造そのものと いうよりも、アルゴリズムと 深く 結びついているので、いままで 説明してきた 他の データ構造とは ちょっと 毛色が 変わっていると いえる。

ハッシュを 使うと、データ構造の 中から あるデータを 検索するのに、データの 比較などを せずに 基本的には 計算するだけで 検索することが できる。

データを 格納するための メモリ領域が 比較的 多めに 必要なかわりに、データの 検索が 速いという 特徴がある。

ハッシュ法の 検索において 「キーから データの 格納場所を 計算する」 関数を ハッシュ関数という。

この関数を 使って データの 内容ごとに 「格納すべき 場所」 を 決定して その位置に データを 格納してあるので、アクセスするときも 計算で 位置が 求められるわけだ。(p216)

K&R 2nd では、次の 2つの 章で 取り上げられています。
http://d.hatena.ne.jp/sekiyo/20051029
http://d.hatena.ne.jp/sekiyo/20051103
まず、キーと データとを 格納するための ポインタ配列を つくり、配列に 格納する 最大値を 決定していきます。 こんな 感じで、

# define HASHSIZE 101
static *hashtab[HASHSIZE];

この hashtable と、あと ハッシュ関数が 準備できれば、hash search の 半分以上は できたも 同然です。
hashtable には ふつう 構造体を 用い、1つの key に 1つの data が 割り当てられるように します。

typedef struct {

    char *key;

    char *data;

} ENTRY;
static ENTRY *hashtab[HASHSIZE];

例題の ハッシュ関数は、 K&R 2nd に 載っているものとは 少しだけ 違っています。

int hash(char *s){

    unsigned u;
    for (u = 0; *s != '\0'; s++)

        u = ((u << 8) + *s) % HASHSIZE;

    return u;

}

s は 「文字列中の 各文字」 ですから、1文字ずつ 「文字の value (と シフト計算の 結果) を 混ぜ合わせながら」 それを HASHSIZE で 割った modulo (余り) を 次々 加算していき、その計算結果を ハッシュ値として 返しています。
また、ここでは ビット演算子の "<<" も 使われています。

a = a << b;

の 場合、a は 必ず 正の値であり、b は ビット数を 表わします。"<<" は 左シフトですから、このとき a の値は 2 の b乗倍に なります。
上の ハッシュ関数だと、2 の 8乗 つまり 256倍に なるわけです。
また、前にも 見たように、モジュロ演算子の 左側の 数値が どれだけ 大きくなっても 割る数の 値を 越えることは ありません。

u = ((u << 8) + *s) % HASHSIZE;

u の値は HASHSIZE より 大きくは ならないわけです。
ハッシュ値は hashtable の 添値として 使われるのですが、モジュロ演算子を 用いることで、格納される key と data は つねに 最大値が HASHSIZE の 配列内に 収まるように なります。

*1:「作ってわかる Cプログラミング」