ギコ猫の初心者VIPPERでも分かる?

    _______________________
    | ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
    |★ハッシュ関数
    |  
    |  ハッシュテーブルとは?
    |  
    |  ハッシュテーブルは、キーと値の組(エントリ)を複数個格納し、
    |  キーに対応する値をすばやく参照するためのデータ構造
    |         by wikipedia
    |  
    |    。/ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
   ΛΛ  / | 再開するかもぜ(’A`)
  (,,゚Д゚)⊃ ∠___________________
~/U /___________________Ellヨ__
 | ̄ ̄|  ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
 ̄ ̄ ̄ ̄


    _______________________
    | ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
    |★でっていう
    |  どういうときに使うかというと
    |  
    |  ヤマダ -> 170cm
    |  タナカ  -> 175cm
    |  サイトウ-> 185cm
    |  
    |  このように 名前に関連付けてデータを扱いたいときに
    |  使います
    |    。/ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
   ΛΛ  / | オナカスイタ
  (,,゚Д゚)⊃ ∠___________________
~/U /___________________Ellヨ__
 | ̄ ̄|  ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
 ̄ ̄ ̄ ̄


    _______________________
    | ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
    |★普通に構造体配列使えばよくね?
    |  
    |  そうですが、ハッシュの魅力は、配列に
    |  順番に入れるよりもすばやく処理できることに
    |  あります
    |  
    |     / ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
    |      | 三項演算・ビット演算・配列の参照にx+1
    |     。| #define a int とか typedef
   ΛΛ  / | みたいな事すると 読み難いコードが出来上がるぜ
  (,,゚Д゚)⊃ ∠___________________
~/U /___________________Ellヨ__
 | ̄ ̄|  ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
 ̄ ̄ ̄ ̄


    _______________________
    | ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
    |★んじゃどうすんの?
    |  
    |  ①入力された「名前」に対して 配列のサイズに合わせて
    |   数字を割り当てます
    |  
    |  ②その数字の位置にデータを入れます。
    |  ③(゚д゚)ウマー
    |  
    |    。/ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
   ΛΛ  / | ①をハッシュ関数っていうんだぜ。
  (,,゚Д゚)⊃ ∠___________________
~/U /___________________Ellヨ__
 | ̄ ̄|  ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
 ̄ ̄ ̄ ̄


    _______________________
    | ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
    |★①についてkwsk
    |
    |  つまり、配列の何番目に入れるかを計算で決めます。
    |  例えば「ヤマダ」だと「3」を返すようにすると
    |
    |   0    1   2   3
    |  [   ][   ][   ][   ]
    |               ↑
    |         ここがヤマダのデータ
    |  
    |  のようになります。
    |  ただし、上の場合だと「3」より大きい値を返すと
    |  Segmentation Fault 配列のサイズ以上の
    |  領域にデータをいれようとするのでエラーが出ます。
    |  
    |    。/ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
   ΛΛ  / | MD5・SHAを返すのとかもハッシュ関数なんだぜ。
  (,,゚Д゚)⊃ ∠___________________
~/U /___________________Ellヨ__
 | ̄ ̄|  ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
 ̄ ̄ ̄ ̄


    _______________________
    | ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
    |★いいから①のハッシュ関数作れよ
    |
    |  最も簡単なのは、名前を整数にして、
    |  Mで割り、その余りをハッシュ値とすることです
    |  この場合、ハッシュ値は 「0~M-1」のどれかになるよね!
    |  
    |   例えば、M=4、ヤマダ=11だとすると
    |  
    |     ヤマダ(11) % M(4) = 3
    |  
    |   0    1   2   3       M-1
    |  [   ][   ][   ][   ]・・・・・・[   ]
    |               ↑
    |         ここがヤマダのデータ
    |  
    |    。/ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
   ΛΛ  / | ハッシュ値とはハッシュ関数が返す値だぜ。
  (,,゚Д゚)⊃ ∠___________________
~/U /___________________Ellヨ__
 | ̄ ̄|  ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
 ̄ ̄ ̄ ̄


    _______________________
    | ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
    |★ちょwwwwやばいwwwww
    |
    |  タナカ=7にするとヤバイwwwww
    |  
    |   そうです、M=4、タナカ=7、ヤマダ=11だとすると
    |  
    |     ヤマダ(11) % M(4) = 3
    |     タナカ(7)  % M(4) = 3
    | 
    |   0    1   2   3       M-1
    |  [   ][   ][   ][   ]・・・・・・[   ]
    |               ↑
    |         タナカ?ヤマダ?どっち?
    |  
    |    。/ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
   ΛΛ  / | これを衝突というんだぜ。
  (,,゚Д゚)⊃ ∠___________________
~/U /___________________Ellヨ__
 | ̄ ̄|  ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
 ̄ ̄ ̄ ̄


    _______________________
    | ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
    |★衝突した時どうすんの?
    |  
    |  衝突は絶対に起きるものです。
    |  そのような時は、適当な計算をしてあらたな
    |  ハッシュ値を与えましょう
    |  
    |  今回は、「配列の右端(M-1)ー余り」でやってみます。
    |   ●M=4、タナカ=7、ヤマダ=11だとすると
    |  
    |     ヤマダ(11) % M(4) = 3
    |     タナカ(7)  % M(4) = 3 ←被ったww
    |     タナカ→ 右端(3)-3 = 0
    | 
    |   0    1   2   3
    |  [   ][   ][   ][   ]
    |   ↑          ↑
    |   タナカ      ヤマダ
    |     / ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
    |     。| 新たなハッシュ値が配列の右端より大きかっ
   ΛΛ  / | たら駄目だぜ
  (,,゚Д゚)⊃ ∠___________________
~/U /___________________Ellヨ__
 | ̄ ̄|  ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
 ̄ ̄ ̄ ̄


    _______________________
    | ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
    |★で、なんの為にしてたんだっけ?
    | 
    |  このようにして、配列の身長を入れることが出来ました!
    | 
    |  [160cm][   ][   ][175cm]
    |   ↑           ↑
    |   タナカ       ヤマダ
    | 
    |  そして、次にデータを取り出すときには
    |  「名前」をハッシュ値にすればいいわけですね。
    |  
    |  ( ゚∀゚)彡ヤマダ!ヤマダ!
    |        となったら
    |  
    |  ゚Д゚)y~~<   ヤマダ(11) % M(4) = 3 だぜ
    | 
    |  ( ゚∀゚)彡ヤマダ=3! ヤマダ=3! ←パスワードを入力します。
    |  yamada = sincyo[3];  のようにすればおk!
    |  
    |    。/ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
   ΛΛ  / | これで、配列の中身から名前検索しなくて済むだろ
  (,,゚Д゚)⊃ ∠___________________
~/U /___________________Ellヨ__
 | ̄ ̄|  ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
 ̄ ̄ ̄ ̄


    _______________________
    | ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
    |★補足1
    |  
    |  実際はヤマダ=11なんてできないので、
    |  大抵はコード番号を使います。
    |  
    |  ASCIIコードを使って
    |    A=65 ですね。
    |  
    |  これならC言語でも簡単に扱えます。
    |  
    |  
    |    。/ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
   ΛΛ  / | Hash('A'); とするんだゴルァ
  (,,゚Д゚)⊃ ∠___________________
~/U /___________________Ellヨ__
 | ̄ ̄|  ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
 ̄ ̄ ̄ ̄


    _______________________
    | ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
    |★補足2
    |  
    |  ●衝突して、新しい値でも衝突したら?
    |  
    |  また、新しい値を与えます。
    |  
    |  
    |    。/ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
   ΛΛ  / | 新しい値は前と違う値になるようにしろよ
  (,,゚Д゚)⊃ ∠___________________
~/U /___________________Ellヨ__
 | ̄ ̄|  ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
 ̄ ̄ ̄ ̄


    _______________________
    | ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
    |★では、実際に作ってみましょう!
    |  
    |  身長と名前 をハッシュテーブルに登録する
    |  プログラムを作ってみます。
    |  
    |    。/ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
   ΛΛ  / | 需要があるのか無いのか分からねぇぞゴルァ
  (,,゚Д゚)⊃ ∠___________________
~/U /___________________Ellヨ__
 | ̄ ̄|  ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
 ̄ ̄ ̄ ̄


    _______________________
    | ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
    |★では、実際に作ってみましょう!
    |  
    |  まず、データの構造体を用意します。
    |  
    |  struct list {
    |   char name[MAX_NAME]; // ←名前
    |   int height;          // ←身長
    |  }
    |     / ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
    |      | 構造体の中に
    |     。|    struct list *next; 
   ΛΛ  / | として衝突時の次の値を参照する方法もあるぞ
  (,,゚Д゚)⊃ ∠___________________
~/U /___________________Ellヨ__
 | ̄ ̄|  ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
 ̄ ̄ ̄ ̄