0

Java でハッシュテールを実装しましたが、コードを最適化する必要があります。私は多くのループをしなければならないと思います。ループの数を「減らす」にはどうすればよいですか? 問題は、要素を削除すると、テーブルを再ハッシュする必要があり、delete() と put() の間にたてがみホップがあることです。これは学校の演習であるため、コード例は必要ありません。ガイダンスだけです:)

ありがとうございました

これが私の機能です：

public void put(String key, Character val) {
    int hashValue = hash(key); 

    if(val == '\r'){
        delete(key); 
    }
    else {
    while(keys[hashValue] != null) {
        if(keys[hashValue].equals(key)) {
            break; 
        }
        hashValue = (hashValue + 1) % M ;  

    }

    keys[hashValue] = key ; 
    vals[hashValue] = val; 
    N++; 
  }
} 

public Character get(String key) {

    int hashValue = hash(key); 
    while(keys[hashValue] != null) {
        if(keys[hashValue].equals(key)){
            return vals[hashValue]; 
        }
        hashValue = (hashValue+1) % M; 
    }
    return null; 
} 

public void delete(String key) {

     int hashValue = hash(key) ; 

     String tempkey; 
     Character tempval; 
     boolean deleted = false; 

     while(keys[hashValue] != null){
         if(keys[hashValue].equals(key)){
             keys[hashValue] = null; 
             vals[hashValue] = null;
             deleted = true;  
             N--; 
             if(keys[(hashValue + 1) % M] == null){ 
                 break; 
             }
         }
         else if(deleted = true){
             tempkey = keys[hashValue]; 
             tempval = vals[hashValue]; 

             keys[hashValue] = null; 
             vals[hashValue] = null; 
             N--; 
             put(tempkey, tempval); 
         }

         hashValue = (hashValue +1) % M; 

     }

    return;
}
4

1 に答える 1

0

まあ、やろうとしていることのデザインを再考する必要があると思います。具体的には衝突。値を次のバケットに移動することで、衝突 (同じハッシュコードを持つ 2 つの値) を解決しようとしているようです。追加と削除を繰り返すと、キーがテーブルのどこかにないことを確認する方法がありません。

リンクされたリストのテーブルとしてハッシュテーブルを設計したい場合があります。こうすることで、衝突するエントリが正しいセルから始まるリンク リストに配置されます。適切なハッシュ関数 (キー空間全体に均一に近いキーを分散する関数) を使用すると、衝突の数は最小限になります。

幸運を！

于 2012-10-16T14:51:18.620 に答える