Sofortiges vs. inkrementelles Kopieren in dynamischer Hashtabelle Größenänderung

Question

Was sind die Vor- und Nachteile von jedem? Wenn ich eine Hash-Tabelle implementiere, in der die schnelle Nachschlagezeit von entscheidender Bedeutung ist, scheint es, als ob ich sofort verwenden sollte, da dies nur bei Einfügungen und Löschungen auftreten würde, während inkrementelle auch die Suche verlangsamen würde. Ist das sinnvoll?

Ich mache das in C, wenn es darauf ankommt.

Answer 1

Wenn Sie keine engen Zeitbeschränkungen für jede Hash-Tabellenoperation haben, ist eine Größenänderung sofort wahrscheinlich am sinnvollsten. Wie Sie sagen, verbessert es die Nachschlagezeiten gegenüber der inkrementellen Größenanpassung und im Allgemeinen amortisieren sich die Kosten für das Einfügen und Löschen. Die inkrementelle Größenanpassung ist in Fällen anwendbar, in denen alle Operationen in einem festen und streng begrenzten Zeitraum ablaufen müssen.