[[ギコ猫の初心者VIPPERでも分かる]] ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿_~ |￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣~ ｜★ハッシュ関数~ ｜ ~ ｜ ハッシュテーブルとは？~ ｜ ~ ｜ ハッシュテーブルは、キーと値の組（エントリ）を複数個格納し、~ ｜ キーに対応する値をすばやく参照するためのデータ構造~ ｜ 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ｌｌﾖ＿＿~ |￣￣| ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣~ ￣￣￣￣~