ハッシュテーブルはデータ構造の一部であるが,アルゴリズムを学習する際に学習される.

1.ハッシュ表とは？

ハッシュテーブルは直接的な広がりを避けるために有効な探索方法である.
ハッシュ・テーブルは、ハッシュ関数を使用して、変換された値をインデックスとして鍵(key)およびデータ(value)を格納する.
ハッシュとは?
任意の長さの値をハッシュ関数で固定サイズの値に変換する操作.
ハッシュ値とは?
「キーkを有する原語は位置h(k)にハッシュされる」とし,k(k)はキーkのハッシュ値となる.
ハッシュ・プロシージャによって計算されるコードは、鍵のデータ型であり、通常intまたはlongである.
次に、hash(key)%array lengthなどのハッシュコードを使用して配列をインデックスします.
ここで重要なのは、ハッシュを使用する場合、同じインデックスを使用できることです.
このような状況を衝突と呼ぶ.衝突を解消することが最も適切に見えるが、これはほとんど不可能であるため、多くの解決方法がある.
1つは連鎖によって衝突を解決することである.
同じ値を持つ位置にハッシュされたすべての要素を接続リストに入れて解決します.

2.ハッシュ表の利点

1.より少ないリソースで大量のデータを効率的に管理する.
たとえば、ハードディスク(HDD)やクラウド上の大量のデータを限られたハッシュ値にマッピングすることで、より小さなキャッシュを使用してプロセス管理を行うことができます.
2.配列インデックスを使用すると、検索、挿入、削除が速くなります.(平均時間複雑度:O(1))

인덱스를 사용해서 배열의 검색이 빠르다는 것은 당연한 소리이다. 하지만 삽입, 삭제는 왜 O(1)인가?
여기서의 인덱스는 데이터만의 고유한 위치이기 때문에 만약 삽입이나 삭제를 한다고 해도 다른 데이터로 채울 필요가 없다. 즉, 삽입이나 삭제할 때 데이터를 이동할 필요가 없기 때문이다.

3.鍵(key)とHash値(Hash)は関連性がないため、セキュリティによく使用される.
4.データ・キャッシュでよく使用されます.
get(key)、put(key)にキャッシュロジックを追加すると、頻繁にヒットするデータがすぐに見つかります.

3.ハッシュ表の欠点

1.競合
2.空間的複雑度が増大する.
3.順序のある配列には向いていません.
4.ハッシュ関数依存性の増加.

4.ハッシュ表の時間的複雑さ

ハッシュテーブルを介して集合Kをナビゲートするのに要する時間はO(1)である.
しかし,衝突が発生すると,時間的複雑さはO(N)に増大する可能性がある.
衝突を防止する方法は,データの規則性を防止するためであり,占有空間が大きい致命的な欠点がある.
また、テーブルが満たされている場合は、テーブルを拡張する必要があります.これにより、パフォーマンスが大幅に低下する可能性があります.そのため、できるだけ少ない低消費電力拡張を設計することが重要です.
リファレンス
Introduction to Algoritms
https://mangkyu.tistory.com/102
https://hee96-story.tistory.com/48
学期中なので、週末のような時間に、可能な日付でさらに内容を強化する予定です.