1

データ構造とアルゴリズムの実験問題の一部として、共謀を避けるために、基になるデータ構造として CustomLinkedList[] を持つ Customhashtable を作成しようとしました (別のチェーン)。返されるインデックスが新しいサイズと同じになるように、以前の内容をサイズを増やした新しい配列にマップするには、サイズ = 100 でハッシュするコード

public int arrayIndex(String key)
{
   int index = key.charAt(0);

   for(int j = 1;j<key.length;j++)
     {
        int temp = key.charAt(j);
         index = ((index*27)+temp)%100;
     }
}
4

2 に答える 2

1

基本的に、新しいハッシュテーブルを作成し、すべてのデータを古いものから新しいものに移行します。負荷係数は、新しい (より大きな) テーブルを作成するタイミングを通知するトリガーです。つまり、新しいハッシュテーブルの開始配列がより大きくなります。

（楽しみのために）「最小負荷係数」設定を追加することもできます。これにより、より小さなハッシュテーブルが構築されます。最小および最大の負荷係数を持つソリューションでは、最初のバッキング アレイ (ハッシュがフォームを選択する唯一の部分) は、格納されたアイテムの数に基づいてサイズを概念的に調整します。サイズはパフォーマンスに関連するため、これにより、ハッシュテーブルは常に許容範囲のパフォーマンスを維持できます (メモリフットプリントを拡大および縮小することにより)。

負荷率の計算まで

  (in the store routines)

  if (array[index] == null) {
    loadCount++;
  }
  if (loadCount / arraySize > maxLoad) {
    resizeUp(...);
  }

  (in the remove routines)
  if (array[index] is cleared to null) {
    loadCount--;
  }
  if (loadCount / arraySize < minLoad) {
    resizeDown(...);
  }
于 2013-07-11T18:00:37.397 に答える
0

単純な実装では、ハッシュ テーブルのバッキング配列のサイズを大きくすると、格納されているすべての要素のインデックスが変更され、リンクされたリストから要素を削除する必要があります。新しいマップの同じバケット。

たとえば、もともとバッキング配列は次のとおりです。

0: [ A ]
1: [ ]
2: [ B, C ]
3: [ D ]

次に、バッキング配列を増やすと、次のようになる可能性があります。

0: [ ]
1: [ ]
2: [ C ]
3: [ ]
4: [ D ]
5: [ A ]
6: [ ]
7: [ B ]

バッキング配列の各アイテムは、新しいバケットに属しているため、ハッシュとモジュロを再計算する必要があります。特定のバッキング配列サイズを使用する場合、この再計算またはマッピングを行うためのより最適な方法がある可能性があり、既存のハッシュ テーブルの実装を調べて、それらが何を行うかを確認できます (つまり、java.util.HashMap のソースはすぐに利用できます)。ただし、一般に、すべての要素を正しいバケットに移動する必要があります。

于 2013-07-11T18:12:01.577 に答える