このタイトルのウェブページを10年以上前に作って，C言語プログラミングの授業の補助資料としてました．サーバのクラッシュやらなんやらで失くしてしもてたんやけど，
Internet Archive: Wayback Machine
で発見したので，以下に載せとくことにします．
ハッシュ法とは
計算機でデータ処理を行う際には，データのキーを表の形式に格納し，そこからあるキーを探してデータを取り出す，という作業が必要となる場面はよくあります． こういう作業では，「あるキーが表の中にあるかどうか調べる（探索といいます）のをすばやくやりたい」，というような要望があるかもしれません． ハッシュ法（hash method, hashing）は，こういう場合によく使われる手法です． キーをその大小によらず表上に散らばるように格納することから，このような名前がついています．
例えば，学籍番号の数字をキーとして一次元配列に格納することを考えましょう． ばらばらのキーを何も考えずに配列の先頭から順に格納してある場合，ある番号を探索するには，配列を先頭から順に調べていく（順探索あるいは逐次探索）しかないでしょう．
i table[i]
------------
0 901051 <-- 901334 ? (^o^ ここか？
1 901002 <-- 901334 ? (^_^ それともここか？
2 901359 <-- 901334 ? (-_- ないのんか？
3 901000 <-- 901334 ? (~_~ うー
4 900555 <-- 901334 ? (~o~ ほげー
5 901334 <-- 901334 ? (^_^)/ あった
順探索の場合，あらかじめキーの数を知ってれば表のサイズをそれに合わせておけばいいですから，後述のハッシュ法と違って記憶領域に無駄はありません． しかし一方で，探索にはかなり時間を要するかもしれません．
ハッシュ法では，探索をもっとうまいことできるようにデータの格納の仕方を工夫します． 例えば，表のサイズを 10 にして，キーを格納する場所を「キーの値を 10 で割った余り」で計算してみます． つまり，901051 mod 10 は 1 なので table[1] に格納，901002 は table[2] へ…という調子です．
i table[i]
-----------
0 901000
1 901051
2 901002
3
4 901334 <-- 901334 ? (^_^)/ あった
5 900555
6
7 <-- 901777 ? (;_;) ないの
8
9 901359
このように表を作っておけば，901334を探索しろといわれたら， 901334 mod 10 は 4 やから table[4]にあるはずということで，一箇所だけ調べれば済みます． また，901777を探索しろといわれたら，table[7]を見て，そんなんない，ちうことが一発でわかります． というわけで，必要な表のサイズは多少大きくなりますが，探索に要する時間はずっと短くすることができます．
この例の場合，「キーを格納する番地」＝「キーの値を 10 で割った余り」としていますが，このようにキーの値からそれを格納する番地を計算する関数をハッシュ関数と呼びます． 例の場合，キーの値 k から番地を決めるハッシュ関数 H(k) を
H(k) = k mod N ただし N は表のサイズ
としていることになります．
衝突の処理
上記の例は一見うまいこといってますが，困った問題をかかえています． もうひとつキー 901234 も表に入れて，と言われたらどうしましょう． H(901234) = 4 になりますから，入れる場所に困ってしまいます． さてどうしましょう…
解決のための一つのやり方は，（プログラミングおよび実習IIの）講義でも出てきたように，
H(k) 番地で衝突したら，そこから d 番先つまり H(k) + d 番地が空いてるか調べ，空いていればそこに格納． また衝突したら H(k) + 2 * d, H(k) + 3 * d と空きを探していく
という方法です． 講義の例では d = 1 でした． そして，探索のときは，
- あるキー k が H(k) に入っている → 探索成功
- なければ H(k) + d, H(k) + 2 * d, ... を順次チェック．
- キーを見つけた → 探索成功
- キーを見付けられずに空き部屋にたどりついた → 表にはそのキーが入っていない
としてやります．
例えば，↑の表に 901234 を格納する動作は以下のようになります（d = 2 としています）．
i table[i]
-----------
0 901000
1 901051
2 901002
3
4 901334 <-- 901234 を入れたいけど空いてない
5 900555
6 <-- じゃあここに
7
8
9 901359
また，そのあとでこの表から 901234 を探索する動作は以下のようになります．
i table[i]
-----------
0 901000
1 901051
2 901002
3
4 901334 <-- 901234 ? ちゃう
5 900555
6 901234 <-- 901234 ? (^_^)/ あった
7
8
9 901359
このような方法を，線形走査法と呼びます．
まとめ
ハッシュ関数をうまく定めてデータを格納し，それを使って探索を楽にしよう，というのが，ハッシュ法の基本的なアイデアです． その重要なポイントは，
- キーをうまいことばらけさせるようなハッシュ関数をいかに作るか
- 異なるキーが同じハッシュ関数値となった場合にどうするか（衝突の処理）
の二点です． それぞれ，（プログラミングおよび実習IIの）講義や上記の説明に出てきた以外にもたくさんのやり方がありますので，興味のある人は，アルゴリズムを解説した本を探してみるとよいでせう． 例えばたかたかの手元にはこんな本があります．
- 「現代 データ構造とプログラム技法」萩原宏・西原清一 オーム社, ISBN4-274-12831-8, 2,903円, 1987
- 「アルゴリズム 第2巻 探索・文字列・計算幾何」R. セジウィック 著 近代科学社, ISBN4-7649-0256-7, 3,200円, 1996
