Hashing Kollisionsauflösung Prüfungsfragen

Was ist eine Kollision im Hashing?

Eine Kollision tritt auf, wenn zwei unterschiedliche Eingabewerte denselben Hashwert generieren.

Nenne eine Methode zur Kollisionsauflösung.

Offene Adressierung ist eine Methode, bei der alternative Speicheradressen gesucht werden.

Was bedeutet offene Adressierung?

Bei offener Adressierung wird die nächste verfügbare Adresse im Array verwendet, wenn eine Kollision auftritt.

Wie funktioniert das separate Chaining?

Jeder Index im Hash-Array verweist auf eine Liste, die alle Elemente mit demselben Hashwert speichert.

Wahr oder Falsch: Kollisionen sollten immer vermieden werden.

Falsch: Kollisionen können nicht vollständig vermieden werden, sie müssen behandelt werden.

Vergleiche offene Adressierung und separates Chaining.

Offene Adressierung: Speichert alle Elemente im Array. Separates Chaining: Verwaltet Kollisionen mit verlinkten Listen.

Fülle die Lücke: Bei ___ wird eine Liste verwendet, um Kollisionen zu speichern.

separates Chaining

Wie wird der Hashwert eines Schlüssels berechnet?

Durch eine Hashfunktion, die einen Schlüssel in einen Index des Hash-Arrays abbildet.

Was sind die Hauptziele der Hashing-Kollisionsauflösung?

Effizienz, Minimierung der Suche und Sicherstellung der Datenintegrität.

Nenne ein Beispiel für eine Hashfunktion.

Eine einfache Hashfunktion könnte $\displaystyle h(k) = k \bmod n$ sein, wobei $\displaystyle n$ die Array-Größe ist.

Was passiert bei einer vollen Hash-Tabelle?

Neue Elemente können nicht mehr hinzugefügt werden, dies erfordert eine Vergrößerung der Tabelle.

Wahr oder Falsch: Hashing ist immer eindeutig.

Falsch: Hashing produziert oft Kollisionen aufgrund der endlichen Anzahl von Hashwerten.

Was ist die Lastfaktor in Hash-Tabellen?

Das Verhältnis von der Anzahl der gespeicherten Elemente zur Größe der Hash-Tabelle.

Fülle die Lücke: Ein guter Hashing-Algorithmus sollte ___ sein.

gleichmäßig verteilt

Wie kann man die Effizienz von Hashing verbessern?

Durch gute Hashfunktionen und das Anpassen der Lastfaktoren.

Was sind die Auswirkungen von Kollisionen auf die Leistung?

Kollisionen erhöhen die Suche und Einfügezeiten, da zusätzliche Schritte erforderlich sind.

Was ist lineares Sondieren?

Eine Technik zur Kollisionsauflösung, bei der bei einer Kollision die nächstgelegene freie Position in der Tabelle gesucht wird.

Fill in the blank: Quadratische Sondierung nutzt ... für die Positionssuche.

quadratische Funktionen zur Bestimmung der nächsten Position.

Vergleiche lineares und quadratisches Sondieren.

Lineares Sondieren sucht nacheinander; quadratisches nutzt $\displaystyle i^2$-Distanz. Quadratisches Sondieren reduziert Clusterbildung.

Welche Technik nutzt eine separate Liste für Kollisionen?

Separate Verkettung. Kollisionen werden in einer Liste gespeichert, die mit der Hash-Tabelle verbunden ist.

True or False: Separate Verkettung verhindert Clusterbildung.

True. Sie speichert Kollisionen in Listen, was Clusterbildung minimiert.

Was ist die Hauptidee der Doppel-Hashing-Technik?

Eine zweite Hash-Funktion bestimmt die Sprünge zur Positionssuche bei Kollisionen.

Erläutere das Problem der Clusterbildung.

Clusterbildung führt zu ineffizienten Suchen, da viele aufeinanderfolgende Positionen belegt sind. Dies kann durch separate Verkettung reduziert werden.

Nenne eine Einschränkung des linearen Sondierens.

Es kann zu Clusterbildung führen, die die Leistung bei Einfügungen und Suchen verringert.

Was ist die Rolle einer Hash-Funktion?

Sie wandelt den Schlüssel in einen Index um, der für die Speicherung in der Hash-Tabelle verwendet wird.

Beispiel für Quadratische Sondierung.

Wenn $\displaystyle h(k) = 3$ und $\displaystyle h'(k) = 2$, dann überprüfe $\displaystyle 3$, $\displaystyle 4$, $\displaystyle 7$, $\displaystyle 12$ für Kollisionen.

Was ist eine ideale Hash-Funktion?

Eine Funktion, die gleichmäßige Verteilung der Indizes und minimale Kollisionen gewährleistet.

Nenne einen Vorteil der Doppel-Hashing-Technik.

Es vermindert die Clusterbildung und sorgt für größere Flexibilität bei der Suche nach freien Positionen.

Wie wird Hashing in Datenbanken verwendet?

Hashing ermöglicht schnellen Zugriff auf Datensätze, indem Schlüssel in Hash-Tabellen abgebildet werden.

Was ist eine typische Anwendung von Hash-Tabellen?

Wörterbuchimplementierungen, um Schlüssel-Wert-Paare effizient zu speichern.

Wahr oder Falsch: Hashing garantiert keine Kollisionen.

Wahr. Hashing kann jedoch durch geeignete Methoden der Kollisionsauflösung behandelt werden.

Nenne zwei Techniken zur Kollisionsauflösung.

- Separate Chaining - Open Addressing

Was ist der Unterschied zwischen Linear Probing und Quadratic Probing?

Linear Probing verwendet gleichmäßige Abstände, während Quadratic Probing quadratische Abstände nutzt.

Vervollständige: Hash-Tabellen sind besonders nützlich bei _____ .

schnellen Suchoperationen, z.B. zur Speicherung von Benutzerdaten.

Wie können Hash-Tabellen in Webanwendungen verwendet werden?

Zur Implementierung von Sitzungsmanagement oder zur Speicherung von Benutzer-Session-Daten.

Was passiert bei einer Kollision?

Zwei Schlüssel haben den gleichen Hash-Wert, wodurch eine Lösung erforderlich ist.

Warum ist die Wahl einer guten Hash-Funktion entscheidend?

Eine gut gestaltete Hash-Funktion minimiert Kollisionen und verteilt die Werte gleichmäßig.

Gib ein Beispiel für eine Hash-Funktion.

Eine einfache Hash-Funktion könnte $\displaystyle h(k) = k \bmod m$ sein, wobei $\displaystyle m$ die Größe der Tabelle ist.

Nenne einen Nachteil von Hash-Tabellen.

Speicherplatzverbrauch kann hoch sein, insbesondere bei sparsamen Daten.

Was sind die Anwendungen von Hashing in der Krypto-Analyse?

Hashing wird zur Integritätssicherung von Daten und zur Erstellung digitaler Signaturen verwendet.