Informatik II, SS 2008 Algorithmen und Datenstrukturen Vorlesung 14 Prof. Dr. Thomas Ottmann Algorithmen & Datenstrukturen, Institut für Informatik Fakultät

Informatik II, SS 2008Algorithmen und Datenstrukturen

Vorlesung 14Prof. Dr. Thomas Ottmann

Algorithmen & Datenstrukturen, Institut für InformatikFakultät für Angewandte WissenschaftenAlbert-Ludwigs-Universität Freiburg

Hashing

Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 2

Das Wörterbuch-Problem (1)

Das Wörterbuch-Problem (WBP) kann wie folgt beschrieben werden:

Gegeben: Menge von Objekten (Daten) die über einen eindeutigen Schlüssel (ganze Zahl, String, . . . ) identifizierbar sind.

Gesucht: Struktur zu Speicherung der Objektmenge, so dass mindestens die folgenden Operationen (Methoden) effizient ausführbar sind:• Suchen (Wiederfinden, Zugreifen)• Einfügen• Entfernen

Bedingungen, die die Wahl einer Lösung des WBP beeinflussen:– Ort, wo die Daten gespeichert sind (Hauptspeicher, Platte, Band, CD,…)

– Art- und Häufigkeit der auszuführenden Operationen



Häufigkeit der Operationen:– überwiegend Einfügen & Löschen (dynamisches Verhalten)– überwiegend Suchen (statisches Verhalten)– annähernd Gleichverteilung– nichts bekannt

Weitere zu implementierende Operationen:– Durchlaufen der Menge in bestimmter Reihenfolge (etwa nach Schlüsselwert aufsteigend)– Mengen-Operationen: Vereinigung, Durchschnitt, Differenz, . . .– Aufspalten– Konstruieren

Kostenmaße zur Beurteilung der Lösung: average, worst, amortisierter worst case

Ausführungsreihenfolge der Operationen:– sequentiell– nebenläufig



Verschiedene Ansätze zur Lösung des WBP:

Aufteilung des gesamten Schlüssel-Universums: Hashing

Strukturierung der aktuellen Schlüsselmange: Listen, Bäume, Graphen, . . .

Hashing (engl.: to hash=zerhacken) beschreibt eine spezielle Art der Speicherung der Elemente einer Menge durch Zerlegung des Schlüssel-Universums.

Die Position des Daten-Elements im Speicher ergibt sich (zunächst) durch Berechnung direkt aus dem Schlüssel.


Hashverfahren

Annahme: Daten sind über einen ganzzahligen Schlüssel eindeutig identifizierbar. Suchen, Einfügen, Entfernen von Datensätzen (Schlüsseln) soll unterstützt werden.

Ort des Datensatzes d: Berechnung aus dem Schlüssel s von d keine Vergleiche konstante Zeit

Datenstruktur: lineares Feld (Array) der Größe mHashtabelle

0 1 2 i m-2 m-1

Schlüssel s

…………. ………….

Der Speicher wird zerlegt in m gleich große Behälter (Buckets).


Implementierung in Java

class TableEntry { private Object key,value;}

