Offene Adressierung grob

Intermediate Algorithmen und Datenstrukturen Deutsch

Also available: English

Created by Best · 16.08.2026 at 09:13 UTC

Offene Adressierung speichert Einträge in der Tabelle selbst und sucht bei Kollision alternative Slots (linear, quadratisch, double hashing). Löschen braucht Platzhalter (tombstones).

Gute Lokalität, aber empfindlich bei hohem Füllgrad.

Strategie	Eintrag landet	Löschen
Chaining	in der Bucketstruktur	lokal in der Kette
Offenes Adressieren	in der Tabelle weiter	Tombstone nötig
## Wo gebraucht

High-Performance-Maps, einige DB-Hash-Indizes, wenn Pointer-Chase von Chaining zu teuer ist. Mehr Sondierungslogik, bessere Cache-Lokalität bei guter Last.

Vertiefung

Bei offener Adressierung liegen alle Einträge direkt im Tabellenarray. Ist der Startplatz belegt, folgt die Suche einer festgelegten Sondierungsfolge. Einfügen und Nachschlagen müssen exakt dieselbe Folge verwenden, sonst können vorhandene Schlüssel übersehen werden.

Beim Löschen wird häufig ein besonderer Marker gesetzt. Ein wirklich leerer Platz zeigt, dass ein Schlüssel entlang dieses Suchwegs nicht mehr folgen kann. Ein Löschmarker erlaubt dagegen die Fortsetzung der Sondierung und kann später bei einer Einfügung wiederverwendet werden.

Schwierigkeitsstufen

Lineares Sondieren für eine kurze Tabelle simulieren.
Leeren Platz und Löschmarker semantisch unterscheiden.
Clusterbildung und ihren Einfluss auf die Zugriffszeit erklären.

Fallstricke

Eine nahezu volle Tabelle kann sehr lange Sondierungsfolgen erzeugen. Wird beim ersten gelöschten Feld erfolglos abgebrochen, bleiben weiter hinten abgelegte Schlüssel unsichtbar.

University approvals: 0

Tasks

Question 1

Warum sind Tombstones beim offenen Adressieren nötig?

Wegen Generics

Damit Suchpfade nach Löschen nicht abbrechen

Weil Stacks voll sind

Weil Bäume balanciert sein müssen

Question 2

Eine Suche trifft nach mehreren belegten Feldern auf einen Löschmarker. Was soll sie tun?

Sofort erfolglos enden.

Den Marker als gesuchten Schlüssel zurückgeben.

Der festgelegten Sondierungsfolge weiter folgen.

Alle vorherigen Einträge löschen.

Question 3

Implementiere den i-ten linearen Sondierungsschritt ab start.

Hint

Für einen umlaufenden Index eignet sich Math.floorMod(value, capacity). So bleiben auch negative Zwischenwerte gültig.

class Probing {
  static int probeLinear(int start, int i, int capacity) {
    // TODO
    return 0;
  }
}

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

1 test case will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Algorithmen und Datenstrukturen
Difficulty: Intermediate
Completed: 0 users

Creator

Best

BestBuddy