Deutsch
Menü

Datenstrukturen und Algorithmen

Welche Aussage beschreibt eine Kollision in einer Hashtabelle richtig?

  1. AAus dem Hashwert lässt sich der ursprüngliche Schlüssel ermitteln
  2. BVerschiedene Schlüssel ergeben denselben Hashwert (dieselbe Speicherposition)
  3. CDerselbe Schlüssel ergibt bei jeder Programmausführung einen anderen Hashwert
Antwort und Erläuterung anzeigen

Antwort: B. Verschiedene Schlüssel ergeben denselben Hashwert (dieselbe Speicherposition)

Eine Hashtabelle berechnet mit einer Hashfunktion aus dem Schlüssel eine Speicherposition und ermöglicht so Suchen, Einfügen und Löschen im Mittel in O(1). Da es weit mehr mögliche Schlüssel als Tabellenplätze gibt, lässt es sich nicht vermeiden, dass verschiedene Schlüssel auf dieselbe Position fallen (Kollision). Kollisionen werden daher mit Verfahren wie der Verkettung (Chaining), die die Elemente derselben Position zu einer Liste verbindet, oder der offenen Adressierung, die eine andere freie Position sucht, behandelt. Derselbe Schlüssel muss immer denselben Hashwert ergeben, sonst würde die Suche scheitern; ob sich der Schlüssel aus dem Hashwert zurückgewinnen lässt, ist eine Eigenschaft, die bei kryptografischer Verwendung zählt, und hat mit Kollisionen nichts zu tun.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Datenstrukturen und Algorithmen

  1. In einer Hashtabelle der Größe 7 (Positionen 0 bis 6) werden mit der Hashfunktion h(k) = k mod 7 die Schlüssel 10, 17, 24 und 3 in dieser Reihenfolge gespeichert. Kollisionen werden durch lineares Sondieren aufgelöst, das jeweils eine Position weiterrückt (nach 6 folgt 0), bis ein freier Platz gefunden ist. An welcher Position wird der Schlüssel 3 gespeichert?
  2. 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.
  3. Welche Voraussetzung muss erfüllt sein, um die binäre Suche zu verwenden, die den Zielwert mit dem mittleren Element vergleicht und den Suchbereich jedes Mal halbiert?
  4. Auf 1000 verschiedene, aufsteigend sortierte Werte wird eine binäre Suche angewendet. Ein Vergleich liefert jeweils „gleich“, „kleiner“ oder „größer“. Wie viele Vergleiche sind höchstens nötig, erfolgreiche und erfolglose Suchen zusammengenommen?
  5. Eine binäre Suche sucht 38 im aufsteigend sortierten Array a[0] bis a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60. Der Suchbereich beginnt mit lo = 0 und hi = 9, und die mittlere Position ist (lo + hi) ÷ 2 abgerundet. Welche Folge gibt die Elemente, die mit 38 verglichen werden, in der richtigen Reihenfolge an?