Beim Hashing wird mit Hilfe einer surjektiven Funktion das Universum auf einen kleineren Speicher abgebildet.

Verschiedene Hashfunktionen

Modulofunktion: $x\,\,mod\,\,y$ wobei die Größe des Hashspeichers ist
Mittelquadrat: Die Speicheradresse wird quadriert. Danach werden aus der quadrierten Zahl in der Mitte Ziffern herausgenommen: Beispiel: $128^{2}=16\underline{38}4\Rightarrow 38$
Multiplikationsmethode: Die Zahl wird mit einer irrationalen Zahl zwischen multipliziert. Danach erhalten wir eine Orignial+d-bittige Zahl. Die letzten d Bits werden als Speicheradresse für den Hash verwendet.

Offenes Hashing mit Kollisionslisten

Wenn es Kollisionen gibt, dann werden an den Hashspeicher Listen angehängt, in denen Elemente gespeichert werden, die nicht mehr in den normalen Speicher passten, weil diese schon besetzt war.

Geschlossenes Hashing mit offener Adressierung

Beim geschlossenen Hashing mit offener Adressierung wird bei belegten Hashspeicherplätzen mittels anderer Hashfunktionen auf andere Speicherplätze ausgewichen.

Schon einmal berechnete Ergebnisse von Teilproblemen eines großen Problems werden gespeichert. Diese können aber problemlos gelöscht werden, wenn ein neuer Wert die Hashspeicherzelle überschreibt, da sie neu berechnet werden können.

Balancierte Bäume

Bei den Bäumen ist jeweils das Verhalten beim Einfügen und Entfernen wichtig.

Höhe von Bäumen

leerer Teilbaum:	-1
ein Knoten:	0
	usw.

Suchbäume

Bei einem INORDER-Durchlauf eines Suchbaumes sind alle Elemente sortiert.

AVL

Wenn und $bal(right(v))\in\{-1,0\}$ einfache Rotation nach links
Wenn und Doppelrotation rechts-links
Wenn und $bal(left(v))\in\{1,0\}$ einfache Rotation nach rechts
Wenn und Doppelrotation links-recht

Die Höhe eines AVL-Baumes ist $O(\log n)$ . Schlechteste AVL-Bäume sind Fibonaccibäume. Bei diesen steht die Fibonaccizahl $F_{n+1}$ in der Wurzel.

Blatt

In den inneren Knoten werden nur die Schlüssel, die zur Suche benötigt werden, gespeichert. Die eigentlichen Informationen stehen in den Blättern. Dabei sind die Blätter zum besseren sequentiellen Auslesen untereinander doppelt verknüpft.

B-Bäume

B-Bäume sind Speicherstrukturen für den externen Speicher.
Wenn ein B-Baum die Ordnung

hat, dann bedeutet das, daß jeder Knoten mindestens

aber höchstens $m\cdot 2$ Schlüsselwerte mit den dazugehörigen Daten beinhaltet. (Davon ist die Wurzel ausgenommen)
B-Bäume haben folgende Eigenschaften:

Jeder Knoten, außer die Wurzel hat mindestens und höchstens Schlüsselwerte, wobei die Ordnung ist.
Die Wurzel hat höchstens Schlüsselwerte. Nach unten gibt es jedoch keine Grenze.
Jeder Knoten mit Schlüsselwerten hat Söhne, wenn dieser Knoten nicht ein Blatt ist.
Alle Blätter haben dieselbe Tiefe bezüglich des Wurzelknotens.

Wir fügen Schlüssel zu dem Baum hinzu, indem wir sie in dem geeigneten Blattknoten einfügen. Wird dieser zu groß (OVERFLOW), müssen wir ihn splitten. Hierbei wandert der mittlere Wert dieses Knoten in den darüber liegenden Vater und aus dem einen Knoten werden zwei gemacht.
Beim Löschen kann es passieren, daß ein Knoten zu klein wird (UNDERFLOW). Wenn es möglich ist, borgen wir uns Schlüsselwerte von einem benachbarten Bruderknoten. Hierbei geht ein Wert aus dem Bruder in den gemeinsamen Vaterknoten, während ein Schlüsselwert aus dem Vaterknoten in den Knoten mit dem UNDERFLOW kommt. Geht dies nicht, so wenden wir Konkatenation an und zwei Bruderknoten werden zu einem Knoten zusammengefügt. Dieser Knoten nimmt des weiteren noch den Wert aus dem Vaterknoten auf, der nun auf keinen Sohn mehr zeigt.
Die Laufzeit von Suchen, Einfügen und Löschen auf B-Bäumen ist

$\begin{displaymath}O(H\uml {o}he(T))=O(\log_{(m+1)}(N))\end{displaymath}$

wobei

die Ordnung und

die Schlüsselanzahl.

Kruskal zur Erstellung des MST Algorithmen der Informatik Greedy Algorithmus

Ψ Die Informatikseite

Speichermöglichkeiten von Datenmengen mit dynamischer Größe

Hashing