5

C++でHashtableクラスを実装しています。私が使用している衝突解決方法は、レイジー削除を使用した線形プロービングです。私はこれの実装を見てきましたが、insertメソッドに関して質問がありました。ハッシュテーブルの各セルには、状態（アクティブ、削除済み、空）があります。何らかの理由で、新しい要素を挿入するときに見た実装では、キーをハッシュしてから、EMPTYセルが見つかるまで（または同じキーが既に含まれているセルが見つかるまで）テーブルをプローブします。

サンプルコード：

int findPos(const string &key){
     int currentPos=hash(key);
     while(data[currentPos].state!=EMPTY && data[currentPos].key!=key){
         currentPos++;
         if (currentPos>=data.size())
            currentPos-=data.size()
         }
      return currentPos;
}

bool insert(const string &key){
     int currentPos=findPos(key);
     if (isActive(currentPos))
          return false; //already exists
     data[currentPos]=hashEntry(key,ACTIVE);
     if (++currentSize>data.size()/2)
          rehash();
     return true;   //element inserted
}

私の質問は、削除済みとしてタグ付けされたセルに停止して挿入しない理由はありますか？つまり、このfindPosメソッドでは、whileステートメントをに変更しwhile(data[currentPos].state==ACTIVE && data[currentPos].key!=key)て、キーのあるセルまたは最初に削除された/空のセルが見つかったときにループが終了するようにします。次に、挿入で、セルの状態をテストします。アクティブな場合、エントリはすでに存在するため、falseを返します。それ以外の場合は、要素を挿入します。

4

2 に答える 2

3

キーはさらに挿入された可能性があり、後で介在するセルの 1 つが削除済みとしてマークされた可能性があります。次に、同じキーの重複インスタンスを挿入します。

于 2012-09-16T16:47:38.093 に答える
0

おそらく参照コードに遅延削除がなかったか、既存の実装に DELETED 状態が追加されました。はい、キーのエントリを安全に「元に戻す」ことができます。ただし、@ Thomas の回答で説明されている状況を回避するために、このアルゴリズムが一貫して使用されていることを確認してください。

于 2012-09-16T18:04:59.787 に答える