[データ構造]Hash

ハシュって何?Hashは、内部で配列を使用してデータを格納するため、検索速度が速い.(ArrayListのメリット)
次に、データを追加/削除するときに、既存のデータをストレッチまたはストレッチ(リストを接続する利点)しないように、特殊なアルゴリズムを使用してデータに関連付けられた一意の数値を生成し、インデックスとして使用します.Hashで使用される内部アレイはHash Tableと呼ばれ、大きさによって性能に差がある.
Hash TableHash Tableは、キー値をテーブルに格納する際に、キー値Hash Methodを用いて計算し、結果値を配列のインデックスとして格納する方式である.
Hash Method
上述したように,Hashは特殊なアルゴリズムを用いてこのアルゴリズムを実現する方法をHash Method,Hash Methodから返されるデータの固有値をHash Codeと呼ぶ.
ハッシュ・メソッドの特性は、次のとおりです.
1.同じ入力値に対して、同じ出力値を保証します.
2.出力値はできるだけ均一な範囲で分布する.
Javaでは、ObjectクラスのhashCode()メソッドを使用して、すべてのオブジェクトのHashCodeを簡単に取得できます.
しかし、入力値が変化しても、同じ出力値が少ないことを해시충돌と呼ぶ.
ハッシュ競合
ハッシュ関数から出力されるハッシュ・コード値が他の入力値と同じ場合に発生する競合をハッシュ競合と呼びます.これらのハッシュ競合は、特定のキーのbucketにデータが集中していることを意味します.したがって、ハッシュ競合が多すぎると、ハッシュ・テーブルのパフォーマンスが低下します.
ハッシュ競合を最小化するには、ハッシュ関数を定義して使用する必要があります.しかし,ハッシュ関数の入力値は無限であるが,出力値は限られているため,必然的にハッシュ競合が発生する.
このハッシュ競合を解決するためには,種々の方法がある.
Hash衝突を解決する方法
1.切寧
bucket内の接続リストを割り当てることでbucketにデータを挿入し、ハッシュ競合が発生した場合は接続リストを使用してデータを接続します.
Java 8以降では、競合を回避するためにより高度な方法が使用され、8つの競合データがある場合は接続リストを트리に変換し、値が6に達した場合は接続リストに変更します.8～7個ではないのは、頻繁な接続リストやツリーの変更によるパフォーマンスの低下を防ぐためです.
2.オープンアドレス法
チェイニングの場合、bucketがいっぱいであっても接続リストに追加されるため、データのアドレス値は変更されません.しかし、オープンアドレス法の場合は異なる.ハッシュ競合が発生した場合,他のbucketにデータを挿入する方法をオープンアドレス法と呼び,オープンアドレス法には3つの代表的なものがある.

1. 선형탐색 : 해시 충돌시 다음 버켓, 혹은 몇개를 건너뛰어 데이터를 삽입한다.
2. 제곱 탐색 : 해시 충돌시 제곱만큼 건너뛴 버켓에 데이터를 삽입
3. 이중 해시 : 해시 충돌시 다른 해시함수를 한 번 더 적용한 결과를 이용함.

Javaは、オープン・アドレス法を使用してデータを削除する際にハッシュ競合を効率的に処理することが難しいため、フィルタ・テクノロジーを使用してハッシュ競合を回避します.