Deutsch
Menü

Datenstrukturen und Algorithmen

Warum ist bei einer Hashtabelle mit vielen Elementen und einem Belegungsfaktor von etwa 0,5 die offene Adressierung mit linearem Sondieren am ehesten schneller als die Verkettung (Verbinden der Elemente durch verkettete Listen)?

  1. ANach einer Kollision wird als Nächstes das benachbarte Element geprüft, das oft in derselben oder der nächsten Cache-Line liegt; daher sind weniger Speicherzugriffe nötig
  2. BBei offener Adressierung treten überhaupt keine Kollisionen auf
  3. CBei Verkettung muss die Hashfunktion zweimal oder öfter berechnet werden
Antwort und Erläuterung anzeigen

Antwort: A. Nach einer Kollision wird als Nächstes das benachbarte Element geprüft, das oft in derselben oder der nächsten Cache-Line liegt; daher sind weniger Speicherzugriffe nötig

Auf heutigen CPUs dauert das Lesen aus dem Hauptspeicher nach einem Cache-Miss weit länger als Berechnungen wie Vergleiche. Lineares Sondieren prüft nach einer Kollision die Nachbarposition, sodass die meisten Sondierschritte in derselben Cache-Line bleiben, und auch das Prefetching hilft. Bei der Verkettung liegt das nächste Element einer Liste oft an einer anderen Stelle im Speicher, sodass jeder verfolgte Zeiger leicht einen Cache-Miss auslöst. Selbst bei gleicher Komplexität in O-Notation kann die tatsächliche Geschwindigkeit je nach Art des Speicherzugriffs stark abweichen. Lineares Sondieren wird allerdings bei hohem Belegungsfaktor stark langsamer, weil sich die belegten Positionen zusammenballen; der Belegungsfaktor wird daher eher niedrig gehalten.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Datenstrukturen und Algorithmen

  1. Für das Sortieren auf paralleler Hardware wie GPUs werden manchmal Sortierverfahren mit einer festen Folge von Vergleichs- und Tauschschritten (Sortiernetzwerke) wie Bitonic Sort verwendet. Warum?
  2. Welche Zeitkomplexität hat bei einem Array mit n Elementen ein Verfahren, das jedes Paar zweier verschiedener Elemente genau einmal vergleicht (eine doppelte Schleife, die das i-te Element mit allen dahinterliegenden Elementen vergleicht und i schrittweise erhöht)?
  3. Ein Programm mit der Zeitkomplexität O(n²) benötigt für 1000 Datenelemente 0,5 Sekunden. Wie lange benötigt es etwa für 4000 Datenelemente?
  4. Eine lineare Suche vergleicht die Elemente eines Arrays mit 100 verschiedenen Werten der Reihe nach von vorn, um einen Zielwert zu finden. Der Zielwert ist immer im Array enthalten und steht mit gleicher Wahrscheinlichkeit an jeder Position. Wie viele Vergleiche sind im Mittel nötig?
  5. Welche Aussage beschreibt eine verkettete Liste (eine Liste, in der jedes Element einen Zeiger auf das nächste Element enthält) im Vergleich zu einem Array richtig?