Hash-Tabellen verwenden, wenn das Array vollständig gefüllt ist, was die bestmögliche Methode/das beste Szenario ist, das wir in Big-O (1) einfügen können ... erklären Sie mich im Detail.In welchem Szenario haben wir in Big-O (1) eingefügt, wenn das Array voll ist?
Wenn das Array vollständig gefüllt ist (was es niemals sein sollte [Edit: caveat, siehe Kommentare]), ist es unmöglich etwas einzufügen, ohne es zu erweitern, was in O (1) nicht möglich ist Zeit. Es sei denn, Sie meinen amortisiert O (1) Zeit. Aber in jedem Fall ist es das beste Verfahren, das Array nicht vollständig ausfüllen zu lassen, bevor es expandiert wird, da sich dann alle Operationen auf O (n) Zeit verschlechtern.
* "sollte nie erlaubt sein", dann ist es unmöglich "* - das gilt für geschlossenes Hashing (aka" offene Adressierung "), aber nicht wahr für offenes Hashing (auch bekannt als" separate Verkettung "). –
Richtig, ich nahm von der Formulierung des Posters an, dass wir über offene Adressierung sprachen. Aber auch bei der Verkettung ist es normal, dass nicht alle Slots gefüllt werden. – njlarsson
Ich erkenne jetzt, dass die beabsichtigte Antwort auf die (Hausaufgaben?) Frage darin liegt, * nicht * zu interpretieren, wie ich es gemacht habe. Ich werde darauf verzichten, das weiter zu erklären. – njlarsson
Ich stimme diese Frage als off-topic zu schließen, weil es von Hausaufgaben schmatzt und nicht respektiert Punkt 3 bei http://stackoverflow.com/help/on-topic –
Die Frage Beschreibung ist nicht sehr gut und Es ist nicht leicht herauszufinden, was du verlangst. Ich denke, Sie möchten ein Element in Hash-Tabelle einfügen, die mit Array implementiert wird, aber das ist nicht klar angegeben. –