Algorithmen und Datenstrukturen · Middle · Frage 53 von 75
Was passiert mit einer Hashtabelle, wenn ihr Füllfaktor zu hoch wird?
- 1Sie vergrößert das Array und fügt alle Einträge neu ein (Rehashing)
- 2Sie wechselt zu einem sortierten Array mit binärer Suche
- 3Sie lehnt neue Schlüssel ab, bis einige gelöscht sind
Antwort zeigen
Richtige Antwort: Sie vergrößert das Array und fügt alle Einträge neu ein (Rehashing)
Erklärung
Der Füllfaktor ist die Zahl der Einträge geteilt durch die Buckets. Überschreitet er eine Schwelle, werden Kollisionen häufig, also wächst die Tabelle, meist auf das Doppelte. Rehashing ist O(n), aber selten, Einfügen bleibt also amortisiert O(1).