Startseite   |  Site map   |  A-Z artikel   |  Artikel einreichen   |   Kontakt   |  
   
  •  
    Biologie
    Themen der Chemie
    Deutsch online artikel
    Englisch / Englische
    Franzosisch
    Geographie
    Geschichte
    Informatik
    Kunst
    Mathematik / Studium
    Musik
    Philosophie
    Physik
    Recht
    Sport
    Wirtschaft & Technik



    Biographie

    Impressum

informatik artikel (Interpretation und charakterisierung)

Suche

Design

Methoden zur kollisionsbehandlung


1. Java
2. Viren



Durch die Verwendung einer Hash-Funktion kann es vorkommen, daß mehreren verschiedenen Schlüsseln ein und dieselbe Adresse zugewiesen wird. Die Behandlung solcher Kollisionen kann auf verschiedenste Art und Weise geregelt werden.

2.1 Getrennte Verkettung

Bei der getrennten Verkettung wird für jede Tabellenadresse eine verkettete Liste erzeugt, die jene Datensätze enthält, deren Schlüssel auf diese Adresse abgebildet werden.



Beispiel:





Da die Schlüssel, die auf ein und dieselbe Tabellenposition abgebildet werden, in einer verketteten Liste abgelegt werden, können sie ebensogut geordnet gespeichert werden. Diese Methode führt zu einer Verallgemeinerung des elementaren Listensuchverfahrens. Anstatt eine einzige Liste mit einem Listenkopf zu führen, werden bei der getrennten Verkettung M Listen mit M Listenköpfen geführt.

Allgemein gilt: Eine getrennte Verkettung verringert die Anzahl der Vergleiche bei einer sequentiellen Suche durchschnittlich um den Faktor M. Es wird jedoch zusätzlicher Platz für die Verkettungen beansprucht.

Bei einer Implementation der getrennten Verkettung wird für M gewöhnlich ein relativ kleiner Wert gewählt, damit kein großer zusammenhängender Speicherbereich belegt wird. Doch es ist sicher am besten, M genügend groß zu wählen, so daß die Listen kurz genug sind, damit die sequentielle Suche zur effizientesten Methode wird.
Als Faustregel gilt, M sollte etwa einem Zehntel der zu erwarteten Schlüssel entsprechen, so daß die Listen durchschnittlich je zehn Schlüssel enthalten.
Falls mehr Schlüssel als erwartet auftreten, dauern die Suchvorgänge ein wenig länger, bei weniger Schlüssel wurde vielleicht etwas mehr Speicherplatz verwendet.


2.2 Offene Adressierung

Falls die Anzahl der Elemente, die in die Hash-Tabelle aufgenommen werden sollen, im voraus geschätzt werden kann, und falls ausreichend zusammenhängender Speicherplatz zur Verfügung steht, um alle Schlüssel aufzunehmen und noch zusätzlich Platz zu lassen, dann lohnt es sich nicht, irgendwelche Verkettungen zu verwenden.
Bei der offenen Adressierung wird im Kollisionsfall der Adreßbereich entweder in konstanten oder in quadratisch ansteigenden Abständen nach freiem Speicherplatz durchsucht.


2.2.1 Lineares Austesten

Die einfachste Methode mit offener Adressierung wird lineares Austesten genannt. Im Falle einer Kollision wird einfach die nächste Position in der Hash-Tabelle untersucht. Ist diese leer, können die Daten dort gespeichert werden. Wenn auch diese Position belegt ist, wird wieder die nächste Position untersucht, solange bis eine leere Position erreicht wurde.


Beispiel:





Der Umfang der Tabelle für lineares Austesten ist größer als für getrennte Verkettung, doch die Gesamtgröße des verwendeten Speicherplatzes ist geringer, da keine Verkettungen benutzt werden.

Allgemein gilt: Für eine Hash-Tabelle, die zu weniger als zwei Dritteln gefüllt ist, erfordert lineares Austesten im Durchschnitt weniger als fünf Tests.



2.2.2 Doppeltes Hashing

Da beim linearen Austesten auch andere Schlüssel untersucht werden, speziell dann, wenn sich die Tabelle zu füllen beginnt, kann das eine drastische Erhöhung der Suchzeit bewirken. Solche Anhäufungen sorgen dafür das lineares Austesten für fast volle Tabellen sehr langsam abläuft.

Mit Hilfe des doppelten Hashing kann dieses Problem praktisch beseitigt werden. Beim Hash-hash-Verfahren wird im Kollisionsfall zur Suche eines freien Speicherplatzes wieder eine Hash-Funktion verwendet, die sich von der ersten unterscheiden sollte auftreten würde. Ansonsten ist dieses Verfahren das geeignetste, um die Anzahl der Kollisionen gering zu halten.

Für das folgende Beispiel wurde folgende Funktion als zweite Hash-Funktion verwendet:

h2 = 8 - (k mod 8).


Beispiel:




Allgemein gilt: Doppeltes Hashing erfordert im Durchschnitt weniger Tests als lineares Austesten.


Methoden der offenen Adressierung können in einer dynamischen Situation, bei der eine nicht vorhersagbare Anzahl von Einfüge- und Löschoperationen auszuführen sind, unzweckmäßig sein. Es muß beim Löschen mit Vorsicht vorgegangen werden, da ein Datensatz nicht einfach aus einer Tabelle entfernt werden kann, die mit Hilfe von linearem Austesten oder doppeltem Hashing erzeugt wurde. Es wurde eine Lücke entstehen, die bei der Suche nach einem anderen Datensatz dazu führt, daß an dieser Stelle abgebrochen wird, anstatt weiterzusuchen. Eine Lösung dieses Problems währe, spezielle Platzhalter zu verwenden.
Zu beachten ist, daß bei der getrennten Verkettung das Löschen eines Datensatzes kein besonderes Problem darstellte.

Die Wahl der besten Hashing-Methode für eine spezielle Anwendung kann sehr kompliziert sein. Im allgemeinen besteht die beste Strategie darin, die Methode der einfachen getrennten Verkettung anzuwenden, um die Suchzeit stark zu verkürzen, wenn die Anzahl der zu verarbeitenden Datensätze nicht im voraus bekannt ist, und doppeltes Hashing zu verwenden, um eine Menge von Schlüsseln zu suchen, deren Größe im voraus grob angegeben werden kann.

 
 




Datenschutz

Top Themen / Analyse
Applets: Animation und Interaktion im WWW
Kaskadiertes FIR-Filter
Virtuelle Methoden -
Die Subtraktionsbefehle
Distribution Counting
Der Pentium ist tot, es lebe der Pentium
TFT-Display
ISOIOSI
Anwendungsbereiche von Computern
Was sind Pager?





Datenschutz

Zum selben thema
Netzwerk
Software
Entwicklung
Windows
Programm
Unix
Games
Sicherheit
Disk
Technologie
Bildung
Mp3
Cd
Suche
Grafik
Zahlung
Html
Internet
Hardware
Cpu
Firewall
Speicher
Mail
Banking
Video
Hacker
Design
Sprache
Dvd
Drucker
Elektronisches
Geschichte
Fehler
Website
Linux
Computer
A-Z informatik artikel:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z #

Copyright © 2008 - : ARTIKEL32 | Alle rechte vorbehalten.
Vervielfältigung im Ganzen oder teilweise das Material auf dieser Website gegen das Urheberrecht und wird bestraft, nach dem Gesetz.