5
私はC++でHashtableクラスを実装しています。 私が使用している衝突解決方法は、レイジー削除による線形プロービングです。 私はこれの実装を見てきましたが、挿入メソッドに関して質問がありました。 ハッシュテーブルの各セルには、状態（アクティブ、削除、空）があります。何らかの理由で、新しい要素を挿入する際に、キーをハッシュしてから、EMPTYセルが見つかるまで（またはすでに同じキーが入っているセルが見つかるまで）、テーブルを調べます。C++でのハッシュテーブルの実装（挿入と遅延の削除）
コード例：
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を返します。それ以外の場合は要素を挿入します。