Forums Neueste Beiträge
 

Informatik für Physiker, 5.Vorlesung ( 200 Mrd Internetadressen sortieren mit Quicksort und mit Hashverfahren )

27/05/2013 - 14:39 von Peter Müller | Report spam
Google sortiert seine Adressen mit Quicksort und mit dem Hashverfahren, für das weitere 10 Computer notwendig sind.

Andere Suchmaschinen verwenden nur Quicksort - Beispiel:

Ich habe 32 Zahlen aufgeschrieben und will euch die größte davon sagen.
Dazu muß ich mir 32*32 mal = 1024 mal diese 32 Zahlen durchlesen.

Aber Zahlen lesen ist ja nicht so schwer ...

Beim Hashverfahren werden die Zieldaten in einer Hashtabelle gespeichert. Eine Hashfunktion berechnet zu jedem Datenobjekt einen Hashwert, der als Index in der Tabelle verwendet wird. Zum Berechnen dieses Hashwertes wird ein Schlüssel benötigt, der dieses Objekt eindeutig identifiziert. Dieser Schlüssel wird von der Hashfunktion zum Berechnen des Hashwertes verwendet. Das Datenobjekt wird an einer durch den Hashwert festgelegten Stelle (englisch Bucket) in der Tabelle gespeichert. Im Idealfall bekommt jedes Objekt einen eigenen Bucket. Hashfunktionen müssen jedoch nicht eindeutig sein, so dass zwei verschiedene Objekte denselben Hashwert haben können. Diesen Fall nennt man Kollision, er benötigt eine spezielle Behandlung durch das Verfahren.
 

Lesen sie die antworten

#1 Izur Kockenhan
27/05/2013 - 15:04 | Warnen spam
Peter Müller wrote
Google sortiert seine Adressen mit Quicksort und mit dem Hashverfahren, für
das weitere 10 Computer notwendig sind.

Andere Suchmaschinen verwenden nur Quicksort - Beispiel:

Ich habe 32 Zahlen aufgeschrieben und will euch die größte davon sagen.
Dazu muß ich mir 32*32 mal = 1024 mal diese 32 Zahlen durchlesen.

Aber Zahlen lesen ist ja nicht so schwer ...

Beim Hashverfahren werden die Zieldaten in einer Hashtabelle gespeichert.
Eine Hashfunktion berechnet zu jedem Datenobjekt einen Hashwert, der als
>Index in der Tabelle verwendet wird. Zum Berechnen dieses Hashwertes wird
ein Schlüssel benötigt, der dieses Objekt eindeutig identifiziert. Dieser
>Schlüssel wird von der Hashfunktion zum Berechnen des Hashwertes
verwendet. Das Datenobjekt wird an einer durch den Hashwert festgelegten
Stelle >(englisch Bucket) in der Tabelle gespeichert. Im Idealfall bekommt
jedes Objekt einen eigenen Bucket. Hashfunktionen müssen jedoch nicht
eindeutig >sein, so dass zwei verschiedene Objekte denselben Hashwert haben
können. Diesen Fall nennt man Kollision, er benötigt eine spezielle
Behandlung >durch das Verfahren.



Algorithmen, R. Sedgewick, Addison Wesley, ISBN 3-89319-301-4

Izur Kockenhan

Ähnliche fragen