Estoy implementando una clase Hashtable en C++. El método de resolución de colisión que estoy usando es un sondeo lineal con eliminación diferida. He visto implementaciones de esto, pero tenía una pregunta con respecto al método de inserción. Cada celda de la tabla hash tiene un estado (activo, eliminado, vacío). Por alguna razón en la implementación que he visto al insertar un nuevo elemento, ellos oprimen la tecla y luego sondean la tabla hasta que se encuentra una celda VACÍA (o hasta que se encuentre una celda que ya contenga la misma clave).Implementando hashtables en C++ (inserción y eliminación diferida)
Código Ejemplo:
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
}
Mi pregunta es: ¿Hay alguna razón para no parar y insertar en una célula que ha sido etiquetado como eliminado? En otras palabras, en el método findPos, ¿por qué no cambiar la instrucción while al while(data[currentPos].state==ACTIVE && data[currentPos].key!=key) para que el bucle finalice cuando encontremos la celda con la clave o la primera celda eliminada/vacía? Luego, en el inserto, prueba el estado de la celda. Si está activo, la entrada ya existe, así que devuelve falso; otra parte inserte el elemento.