私は、チェーン化されたハッシュ セットを実装する割り当てとして与えられました。
このセットは Linked-List の配列 (ここでは と呼びますA[]) によって支えられており、2 つの異なる値が同じハッシュ値を取得した場合k、それらは list に追加されますA[k]。
構造は、制限された負荷係数 (間隔[0.25, 0.75]) で問題なく動作します。
指示では、負荷係数を次のように計算するように指示されました。
負荷率=サイズ/容量
ここで、「サイズ」は現在セット内にある要素の総数であり、「容量」は配列の長さ ( A.length) です。
この場合、この「サイズ」の定義は適切ではなく、 で使用されているリストの数にする必要があると思いますA。
たとえば、すべての値が同じセルにマップされている場合、たとえば、A[1]負荷係数に従って再ハッシュすると、A実際には最初のセルのみが使用されるときにバック配列が大きくなります。
ここで私の論理に誤りがある人はいますか?
ハッシュは通常、配列インデックスに変換されるように変更されます。したがって、配列のサイズを大きくすると、要素が同じリンクリストに戻らない可能性が非常に高くなります (少なくとも、適切なハッシュ関数)。
また、負荷率の意味もかなり変わります。定義されているように、リンクされたリスト内のアイテムの平均数をある程度示します。これは非常に重要な数値です。これは、アイテムを取得するのに (平均で) かかる時間だからです。
良くも悪くも、ハッシュ テーブルは適切なハッシュの分布に基づいているため、1 つのリストが他のリストに比べて大きくなりすぎないことが想定されます。
ハッシュ関数の品質を示すために使用されるインデックスの数を格納することも意味がありますが、あまり意味がないと思います。これについて API ができることはあまりありません (ハッシュ関数を処理しないため、呼び出すだけです)。また、不適切なハッシュ関数を使用する場合、呼び出し元のコードでハッシュ関数を動的に変更することはあまり実用的ではないようです。