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

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

ハッシュテーブルの特徴

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

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

追加と呼び出しが早い

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

原理

流れのイメージ

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

こんな流れです（wikipediaの画像）

ハッシュ関数

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

例:

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. 連鎖法。重複になったキーをリンクリストの型でアドレスの最後尾に追加する

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

---

いかがでしょうか