abstract class HashTable { private TableEntry[] tableEntry; private int capacity;

//Konstruktor HashTable (int capacity) { this.capacity = capacity; tableEntry = new TableEntry [capacity]; for (int i = 0; i <= capacity-1; i++) tableEntry[i] = null; } // die Hashfunktion protected abstract int h (Object key);

/* fuege Element mit Schluessel key und Wert value ein (falls nicht vorhanden) */

public abstract void insert (Object key Object value);

// entferne Element mit Schluessel key (falls vorhanden) public abstract void delete (Object key);

// suche Element mit Schluessel key public abstract Object search (Object key);} // class hashTable


Hashverfahren - Probleme

Größe der HashtabelleNur eine kleine Teilmenge S aller möglichen Schlüssel (des Universums) U kommt vor

Berechnung der Adresse eines Datensätzen- Schlüssel sind keine ganzen Zahlen- Index hängt von der Größe der Hashtabelle ab

In Java:public class Object { ... public int hashCode() {…} ...}

Das Universum U sollte möglichst gleichmäßig auf die Zahlen -231,…,231-1 verteilt werden


h(s) = Hashadresse

h(s) = h(s´) s und s´ sind Synonyme bzgl. h

Adresskollision

Hashfunktion (1)

Schlüsselmenge S

Univer-sum Ualler mög-lichen Schlüs-sel

Hashfunktion h

0,…,m-1

Hashtabelle T

])12,2[)(( 3131 UH


Hashfunktion (2)

Definition: Sei U ein Universum möglicher Schlüssel und {B0, . . . ,Bm-1} eineMenge von m Behältern zum Speichern von Elementen aus U:

Dann ist eine Hash-Funktion eine totale Abbildung

h : U {0, . . . ,m - 1} ,

die jedem Schlüssel s aus U eine Nummer h(s) (und dem entsprechenden Element den Behälter Bh(s) ) zuordnet.

Die Behälter-Nummern nennt man auch Hash-Adressen, die Gesamtmenge der Behälter Hash-Tabelle.

B0

B1

Bm-1

…

…


Adresskollisionen

Eine Hashfunktion h berechnet für jeden Schlüssel s die Nummer des Buckets.

Ideal wäre eine eindeutige Speicher-Zuordnung eines Datums mit Schlüssel s zum Bucket mit Nummer h(s): Einfügen und Suchen könnten dann in konstanter Zeit (O(1)) erfolgen.

Tatsächlich treten natürlich Kollisionen auf: Mehrere Elemente können auf die gleiche Hash-Adresse abgebildet werden. Kollisionen müssen (auf eine von verschiedenen Arten) behandelt werden.


Hashverfahren

Beispiel für U: alle Namen in Java mit Länge ≤ 40 |U | = 6240

Falls |U | > m : Adresskollisionen unvermeidlich

Hashverfahren:1. Wahl einer möglichst „guten“ Hash-Funktion2. Strategie zur Auflösung von Adresskollisionen

Belegungsfaktor :

Annahme: Tabellengröße m ist fest

m

n

m

S

Tabelle-Hashder Größe

Schlüssel tegespeicher #


Anforderungen an gute Hashfunktionen

Eine Kollision tritt dann auf, wenn bei Einfügen eines Elementes mit Schlüssel s der Bucket Bh(s) schon belegt ist.

Eine Hash-Funktion h heißt perfekt für eine Menge von Schlüsseln S, falls keine Kollisionen für S auftreten.

Ist h perfekt und |S| = n, dann gilt: n ≤ m. Der Belegungsfaktor (BF) derHash-Tabelle ist n/m ≤ 1.

Eine Hash-Funktion ist gut gewählt, wenn

– der Belegungsfaktor möglichst hoch ist,– für viele Schlüssel-Mengen die # der Kollisionen möglichst klein ist,– sie effizient zu berechnen ist.


Beispiel einer Hashfunktion

Beispiel: Hash-Funktion für Strings

public static int h (String s){ int k = 0, m = 13; for (int i=0; i < s.length(); i++) k += (int)s.charAt (i); return ( k%m );}

Folgende Hash-Adressen werden generiert für m = 13.

Schlüssel s h(s)Test 0Hallo 2SE 9Algo 10

h wird perfekter, je größer m gewählt wird.


Kollisionswahrscheinlichkeit (1)

Zur Wahl der Hash-Funktion

Die Anforderungen hoher Belegungsfaktor und Kollisionsfreiheit stehen in Konfliktzueinander. Es ist ein geeigneter Kompromiss zu finden.

Für die Schlüssel-Menge S mit |S| = n und Behälter B0, . . . , Bm-1 gilt:

– für n > m sind Konflikte unausweichlich– für n < m gibt es eine (Rest-) Wahrscheinlichkeit PK(n,m) für das Auftreten

mindestens einer Kollision.

Wie findet man Abschätzung für PK(n,m)?

Für beliebigen Schlüssel s ist die W’keit dafür, dass h(s) = j mitj {0, . . . ,m - 1}: PK [h(s) = j ] = 1/m, falls Gleichverteilung gilt.

Es ist PK(n,m) = 1 - P¬K(n,m),

wenn P¬K(n,m) die W’keit dafür ist, dass es beim Speichern von n Elementen in

m Behälter zu keinen Kollisionen kommt.


Kollisionswahrscheinlichkeit (2)

Zur Wahrscheinlichkeit von Kollisionen

Werden n Schlüssel nacheinander auf die Behälter B0, . . . , Bm-1 verteilt (beiGleichverteilung), gilt jedes mal P [h(s) = j ] = 1/m.

Die W’keit P(i) für keine Kollision im Schritt i ist P(i) = (m - (i - 1))/m

Damit ist

Für m = 365 etwa ist P(23) > 50% und P(50) 97% (Geburtstagsparadoxon)

nK mnmmm

nPPPmnP)1)...(1(

1)(*...*)2(*)1(1),(


Gebräuchliche Hashfunktionen

In der Praxis verwendete Hash-Funktionen:

Siehe: D.E. Knuth: The Art of Computer Programming

Für U = integer wird die Divisions-Rest-Methode verwandt:

h(s) = (a × s) mod m (a 0, a m, m Primzahl)

Für Zeichenreihen der Form s = s0s1 . . . sk-1 nimmt man etwa:

etwa mit B = 131 und w = Wortbreite des Rechners (w = 32 oder w = 64 ist üblich).

msBsh wk

ii

i mod2mod)(1

0


Einfache Hashfunktion

Wahl der Hash-Funktion- leichte und schnelle Berechenbarkeit - gleichmäßige Verteilung der Daten (Beispiel: Compiler)

(Einfache) Divisions-Rest-Methode

h(k) = k mod m

Wahl von m?

Beispiele:

a) m gerade h(k) gerade k gerade

Problematisch, wenn letztes Bit Sachverhalt ausdrückt (z.B. 0 = weiblich,

1 = männlich)

b) m = 2p liefert p niedrigsten Dualziffern von k

