データ構造vol.4【動画#22】ハッシュとは/ハッシュ関数/連鎖ハッシュの解説

＜データ構造vol.4 ハッシュとは/ハッシュ関数＞

1. ハッシュとは

任意の要素がデータ集合に含まれているのかを
高速で見分けるためのデータ構造

※ハッシュ化とは、ハッシュ関数を用いてKeyをハッシュ値にすること

2. ハッシュ化の技術について

ITにおいて非常に多くの場所で使用されている。

【例】
ユーザーのメールアドレスを保存する場合
➡︎そのまま保存するのではリスクが高いためハッシュ化して保存する。

3. ハッシュの問題

ハッシュ関数によって、衝突する場合がある。

4. 衝突を回避する方法

連鎖ハッシュ

ハッシュ関数によって、衝突を回避する関数

【具体的説明】

①ハッシュ値をインデックスにする
➡︎田中、佐々木、吉田、岡村をKeyとして年齢をハッシュに格納

②配列の中身をリストへのポインタとする
この場合、吉田と岡村で衝突するためその回避方法
➡︎吉田と岡村が連鎖している状態になる

連鎖ハッシュでは、吉田と岡村のように衝突が起きても、リストで連鎖的に保存しているため、リストを先頭から順番に辿れば、欲しいKeyに対応するデータを探し出すことができる。

＜今回の総まとめ＞
ハッシュと連鎖ハッシュを使えるようにして、より効率的にデータを扱えられるようにしよう

次回、AI開発に必要な計算量について　時間計算量とは/空間計算量とは/IO計算量とは　について簡単に整理する。