0
Von Mark Weiss Datenstrukturen und Algorithmen-Analyse in C++:Was ist der schnellste Weg, um zu rehasen?
/**
* Rehashing for quadratic probing hash table.
*/
void rehash()
{
vector<HashEntry> oldArray = array;
// Create new double-sized, empty table
array.resize(nextPrime(2 * oldArray.size()));
for(auto & entry : array)
entry.info = EMPTY;
// Copy table over
currentSize = 0;
for(auto & entry : oldArray)
if(entry.info == ACTIVE)
insert(std::move(entry.element));
}
Es scheint wie eine wirklich schmerzhafte Operation der durch jedes Element in der Tabelle zu gehen, und wenn das Element zu sehen, die Überprüfung aktiv ist oder nicht. Gibt es eine Implementierung, bei der nur die Anzahl der Elemente (im Gegensatz zur gesamten Tabelle) durchlaufen wird?
Eine verknüpfte Hash-Struktur (bei der Einträge auch als doppelt verknüpfte Liste verknüpft sind) ermöglicht Ihnen, die Elemente und nicht die gesamte Tabelle direkt zu durchlaufen (und die Tabelle in Einfügereihenfolge anstelle einer beliebigen Reihenfolge zu durchlaufen)). Funktioniert das? – ShadowRanger
Würde dies in einem geschlossenen Hash-Szenario funktionieren (mein Ziel)? Als Referenz: Open Hashing (Separate Verkettung): Beim offenen Hashing werden Schlüssel in verknüpften Listen gespeichert, die an Zellen einer Hash-Tabelle angehängt sind. Closed Hashing (Open Addressing): In geschlossenem Hashing werden alle Schlüssel in der Hash-Tabelle selbst ohne die Verwendung von verketteten Listen gespeichert. – blueman
Sie müssen nur dann erneut anzeigen, wenn die Anzahl der eingefügten Elemente mindestens die Hälfte der Größe der Tabelle beträgt. Daher ist es nicht kostspielig, alle Tabellenzellen zu überprüfen. –