Startseite   |  Site map   |  A-Z artikel   |  Artikel einreichen   |   Kontakt   |  
  


informatik artikel (Interpretation und charakterisierung)

Doppeltes hashing


1. Java
2. Viren



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, daß 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 würde 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äre, 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
Logische Namen:
DSP mit Harvard-Architektur
Seitenaufteilung in Segmente - Frames
Erstellung von DFD's
Arbeitsweise eines Scanners
ZUGANGSVERFAHREN-
Beschreiben Sie das EVA-Prinzip! (Alscher Hedwig)
Datenbankmodelle, ihre Entwicklung und Bedeutung
Speichermedien mit Bild
PositiveTemperatureCoefficent





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.