ハッシュというと、キーと値をマッピングしたものを連想しますか？
string str = hash["あいう"];
で、”あいう”にマッピングされた値を取り出せるような。
実は、正確にはこれをハッシュと呼ぶのは間違いのようです。
実際には、連想配列と言います。
ハッシュとは、ハッシュ関数から得られた値を指すようです。
連想配列は、ハッシュを応用したものの１つなのです。
ハッシュを利用したものの代表的なものなので、俗にハッシュと呼ばれるようです。
すみません。言葉遊びから入ってしまいました（＾＾）
突然、「ハッシュ関数」「ハッシュ値」と言われても分からないですよね。
でも、このあとハッシュ関数とハッシュテーブルの説明でバッチリ
分かるはず。（たぶん。。）
つたない説明ですが、よろしくお願いします。
ここでは、連想配列を作成することを考えることで説明を試みようと思います。
＜連想配列を作る前に＞
キーと値をマッピングして、キーから値を検索できるようにするにはどうするでしょうか？
まず考えそうなのが、キーとその値を構造体などにして配列に入れていき、検索するときは、配列の上から順に１つずつ文字列比較していけばよさそうです。
しかし、この方法は最悪、配列の一番最後でマッチするので、キーがn個あるとn回文字列比較しないといけないです。
そして、m回検索するとなると、n×m回の文字列比較です。
それくらいたいしたことないでしょ！って思います？
配列が100個、検索を100回すると、文字列比較は10000回です。
配列が1000個、検索1000回なら100万回！！
ほら！だんだん怪しくなってきましたよ～。
これだけ回数があると、文字列の比較は結構時間が掛かります。
＜賢い人の思いつき＞
あるとき、賢い人が思いました。
なんとか文字列比較の回数を減らせないかと。
＜ハッシュ関数＞
まず、文字列を何らかの方法で、0～50の範囲の数値に変換しましょう！
え！？どうやって？
文字列はC言語では単なる数値なので簡単なのです。
char* str = "abcdef";
str[0] ⇒ 97
str[1] ⇒ 98
：
安易な方法の１つは、全部足して51で割って余りを得るなどです。
( str[0] + str[1] + ・・・ + str[5] ) % 51
これで文字列から、指定の範囲の数値を得ることができました。
このような数値を得られる関数をハッシュ関数といいます。（計算方法は規定されていません）
これがいったい何の役に立つの？って思いますよね？
＜ハッシュテーブル＞
ここで、唐突ですが、配列の配列（2次元配列）を考えます。
このときルールを付けます。
キーの文字列を数値化して、その数値と同じ配列の位置にキーと値を設定するのです。
例：
ary[0] ⇒ { "あいう", "さしす"}
ary[1] ⇒ { "たちつ"}
ary[2] ⇒ { "かきく", "ふいに", "くるす"}
：
ary[50] ⇒ ・・・
たとえば、「かきく」を数値化したときに「２」になったとすると、ary[2]に入れるのです。
そうすると、すばらしいことが起きます！
なんと、キーの検索をするときに、「かきく」を指定するといきなり、要素「２」にキーが存在することが分かるのです。
そうすると、最大でも3回の文字列比較で目的のキーに到達します。
良いアイデアですよね？
ハッシュ関数をうまく決めて、各ary配列にキーを収める数が平均化されれば、
キーの数 ÷ 51 回 の検索数ですみます！！
また、aryの要素数を今回51にしましたが、これも増やせばもっと検索数が少なくなります。
これが、連想配列でキーの検索が早くなる仕組みです。
【補足】
①実はハッシュ関数の作り方が結構難しいのです。
たとえば偏りが大きくて、ほとんどの文字列が「３０」になったとします。
そうすると、結局キーの数だけ文字列比較しないといけなくなります。
②上記では、要素の数を５１にしました。
これは割り算の余りを利用しているのですが、素数の方が偏りが少なくなることが知られているようです。
参考：