Suchalgorithmus

Angebote / Angebote:

Quelle: Wikipedia. Seiten: 33. Kapitel: Minimax-Algorithmus, Lineare Suche, String-Matching-Algorithmus, Binäre Suche, Hashtabelle, Knuth-Morris-Pratt-Algorithmus, Alpha-Beta-Suche, Rabin-Karp-Algorithmus, Grover-Algorithmus, Suchverfahren, Interpolationssuche, Boyer-Moore-Algorithmus, Dichtestes Punktpaar, Baeza-Yates-Gonnet-Algorithmus, Gottes Algorithmus, Bergsteigeralgorithmus, Null-Zug-Suche, Pattern Matching, Heuristik von Curtis, Powell und Reid, Proof-Number-Suche, Bidirectional Best Hits, Geometrische Suche, Aho-Corasick-Algorithmus, Rapidly-exploring random tree, Quadratische Binärsuche, Suchraum. Auszug: In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen stehen dabei in Konkurrenz zu Baumstrukturen (wie etwa ein B+-Baum) und der Skip-List, die ebenfalls als Indexstruktur dienen können. Beim Einsatz einer Hashtabelle zur Suche in Datenmengen spricht man auch von einem Hashverfahren oder Streuspeicherverfahren. Das Hashverfahren ist ein Algorithmus zum Suchen von Datenobjekten in großen Datenmengen. Es basiert auf der Idee, dass eine mathematische Funktion die Position eines Objektes in einer Tabelle berechnet. Dadurch erübrigt sich das Durchsuchen vieler Datenobjekte, bis das Zielobjekt gefunden wurde. 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 (Bucket genannt) 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. Bei einer Suche in der Hashtabelle wird nun ähnlich vorgegangen. Zunächst wird aus einem Suchschlüssel wieder ein Hashwert berechnet, der den Bucket des gesuchten Datenobjektes bestimmt. Falls es zu einer Kollision gekommen ist, muss jetzt nur noch durch direkten Vergleich des Suchschlüssels mit den Objekten das gesuchte Ziel bestimmt werden. In der Praxis wird die Tabelle als ein Array implementiert. Wegen der möglichen Kollisionen werden di