サイズ変更後にハッシュテーブルの古い要素が見つかりませんか？

Question

私は自分のデータ構造体クラスのために私自身のハッシュテーブルadtを作成しており、問題を横切って実行しています。私は（キー、値）をハッシュ私のハッシュテーブルのエントリには、以下の機能を使用（キーは文字列であり、値は任意のデータ型を指定でき、それは一般的なもの）：への挿入をプロービングリニアを使用して

private int hashCode(String key) 
{ 
    final int constant = 37; 
    int hash = 0; 

    for(int i=0;i<key.length();i++) 
    { 
     hash+=(int)key.charAt(i) * Math.pow(constant,i); 
    } 
    return hash; 
} 
private int hash(String key) 
{ 
    return hashCode(key) % capacity 
} 

テーブルはうまく動作しますが、テーブルを展開することを選択した場合、容量が変更されているのでハッシュテーブルのget（キー）操作でハッシュ（キー）関数が適切に機能しませんそれが正しくマップされたテーブル拡張）。これを編集する簡単な方法はありますか？これは、2の係数を使ってハッシュテーブルの拡張を考慮に入れます。つまり、loadfactor> 0.5の場合は、テーブルを2 *容量増加させます。

Answer 1

一般に、ハッシュテーブルを再ハッシュするときは、ハッシュテーブル内のすべての要素を繰り返し処理し、ハッシュコードに基づいて再配置して適切な場所に配置する必要があります。通常はサイズを変更するよりも少し時間がかかりますが、それ以外の場合はテーブルが正しく機能しません。

代わりに、extendible hashingなどの異なる衝突解決スキームを使用することがあります。これは、配置後に物を移動させないように特別に作成されていますが、実際には盲目的に速い線形プロービングハッシュがどのようにしているかを考えれば、それに値するものではありません。