Welche Aussage vergleicht die Verkettung (Chaining: Elemente derselben Position werden in einer verketteten Liste verbunden) und die offene Adressierung (eine andere freie Position innerhalb der Tabelle wird gesucht) als Verfahren zur Kollisionsauflösung in Hashtabellen richtig? Der Belegungsfaktor ist die Zahl der gespeicherten Elemente geteilt durch die Tabellengröße.

Antwort: A. Mit Verkettung lassen sich auch bei einem Belegungsfaktor über 1 Elemente speichern; bei offener Adressierung können nicht mehr Elemente gespeichert werden, als die Tabelle groß ist, und die Zahl der Sondierschritte steigt stark an, wenn sich der Belegungsfaktor 1 nähert

Die Verkettung verbindet die Elemente derselben Position zu Listen und kann daher mehr Elemente speichern, als die Tabelle groß ist; die mittlere Listenlänge wächst aber proportional zum Belegungsfaktor und mit ihr der Suchaufwand. Die offene Adressierung speichert alles innerhalb der Tabelle und fasst daher höchstens so viele Elemente, wie die Tabelle groß ist; die Zahl der Sondierschritte bis zu einem freien Platz steigt stark an, wenn sich der Belegungsfaktor 1 nähert. Bei beiden Verfahren ist es üblich, die Tabelle zu vergrößern und alle Elemente neu einzufügen (Rehashing), sobald der Belegungsfaktor einen gewählten Grenzwert wie etwa 0,5 bis 0,75 überschreitet. Auch bei offener Adressierung treten Kollisionen auf; sie werden durch die Suche nach einer freien Position behandelt.