Regel: Wähle m prim, wobei m keine Zahl ri +- j teilt,wobei i und j kleine, nichtnegative Zahlen und r Radix der Darstellung sind.


Multiplikative Methode

p Bits = h(k)

r0 r1

0,

k

Wähle eine irrationale Zahl

Berechne h(k) = [m (k mod 1) ]

Berechnung von h(k) :

Wahl von m unkritisch, wähle m = 2p


Universelles Hashing

Idee :Wähle Hashfunktion h zufällig aus einer sorgfältig definierten endlichen Menge H von Hashfunktionen, und zwar so dass für eine zufällig gewählte Funktion h H gilt:

Die Wahrscheinlichkeit dafür, dass h für zwei beliebige Elemente x und y aus dem Universum U eine Adresskollision verursacht, ist 1/m, m = Größe der Hashtabelle.

Beispiel für eine universelle Klasse von Hashfunktionen:

|U| = p mit Primzahl p und |U| = {0,…,p-1}

Seien a {1,…,p-1} und b {0,…,p-1} und ha,b : U {0,…,m-1} wie folgt definiert

ha,b = ((ax+b)mod p) mod m

Folgerung: Die Menge H = {ha,b | 1 ≤ a ≤ p,0 ≤ b ≤ p} ist eine universelle Klasse von Hashfunktionen.


Möglichkeiten der KollisionsbehandlungDie Behandlung von Kollisionen erfolgt bei verschiedenen Verfahren

unterschiedlich.

Ein Datensatz mit Schlüssel s ist ein Überläufer, wenn der Behälter h(s) schondurch einen anderen Satz belegt ist.

Wie kann mit Überläufern verfahren werden?

1. Behälter werden durch verkettete Listen realisiert. Überläufer werden in diesen Listen abgespeichert.Chaining (Hashing mit Verkettung der Überläufer)

