連鎖の場合:
誰かが私にこの概念を説明し、理論的な例と簡単なコードを提供してくれませんか?
「各テーブルの場所は、この場所にハッシュされるアイテムのリンクされたリスト (チェーン) を指している」という考えは得られますが、実際に何が起こっているのかを説明することはできません。
h(x) (ハッシュ関数) = x/10 mod 5 があるとします。12540、51288、90100、41233、54991、45329、14236 をハッシュすると、どのようになりますか?
また、オープン アドレッシング (線形プロービング、二次プロービング、すべての R ロケーションのプロービング) についても、誰かが私に説明してくれますか? グーグルで試してみましたが、さらに混乱しているようです。
チェーンは、おそらくハッシュの最も明白な形式です。ハッシュ テーブルは実際には、最初は空であるリンク リストの配列です。項目は、項目の計算テーブル インデックスでリンク リストに新しいノードを追加することによって挿入されます。衝突が発生すると、新しいノードがリンク リストの前のテール ノードにリンクされます。(実際には、実装によってリスト内のアイテムがソートされる場合がありますが、単純にしておきましょう)。このモードの利点の 1 つは、ハッシュ テーブルが「満杯」にならないことです。欠点は、メモリを頻繁にジャンプし、CPU キャッシュに嫌われることです。
Open Addressing は、ハッシュ テーブルがまばらに読み込まれる (エントリ間の大きなギャップ) 可能性が高いという事実を利用しようとします。ハッシュ テーブルは項目の配列です。競合が発生した場合、その場所にある現在のアイテムの末尾にアイテムを追加する代わりに、アルゴリズムはハッシュ テーブル内の次の空きスペースを検索します。ただし、これは、アイテムが存在するかどうかを確認するためにハッシュコードだけに頼ることはできないことを意味します。ハッシュコードが一致する場合は、コンテンツも比較する必要があります。「プローブ」は、次の空きスロットを見つけようとするときにアルゴリズムがたどる戦略です。1 つの問題は、テーブルがいっぱいになる可能性があることです。つまり、空のスロットがなくなります。この場合、テーブルのサイズを変更し、新しいサイズを考慮してハッシュ関数を変更する必要があります。ハッシュ関数が変更されると、ハッシュ コードが同じ値を持たなくなるため、テーブル内の既存のアイテムもすべて再挿入する必要があります。これは時間がかかる場合があります。
これは、ハッシュ テーブルのJava アニメーションです。
mod 5を行うため、テーブルには5つの場所があります
ロケーション 0: 90100
の結果90100/10 mod 5が 0 なので
同じ理由で、次のものがあります。
ロケーション 1: なし
ロケーション 2: 45329
ロケーション 3: 51288->41233->14236
ロケーション 4: 12540->54991
ウィキペディアで詳細を確認できます
オープンアドレッシングでは、任意の手法（負荷率が1未満）を使用して要素をテーブルに格納する必要があります。
ただし、ハッシュテーブルをチェーン化する場合は、リンクリストのヘッドポインターのみが格納されるため、負荷率は1より大きくなる可能性があります。