[解決済み] HashTableは衝突をどのように処理するのですか？

質問

学位論文の授業で HashTable は、新しい Key エントリが他のエントリと衝突した場合、「次に利用可能な」バケツに配置するそうです。

はどのように HashTable を呼び出したときにこの衝突が発生した場合でも、正しい値を返すのでしょうか？

私が想定しているのは Keys は String の型であり hashCode() はJavaと言ったもので生成されたデフォルトを返します。

もし私が独自のハッシュ関数を実装し、それをルックアップテーブルの一部として使うなら (すなわち HashMap または Dictionary など）、衝突に対処するための戦略はどのようなものがあるでしょうか？

素数に関するメモも見たことがありますよ。Google検索ではあまりはっきりしない情報です。

どうやって解くのですか？

ハッシュテーブルは、2つの方法のいずれかで衝突に対処しています。

オプション1: 各バケットに、そのバケットにハッシュ化された要素のリンクリストを持たせることで、そのバケットにハッシュ化された要素が含まれるようになります。これは、悪いハッシュ関数がハッシュテーブルのルックアップを非常に遅くしてしまう理由です。

オプション 2: ハッシュテーブルのエントリがすべて一杯になった場合、ハッシュテーブルは持っているバケットの数を増やし、テーブル内のすべての要素を再分配することができます。ハッシュ関数は整数を返すので、ハッシュテーブルはハッシュ関数の結果を受け取り、それをテーブルのサイズに対して修正する必要があります。そのため、サイズを大きくすると、ハッシュ関数が再計算されてモジュロ計算が行われ、運が良ければオブジェクトが別のバケツに送られるかもしれません。

Java では、ハッシュ テーブルの実装でオプション 1 と 2 の両方を使用しています。