2. Überläufer werden in noch freien anderen Behältern abgespeichert. Diese werden beim Speichern und Suchen durch sogenanntes Sondieren gefunden.Open Addressing (Offene Hashverfahren)


Verkettung der Überläufer (1)

Die Hash-Tabelle ist ein Array (Länge m) von Listen. Jeder Behälter wird durch eine Liste realisiert.

class hashTable { Liste [] ht; // ein Listen-Array hashTable (int m){ // Konstruktor ht = new Liste[m]; for (int i = 0; i < m; i++) ht[i] = new Liste(); // Listen-Erzeugung } ...}

Zwei verschiedene Möglichkeiten der Listen-Anlage:1. Hash-Tabelle enthält nur Listen-Köpfe, Datensätze sind in Listen: DirekteVerkettung

2. Hash-Tabelle enthält pro Behälter maximal einen Datensatz sowie einen

Listen-Kopf. Überläufer kommen in die Liste: Separate Verkettung


Hashing mit Verkettung der Überläufer

Schlüssel werden in Überlauflisten gespeichert

Diese Art der Verkettung wird auch als direkte Verkettung bezeichnet.

h(k) = k mod 7

0 1 2 3 4 5 6Haschtabelle TZeiger

Überläufer

15 2

43

53 12

19

5


Verkettung der Überläufer

Suchen nach Schlüssel k - Berechne h(k) und Überlaufliste T[h(k)] - Suche nach k in der Überlaufliste

Einfügen eines Schlüssels k - Suchen nach k (erfolglos)- Einfügen in die Überlaufliste

Entfernen eines Schlüssels k - Suchen nach k (erfolgreich)- Entfernen aus Überlaufliste

Reine Listenoperationen


Analyse der direkten Verkettung

Uniform-Hashing Annahme:

alle Hashadressen werden mit gleicher Wahrscheinlichkeit gewählt, d.h.:

Pr(h(ki) = j) = 1/m

unabhängig von Operation zu Operation

Mittlere Kettenlänge bei n Einträgen:

n/m = Definition

Cń = Erwartungswert für die Anzahl betrachteter Einträge bei erfolgloser Suche

Cn = Erwartungswert für die Anzahl betrachteter Einträge bei erfolgreicher Suche

Analyse

21

´

n

n

C

C


Verkettung der Überläufer

Vorteile:

+ Cn und Cń niedrig

+ > 1 möglich

+ echte Entfernungen

+ für Sekundärspeicher geeignet

Effizienz der Suche

Cn (erfolgreich) Cń (erfolglos)

0.50 1.250 0.50

0.90 1.450 0.90

0.95 1.457 0.95

1.00 1.500 1.00

2.00 2.000 2.00

3.00 2.500 3.00

Nachteile- Zusätzlicher Speicherplatz für Zeiger- Überläufer außerhalb der Hashtabelle


worst case: h(s) liefert immer den gleichen Wert, alle Datensätze sind in einer Liste.Verhalten wie bei Linearer Liste.

average case:– Erfolgreiche Suche & Entfernen: Aufwand in Datenzugriffen 1 + 0.5 × BF– Erfolglose Suche & Einfügen: Aufwand BF

Das gilt für direkte Verkettung, bei separater Verkettung ist der Aufwand jeweilsetwas höher.

best case: Die Suche hat sofort Erfolg. Aufwand O(1).

Analyse Hashing mit Verkettung


Offene Hashverfahren

Idee:Unterbringung der Überläufer an freien (“offenen”) Plätzen in Hashtabelle

Falls T[h(k)] belegt, suche anderen Platz für k nach fester Regel

Beispiel:Betrachte Eintrag mit nächst kleinerem Index:

(h(k) - 1) mod m

Allgemeiner:Betrachte die Folge

(h(k) - j) mod m j = 0,…,m-1

0 1 h(k) m-2 m-1

… ..... .….


Sondierungsfolgen

Noch allgemeiner:

Betrachte Sondierungsfolge

(h(k) – s(j,k)) mod m

j = 0,...,m-1, für eine gegebene Funktion s(j,k)

Beispiele für die Funktion

s(j,k) = j (lineares Sondieren)

s(j,k) = (-1)j * j/22 (quadratisches Sondieren)

s(j,k) = j * h´(k) (Double Hashing)


Sondierungsfolgen

Eigenschaften von s(j,k)

Folge(h(k) – s(0,k)) mod m,(h(k) – s(1,k)) mod m,

(h(k) – s(m-2,k)) mod m,(h(k) – s(m-1,k)) mod m

sollte eine Permutation von 0,...,m-1 liefern.

Beispiel: Quadratisches Sondieren

Kritisch: Entfernen von Sätzen als entfernt markieren

(Einfügen von 4, 18, 25, Löschen 4, Suche 18, 25)

0 1 2 3 4 5 6

h(11) = 4

s(j,k) = -1,1,-4,4,-9,9


Offene Hashverfahren

class OpenHashTable extends HashTable { // in HashTable: TableEntry [] T; private int [] tag;

static final int EMPTY = 0; // Frei static final int OCCUPIED = 1; // Belegt static final int DELETED = 2; // Entfernt

// Konstruktor OpenHashTable (int capacity) { super(capacity); tag = new int [capacity]; for (int i = 0; i < capacity; i++) { tag[i] = EMPTY; } }

// Die Hashfunktion protected int h (Object key) {...}

// Funktion s für Sondierungsfolge protected int s (int j, Object key) { // quadratisches Sondieren if (j % 2 == 0) return ((j + 1) / 2) * ((j + 1) / 2); else return -((j + 1) / 2) * ((j + 1) / 2); }


Offene Hashverfahren - Suchenpublic int searchIndex (Object key) { /* sucht in der Hashtabelle nach Eintrag mit Schluessel key und liefert den zugehoerigen Index oder -1 zurueck */ int i = h(key); int j = 1; // naechster Index der Sondierungsfolge

while (tag[i] != EMPTY &&!key.equals(T[i].key)){ // Naechster Eintr. in Sondierungsfolge i = (h(key) - s(j++, key)) % capacity; if (i < 0) i = i + capacity; }

if (key.equals(T[i].key) && tag[i] == OCCUPIED) return i; else return -1; }

public Object search (Object key) { /* sucht in der Hashtabelle nach Eintrag mit Schluessel key und liefert den zugehoerigen Wert oder null zurueck */ int i = searchIndex (key); if (i >= 0) return T[i].value; else return null; }


Offene Hashverfahren - Einfügen

public void insert (Object key, Object value) { // fuegt einen Eintrag mit Schluessel key und Wert value ein int j = 1; // naechster Index der Sondierungsfolge int i = h(key);

while (tag[i] == OCCUPIED) { i = (h(key) - s(j++, key)) % capacity; if (i < 0) i = i + capacity; }

T[i] = new TableEntry(key, value); tag[i] = OCCUPIED; }


Offene Hashverfahren - Entfernen

public void delete (Object key) { // entfernt Eintrag mit Schluessel key aus der Hashtabelle

int i = searchIndex(key);

if (i >= 0) { // Suche erfolgreich tag[i] = DELETED; }}


Test-Programm

public class OpenHashingTest { public static void main(String args[]) { Integer[] t= new Integer[args.length];

for (int i = 0; i < args.length; i++) t[i] = Integer.valueOf(args[i]);

OpenHashTable h = new OpenHashTable (7); for (int i = 0; i <= t.length - 1; i++) { h.insert(t[i], null);# h.printTable (); } h.delete(t[0]); h.delete(t[1]); h.delete(t[6]); h.printTable(); }}

Aufruf:java OpenHashingTest 12 53 5 15 2 19 43

Ausgabe (Quadratisches Sondieren):[ ] [ ] [ ] [ ] [ ] (12) [ ]

[ ] [ ] [ ] [ ] (53) (12) [ ]

[ ] [ ] [ ] [ ] (53) (12) (5)

[ ] (15) [ ] [ ] (53) (12) (5)

[ ] (15) (2) [ ] (53) (12) (5)

(19) (15) (2) [ ] (53) (12) (5)

(19) (15) (2) (43) (53) (12) (5)

(19) (15) (2) {43} {53} {12} (5)


Sondierungsfolgen - Lineares Sondieren

s(j,k) = j

Sondierungsfolge für k:

h(k), h(k)-1,...,0,m-1,..., h(k)+1,

Problem:primäre Häufung (“primary clustering”)

Pr (nächstes Objekt landet an Position 2) = 4/7

Pr (nächstes Objekt landet an Position 1) = 1/7

Lange Ketten werden mit größerer Wahrscheinlichkeit verlängert als kurze.

0 1 2 3 4 5 6

5 53 12


Effizienz des linearen Sondierens

erfolgreiche Suche:

erfolglose Suche:

Effizienz des linearen Sondierens verschlechtert sich drastisch, sobald sich der

Belegungsfaktor dem Wert 1 nähert.

)1(1

121

nC

2)1(1

121

ńC

Cn (erfolgreich) Cń(erfolglos)0.50 1.5 2.50.90 5.5 50.50.95 10.5 200.51.00 - -


Quadratisches Sondieren

s(j,k) = (-1)j * j/22


h(k), h(k)+1, h(k)-1, h(k)+4, ...

Permutation, falls m = 4l + 3 eine Primzahl ist.

Problem: sekundäre Häufung, d.h. zwei Synonyme k und k´ durchlaufen

stets dieselbe Sondierungsfolge.


Effizienz des quadratischen Sondierens

erfolgreiche Suche:

erfolglose Suche:

)1(1

ln2

1

nC

)1(1

ln11

´

nC

Cn (erfolgreich) Cń(erfolglos)0.50 1.44 2.190.90 2.85 11.400.95 3.52 22.051.00 - -


Uniformes Sondieren

s(j,k) = πk(j)

πk eine der m! Permutationen von {0,...,m-1}

- hängt nur von k ab- gleichwahrscheinlich für jede Permutation

11

nC

)1(1

ln*1

nC

Cn (erfolgreich) Cń(erfolglos)0.50 1.39 20.90 2.56 100.95 3.15 201.00 - -


Zufälliges Sondieren

Realisierung von uniformem Sondieren sehr aufwendig.

Alternative:

Zufälliges Sondieren

s(j,k) = von k abhängige Zufallszahl

s(j,k) = s(j´,k) möglich, aber unwahrscheinlich


Double Hashing

Idee: Wähle zweite Hashfunktion h´

s(j,k) = j*h´(k)


h(k), h(k)-h´(k), h(k)-2h´(k),...

Forderung:Sondierungsfolge muss Permutation der Hashadressen entsprechen.

Folgerung:h´(k) ≠ 0 und h´(k) kein Teiler von m, d.h. h´(k) teilt m nicht.

Beispiel:h´(k) = 1 + (k mod (m-2))


Beispiel

Hashfunktionen: h(k) = k mod 7h´(k) = 1 + k mod 5

Schlüsselfolge: 15, 22, 1, 29, 26

In diesem Beispiel genügt fast immer einfaches Sondieren.

Double Hashing ist genauso effizient wie uniformes Sondieren.

Double Hashing ist leichter zu implementieren.

0 1 2 3 4 5 6

15

0 1 2 3 4 5 6

0 1 2 3 4 5 6

0 1 2 3 4 5 6

15 22

15 22 1

15 29 22 1

h´(22) = 3

h´(29) = 5

h´(26) = 2

h´(1) = 2


Hashtabelle der Größe 11, Double Hashing mit

h(k) = k mod 11 und

h´(k) = 1 + (k mod (11 – 2)) = 1 + (k mod 9)

Bereits eingefügt: 22, 10, 37, 47, 17Noch einzufügen: 6 und 30

h(6) = 6, h´(6) = 1 + 6 = 7

h(30) = 8, h´(30) = 1 + 3 = 4

0 1 2 3 4 5 6 7 8 9 10

0 1 2 3 4 5 6 7 8 9 10

22 47 37 17 10

22 47 37 6 17 10

Verbesserung der erfolgreichen Suche -Motivation


Verbesserung der erfolgreichen Suche: Allgemein

Einfügen: - k trifft in T[i] auf kalt, d.h. i = h(k) - s(j,k) = h(kalt) - s(j´,kalt)

- kalt bereits in T[i] gespeichert

Idee:Suche freien Platz für k oder kalt

Zwei Möglichkeiten:

(M1) kalt bleibt in T[i]

betrachte neue Position

h(k) - s(j+1,k) für k

(M2) k verdrängt kalt

betrachte neue Position

h(kalt) - s(j´+1, kalt) für kalt

if (M1) or (M2) trifft auf einen freien Platzthen trage entsprechenden Schlüssel ein fertigelse verfolge (M1) oder (M2) weiter


Verbesserung der erfolgreichen Suche

Brent’s Verfahren: verfolge nur (M1)

Binärbaum Sondieren: verfolge (M1) und (M2)

k trifft auf k´

k weicht aus

k´´ weicht aus

k´ weicht aus

k´´´ weicht aus

k weicht aus

k trifft auf k´´´´

k trifft auf k´´´

k trifft auf k´´

fertig

fertig

fertig


Verbesserung der erfolgreichen Suche

Problem: kalt von k verdrängt: nächster Platz in Sondierungsfolge für kalt?

Ausweichen von kalt einfach, wenn gilt:

s(j, kalt) - s(j -1, kalt) = s(1,kalt)

für alle 1 ≤ j ≤ m -1.

Das gilt beispielsweise für lineares Sondieren und double Hashing.

11

5.2...1542

1

´

43

C

C

n

Brent

n

2.2...1542

143

CBinärbaum

n


Beispiel

Hashfunktionen: h(k) = k mod 7h´(k) = 1 + k mod 5

Schlüsselfolge: 12, 53, 5, 15, 2, 19

h(5) = 5 belegt k´= 12

Betrachte:

h´(k) = 1 h(5) -1 * h´(5)

5 verdrängt 12 von seinem Platz

0 1 2 3 4 5 6

53 12


Verbesserung der erfolglosen Suche

Suche nach k: k´>k in Sondierungsfolge: Suche erfolglos

Einfügen:kleinere Schlüssel verdrängen größere Schlüssel

Invariante:Alle Schlüssel in der Sondierungsfolge vor k sind kleiner als k (aber nicht notwendigerweise aufsteigend sortiert)

Probleme:

Verdrängungsprozess kann “Kettenreaktion” auslösen

k´ von k verdrängt: Position von k´ in Sondierungsfolge?

Es muss gelten:

s(j,k) - s(j -1,k) = s(1,k), 1 ≤ j ≤ m


Ordered Hashing

Suchen

Input: Schlüssel kOutput: Information zu Datensatz mit Schlüssel k oder nullBeginne bei i h(k)while T[i] nicht frei and T[i] .k < k do

i (i – s(1,k)) mod m end while; if T[i] belegt and T[i] .k = k

then Suche erfolgreichelse Suche erfolglos


Ordered Hashing

Einfügen

Input: Schlüssel k Beginne bei i h(k) while T[i] nicht frei and T[i] .k ≠ k do

if k < T[i].k then if T[i] ist entfernt

then exit while-loopelse // k verdrängt T[i].k vertausche T[i].k mit k

i = (i – s(1,k)) mod mend while;

if T[i] ist nicht belegt then trage k bei T[i] ein

Documents

Informatik II, SS 2008 Algorithmen und Datenstrukturen Vorlesung 14 Prof. Dr. Thomas Ottmann Algorithmen & Datenstrukturen, Institut für Informatik Fakultät