Hashing und Kollisionen
2005-03-13 15:33
Morpheus
Moin,
ich lern grad n bissi was für meine p2-p3 prüfung und bin da über ein was sehr verwirrendes gestoplpert. und zwar hat prof. neumann ne frage-antwort pdf als übung für die prüfung ins net gestellt. ich weiss jetzt nich mehr wo genau, aber zu hashing und kollisionen schreibt er:
geschlossenes hashing: behälter kann nur konstante zahl von schlüsseln aufnehmen, und bei kollision werden die daten in mehreren behältern umgelagert mit der hilfe einer neuen hashfunktion
offenes hashing: behälter kann beliebig viele schlüssel aufnehmen
nur hab ich jetzt folgendes bei wikipedia gefunden, was ja eigentlich recht zuverlässig ist…
Geschlossenes Hashing
Beim geschlossenem Hashing ist die Hash-Tabelle so strukturiert, dass jeder Behälter eine dynamische Datenstruktur aufnehmen kann - beispielsweise auf eine Liste oder einen Baum. Jeder Schlüssel wird dann in dieser Datenstruktur eingetragen oder gesucht. So ist es problemlos möglich, mehrere Schlüssel in einem Behälter abzulegen, was allerdings zu mehr oder weniger verlängerten Zugriffszeiten führt. Die Effizienz des Zugriffs wird dabei davon bestimmt, wie schnell Datensätze in die gewählte Datenstruktur eingefügt und darin wiedergefunden werden können.
Offenes Hashing
Beim offenen Hashing kann jedem Behälter nur eine feste Anzahl von Schlüsseln zugewiesen werden. Häufig wählt man einfach einen einzigen möglichen Schlüssel pro Behälter. Im Kollisionsfall muss dann nach einem alternativen Behälter gesucht werden. Dabei geht man so vor, dass man für m Behälter eine ganze Folge von m Hash-Funktionen definiert. Führt die Anwendung der ersten Hash-Funktion, nennen wir sie h0, zu einer Kollision, so wendet man h1 an. Führt diese ebenfalls zu einer Kollision (d.h. der entsprechende Behälter ist bereits belegt), so wendet man h2 an, und so weiter bis hm − 1. Das Verfahren arbeitet mit sogenannter offener Adressierung, da durch Kollisionen gleiche Schlüssel unterschiedliche Adressen zugewiesen bekommen können.
Welche version entspricht den der wahrheit, kann mich da ma jemand auklären? danke im vorraus
ich lern grad n bissi was für meine p2-p3 prüfung und bin da über ein was sehr verwirrendes gestoplpert. und zwar hat prof. neumann ne frage-antwort pdf als übung für die prüfung ins net gestellt. ich weiss jetzt nich mehr wo genau, aber zu hashing und kollisionen schreibt er:
geschlossenes hashing: behälter kann nur konstante zahl von schlüsseln aufnehmen, und bei kollision werden die daten in mehreren behältern umgelagert mit der hilfe einer neuen hashfunktion
offenes hashing: behälter kann beliebig viele schlüssel aufnehmen
nur hab ich jetzt folgendes bei wikipedia gefunden, was ja eigentlich recht zuverlässig ist…
Geschlossenes Hashing
Beim geschlossenem Hashing ist die Hash-Tabelle so strukturiert, dass jeder Behälter eine dynamische Datenstruktur aufnehmen kann - beispielsweise auf eine Liste oder einen Baum. Jeder Schlüssel wird dann in dieser Datenstruktur eingetragen oder gesucht. So ist es problemlos möglich, mehrere Schlüssel in einem Behälter abzulegen, was allerdings zu mehr oder weniger verlängerten Zugriffszeiten führt. Die Effizienz des Zugriffs wird dabei davon bestimmt, wie schnell Datensätze in die gewählte Datenstruktur eingefügt und darin wiedergefunden werden können.
Offenes Hashing
Beim offenen Hashing kann jedem Behälter nur eine feste Anzahl von Schlüsseln zugewiesen werden. Häufig wählt man einfach einen einzigen möglichen Schlüssel pro Behälter. Im Kollisionsfall muss dann nach einem alternativen Behälter gesucht werden. Dabei geht man so vor, dass man für m Behälter eine ganze Folge von m Hash-Funktionen definiert. Führt die Anwendung der ersten Hash-Funktion, nennen wir sie h0, zu einer Kollision, so wendet man h1 an. Führt diese ebenfalls zu einer Kollision (d.h. der entsprechende Behälter ist bereits belegt), so wendet man h2 an, und so weiter bis hm − 1. Das Verfahren arbeitet mit sogenannter offener Adressierung, da durch Kollisionen gleiche Schlüssel unterschiedliche Adressen zugewiesen bekommen können.
Welche version entspricht den der wahrheit, kann mich da ma jemand auklären? danke im vorraus