＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿_
|￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
｜★ハッシュ関数
｜
｜ ハッシュテーブルとは？
｜
｜ ハッシュテーブルは、キーと値の組（エントリ）を複数個格納し、
｜ キーに対応する値をすばやく参照するためのデータ構造
｜ by wikipedia
｜
｜ 。／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
ΛΛ ／ | 再開するかもぜ(’A`)
(,,ﾟДﾟ)⊃ ∠＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
～/U /＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿Eｌｌﾖ＿＿
|￣￣| ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
￣￣￣￣
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿_
|￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
｜★でっていう
｜ どういうときに使うかというと
｜
｜ ヤマダ -> 170cm
｜ タナカ -> 175cm
｜ サイトウ-> 185cm
｜
｜ このように 名前に関連付けてデータを扱いたいときに
｜ 使います
｜ 。／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
ΛΛ ／ | オナカスイタ
(,,ﾟДﾟ)⊃ ∠＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
～/U /＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿Eｌｌﾖ＿＿
|￣￣| ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
￣￣￣￣
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿_
|￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
｜★普通に構造体配列使えばよくね？
｜
｜ そうですが、ハッシュの魅力は、配列に
｜ 順番に入れるよりもすばやく処理できることに
｜ あります
｜
｜ ／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
｜ | 三項演算・ビット演算・配列の参照にx+1
｜ 。| #define a int とか typedef
ΛΛ ／ | みたいな事すると 読み難いコードが出来上がるぜ
(,,ﾟДﾟ)⊃ ∠＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
～/U /＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿Eｌｌﾖ＿＿
|￣￣| ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
￣￣￣￣
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿_
|￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
｜★んじゃどうすんの？
｜
｜ ①入力された「名前」に対して 配列のサイズに合わせて
｜ 数字を割り当てます
｜
｜ ②その数字の位置にデータを入れます。
｜ ③(ﾟдﾟ)ｳﾏｰ
｜
｜ 。／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
ΛΛ ／ | ①をハッシュ関数っていうんだぜ。
(,,ﾟДﾟ)⊃ ∠＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
～/U /＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿Eｌｌﾖ＿＿
|￣￣| ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
￣￣￣￣
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿_
|￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
｜★①についてｋｗｓｋ
｜
｜ つまり、配列の何番目に入れるかを計算で決めます。
｜ 例えば「ヤマダ」だと「3」を返すようにすると
｜
｜ 0 １ ２ ３
｜ [ ][ ][ ][ ]
｜ ↑
｜ ここがヤマダのデータ
｜
｜ のようになります。
｜ ただし、上の場合だと「３」より大きい値を返すと
｜ Segmentation Fault 配列のサイズ以上の
｜ 領域にデータをいれようとするのでエラーが出ます。
｜
｜ 。／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
ΛΛ ／ | MD5・SHAを返すのとかもハッシュ関数なんだぜ。
(,,ﾟДﾟ)⊃ ∠＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
～/U /＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿Eｌｌﾖ＿＿
|￣￣| ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
￣￣￣￣
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿_
|￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
｜★いいから①のハッシュ関数作れよ
｜
｜ 最も簡単なのは、名前を整数にして、
｜ Mで割り、その余りをハッシュ値とすることです
｜ この場合、ハッシュ値は 「０～M-1」のどれかになるよね！
｜
｜ 例えば、M＝4、ヤマダ＝11だとすると
｜
｜ ヤマダ（11） % M（４） ＝ ３
｜
｜ 0 １ ２ ３ M-1
｜ [ ][ ][ ][ ]・・・・・・[ ]
｜ ↑
｜ ここがヤマダのデータ
｜
｜ 。／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
ΛΛ ／ | ハッシュ値とはハッシュ関数が返す値だぜ。
(,,ﾟДﾟ)⊃ ∠＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
～/U /＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿Eｌｌﾖ＿＿
|￣￣| ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
￣￣￣￣
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿_
|￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
｜★ちょｗｗｗｗやばいｗｗｗｗｗ
｜
｜ タナカ＝７にするとヤバイｗｗｗｗｗ
｜
｜ そうです、M＝4、タナカ＝７、ヤマダ＝11だとすると
｜
｜ ヤマダ（11） % M（４） ＝ ３
｜ タナカ（７） % M（４） ＝ ３
｜
｜ 0 １ ２ ３ M-1
｜ [ ][ ][ ][ ]・・・・・・[ ]
｜ ↑
｜ タナカ？ヤマダ？どっち？
｜
｜ 。／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
ΛΛ ／ | これを衝突というんだぜ。
(,,ﾟДﾟ)⊃ ∠＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
～/U /＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿Eｌｌﾖ＿＿
|￣￣| ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
￣￣￣￣
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿_
|￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
｜★衝突した時どうすんの？
｜
｜ 衝突は絶対に起きるものです。
｜ そのような時は、適当な計算をしてあらたな
｜ ハッシュ値を与えましょう
｜
｜ 今回は、「配列の右端（M-1）ー余り」でやってみます。
｜ ●M＝4、タナカ＝７、ヤマダ＝11だとすると
｜
｜ ヤマダ（11） % M（４） ＝ ３
｜ タナカ（７） % M（４） ＝ ３ ←被ったｗｗ
｜ タナカ→ 右端(３)-３ ＝ ０
｜
｜ 0 １ ２ ３
｜ [ ][ ][ ][ ]
｜ ↑ ↑
｜ タナカ ヤマダ
｜ ／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
｜ 。| 新たなハッシュ値が配列の右端より大きかっ
ΛΛ ／ | たら駄目だぜ
(,,ﾟДﾟ)⊃ ∠＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
～/U /＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿Eｌｌﾖ＿＿
|￣￣| ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
￣￣￣￣
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿_
|￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
｜★で、なんの為にしてたんだっけ？
｜
｜ このようにして、配列の身長を入れることが出来ました！
｜
｜ [160cm][ ][ ][175cm]
｜ ↑ ↑
｜ タナカ ヤマダ
｜
｜ そして、次にデータを取り出すときには
｜ 「名前」をハッシュ値にすればいいわけですね。
｜
｜ ( ﾟ∀ﾟ)彡ヤマダ！ヤマダ！
｜ となったら
｜
｜ ﾟДﾟ）y~~＜ ヤマダ（11） % M（４） ＝ ３ だぜ
｜
｜ ( ﾟ∀ﾟ)彡ヤマダ=3! ヤマダ=3! ←パスワードを入力します。
｜ yamada = sincyo[3]; のようにすればおｋ！
｜
｜ 。／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
ΛΛ ／ | これで、配列の中身から名前検索しなくて済むだろ
(,,ﾟДﾟ)⊃ ∠＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
～/U /＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿Eｌｌﾖ＿＿
|￣￣| ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
￣￣￣￣
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿_
|￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
｜★補足１
｜
｜ 実際はヤマダ＝11なんてできないので、
｜ 大抵はコード番号を使います。
｜
｜ ASCIIコードを使って
｜ A=65 ですね。
｜
｜ これならC言語でも簡単に扱えます。
｜
｜
｜ 。／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
ΛΛ ／ | Hash('A'); とするんだｺﾞﾙｧ
(,,ﾟДﾟ)⊃ ∠＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
～/U /＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿Eｌｌﾖ＿＿
|￣￣| ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
￣￣￣￣
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿_
|￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
｜★補足２
｜
｜ ●衝突して、新しい値でも衝突したら？
｜
｜ また、新しい値を与えます。
｜
｜
｜ 。／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
ΛΛ ／ | 新しい値は前と違う値になるようにしろよ
(,,ﾟДﾟ)⊃ ∠＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
～/U /＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿Eｌｌﾖ＿＿
|￣￣| ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
￣￣￣￣
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿_
|￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
｜★では、実際に作ってみましょう！
｜
｜ 身長と名前 をハッシュテーブルに登録する
｜ プログラムを作ってみます。
｜
｜ 。／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
ΛΛ ／ | 需要があるのか無いのか分からねぇぞｺﾞﾙｧ
(,,ﾟДﾟ)⊃ ∠＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
～/U /＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿Eｌｌﾖ＿＿
|￣￣| ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
￣￣￣￣
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿_
|￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
｜★では、実際に作ってみましょう！
｜
｜ まず、データの構造体を用意します。
｜
｜ struct list {
｜ char name[MAX_NAME]; // ←名前
｜ int height; // ←身長
｜ }
｜ ／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
｜ | 構造体の中に
｜ 。| struct list *next;
ΛΛ ／ | として衝突時の次の値を参照する方法もあるぞ
(,,ﾟДﾟ)⊃ ∠＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
～/U /＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿Eｌｌﾖ＿＿
|￣￣| ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
￣￣￣￣