java - Javaでの個別の連鎖

Question

私たちのクラスはハッシュテーブルについて学習しています。私の研究の質問の1つは、個別のチェーンを持つハッシュテーブルを使用して辞書を作成することです。ただし、問題は、ハッシュテーブルを作成するためにJavaが提供するメソッドを使用することは許可されていないということです。むしろ、私たちの講義ノートは、個別の連鎖には、エントリのリンクリストを指す配列内の各セルが含まれると述べています。

したがって、私の理解では、サイズn（nは素数）の配列を作成し、配列の各位置に空のリンクリストを挿入する必要があります。次に、ハッシュ関数を使用して文字列をハッシュし、対応するリンクリストの適切な配列位置に挿入します。ハッシュ関数を作成しました。これまでのところ、Dictionaryコンストラクターはサイズを受け取り、そのサイズの配列を作成します（実際には、クラスで説明されているように、プライムとラージの両方のサイズ4999です）。私はここで正しい方向に進んでいますか？ここで、新しいリンクリストを各位置に挿入してから、挿入/削除メソッドで作業する必要がありますか？

Answer 1

あなたが持っているものは今のところ良い音がします。

オブジェクト参照の配列にはnullデフォルトで各セルがあり、それを操作するために挿入関数と削除関数を記述できることに注意してください。データを含まないリンクリストオブジェクト（センチネルノードと呼ばれることもあります）を作成する場合は、new（ほとんどの場合、データは保持されません）。

Answer 2

順調に進んでいるようですね。

いくつかの追加のポインタ：

• 実際に使用されるまで、各バケットにLinkedListを作成する価値はありません。したがって、バケットが追加されるまで、バケットをnullのままにしておくことができます。これを考慮して、アクセサ関数を作成することを忘れないでください。
• 大きなアレイをすぐに作成することは必ずしも効率的ではありません。小さな配列から始めて、使用されている容量を追跡し、必要に応じて配列を拡大することをお勧めします（これには、新しい配列への値の再バケット化が含まれます）
• クラスにインターフェース全体を実装させることをお勧めしますMap<K,V>。他の標準的なJavaコレクションメソッドを実装する練習をするためだけです。