102
Help us understand the problem. What are the problem?

More than 5 years have passed since last update.

posted at

updated at

ハッシュテーブル(Hash Table)を簡単に理解しよう

ハッシュテーブルは普段色々な名前でよく出て来ると思うが、例えばpython/swiftのdictionary, JSON, PHPの配列、java/c++のhashmapなど
これはコンピューターの中でどうやって実現したのだろうかを説明しようと思う

ハッシュテーブルの特徴

一つ値に対して唯一のキー

あれ?逆じゃない?と思う人いると思うが、実はハッシュテーブルを作るとき違う値を同じキーに配ってしまう場合もある、それは「衝突」と呼ぶ。
衝突はあとで説明する。

追加と呼び出しが早い

ハッシュテーブルも配列系のデータ構造の一種類として、他の二つは配列とリンクリストになる。
・配列は値を呼び出す時アドレスさえあれば一瞬で終わるが、一つの値を追加・削除すると、他の値も詰めてきて、引っ越さないといけない
・リンクリストは追加が早いが(最後尾に入るから)、呼び出す時入ってるデータを一つづつ確認しないといけない
・ハッシュテーブルは、追加する時ハッシュ関数を回してキーからアドレスを得て、他の値に影響しない上で、呼び出す時キーさえあれば、アドレスもキーからわかってきて、すぐ値を尋ねられる。

原理

流れのイメージ

key ====ハッシュ関数をかける====> H(key) ====アドレスGET====> (key|value)

こんな流れです(wikipediaの画像)
image.png

ハッシュ関数

それではハッシュ関数はどんなものだろうか
簡単にいうと:どんなキーがきてもとりあえず重複のない数字に変換するメソッド

例:

input = [23, 7, 11, 4, 10]  (キー)
これは明らかに5を割ってその余を取れば重複がなさそう
Hash関数 h(key) = n mod 5
Hash後 [3, 2, 1, 4, 0]  ( H(key) )

ハッシュテーブルに使うハッシュ関数はこの三つを要求されている

・わかりやすさ
・アドレスを平均的に配る
・キーの重複を避ける

よく使われるハッシュ関数

  1. キーが数字の場合、一次方程式をとる:H(key) = a·key + b
  2. キーが数字の場合、それらのキーは規律あるかどうかを探ぐり、重複の少ない一部を取る
  3. キーが数字の場合、そして規律もなさそうで、キーを二乗を取って、二乗した結果の真ん中の一部をとる。(二乗した結果の真ん中の部分は数字全体と関係あるので、重複を避けられる)
  4. キーを何等分して、それを全部加算する
  5. 乱数関数を用いる
  6. テーブルの長さを割って、余をとる

色々紹介したと思うが、実際使う時ハッシュ関数は重複なければなんでもいい

ハッシュテーブルの例

データ:

名前 小嶋陽菜 柏木由紀 前田敦子
成績 76 78 66

これを名前->成績の形のハッシュテーブルを作ると
名前の略語のアルファベット順の和というハッシュ関数を使おう

名前 小嶋陽菜 柏木由紀 前田敦子
名前の略語 KH KY MA
アルファベット順 11 8 11 25 13 1
H(key) 11+8 11+25 13+1
アドレス 19 36 14
成績 76 78 66

こんな感じ

衝突

例:

しかし、さっきと同じハッシュ関数を用いて、今回まゆゆもテスト参加することになったら、

名前 小嶋陽菜 柏木由紀 前田敦子 渡辺麻友
成績 76 78 66 80

ハッシュする時はこうなってしまう

名前 小嶋陽菜 柏木由紀 前田敦子 渡辺麻友
名前の略語 KH KY MA WM
アルファベット順 11 8 11 25 13 1 23 13
H(key) 11+8 11+25 13+1 23+13
アドレス 19 36 14 36
成績 76 78 66 80

これは「衝突」と言います

衝突解消

  1. バイヤスを追加する H(key) => H(key) + di(開番地法)

    • 線形プローブ di = 1, 2, 3, … , m-1
    • 二次プローブ di=1^2,-1^2,2^2,-2^2, 3^2, … , ±(k)^2
    • 乱数
  2. ダブルハッシュ(もう一回ハッシュ関数をかける)。重複解消のが目的なので、違う関数を用いるが、同じ関数をもう一回かけるか、どちらでも構わない

  3. 連鎖法。重複になったキーをリンクリストの型でアドレスの最後尾に追加する

ここも色々紹介したが、実際使う時キーの重複を解消できればなんでもいい


いかがでしょうか

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
102
Help us understand the problem. What are the problem?