Algorithmen und Datenstrukturen · Senior · Frage 54 von 75
Wie viele Vergleiche erwartet man bei erfolgreicher Suche in einer Hashtabelle mit Verkettung und Füllfaktor α?
- 1Genau α²
- 2Etwa log α
- 3Etwa 1 + α/2
Antwort zeigen
Richtige Antwort: Etwa 1 + α/2
Erklärung
Bei gleichmäßigem Hashing hat eine Kette im Schnitt α Elemente, und eine erfolgreiche Suche durchläuft etwa die Hälfte. Deshalb halten Tabellen α unter einer Konstante wie 0,75: Suchen bleiben wenige Vergleiche lang.