ギコ猫/C言語/ハッシュテーブル
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
[[ギコ猫の初心者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ｌｌﾖ＿＿~
|￣￣| ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣~
￣￣￣￣~
終了行:
[[ギコ猫の初心者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ｌｌﾖ＿＿~
|￣￣| ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣~
￣￣￣￣~
ページ名:
