Immediate vs. inkrementelles Kopieren in dynamischen Hash Table Resize

Question

Was sind die Vor- und Nachteile der einzelnen? Wenn ich eine Hash-Tabelle Implementierung, wo schnelles Nachschlagen Zeit von entscheidender Bedeutung ist, wie es scheint, sollte ich sofort verwenden, weil das nur auf Einfügungen und Löschungen auftreten würde, während inkrementelle nach unten Lookup auch verlangsamen würde. Ist das sinnvoll?

Ich tue dies in C, wenn es darauf ankommt.

Answer 1

Wenn Sie Zeitdruck auf jeder Hash-Tabelle Operation haben, Ändern der Größe macht sofort wohl am meisten Sinn. Wie Sie sagen, wird es Lookup-mal über inkrementelle Redimensionierung verbessern, und nur allgemein die Kosten für das Einfügen und Löschen amortisieren. Inkrementelle Redimensionierung ist anwendbar auf Fälle, in denen alle Operationen haben in einer festen und streng begrenzte Menge an Zeit, um fortzufahren.