Alda - User contributions [en]

Talk:Hashing und assoziative Arrays

2008-07-09T20:14:24Z

Thorben:

'''Wie sieht es denn jetzt mit einer Wiki Version aus?'''

Warum als PDF? Das ist doch völlig am Sinn des Wikis vorbei...

Finde ich auch, wenn du es schon als tex gemacht hast ist es doch super einfach
es in die Wiki zu übertragen, die unterstützt ja über < math > und < /math > auch
viele Latexbefehle...

Hmmkay, war mir über die Funktionalität eines Wikis nicht ganz im klaren. Daher auch einfach "Faulheit" dahingehend, dass ich was genommen habe, was ich kannte. Wie gesagt, ich hätte sehr gern die Sourcen gescheit veröffentlicht, sodass eine gewissen Interaktualität gesichert wäre, aber .tex's darf man ja nicht hochladen. Ich kümmer mich frühestens Freitag, spätestens am Wochenende darum, dass ganze ins Wiki Format zu bringen. Sorry für die Verzögerung, Übungsblätter rufen...

Talk:Graphen und Graphenalgorithmen

2008-06-18T15:14:54Z

Thorben:

Habe die Graphen k1 bis k5 mit Graphviz gezeichnet und die Bilder gegen die ASCII Art ausgetauscht.

Hier meine Quelltext:
k1.dot:
graph {
1
}

k2.dot:
graph {
1 -- 2
}

k3.dot:
graph {
1 -- 2
2 -- 3
3 -- 1
}

k4.dot:
graph {
1 -- 2 [weight = 10]
1 -- 3
2 -- 3 [weight = 10]
3 -- 4 [weight = 10]
4 -- 1 [weight = 10]
4 -- 2
}

k5.dot
graph {
1 -- 2
2 -- 3
3 -- 4
4 -- 5
5 -- 1

1 -- 3
1 -- 4
2 -- 4
2 -- 5
5 -- 3
}

Generierung der Graphiken mit:
#!/bin/bash
for i in *.dot; do
fdp -Tpng $i -Gcharset=latin1 -o `basename $i .dot`.png
done;

Gerichteter Graph:
digraph {
1 -> 2
1 -> 4
3 -> 2
3 -> 4
}
und übersetzt mit <tt>circo</tt>
[[User:Thorben|Thorben]]

Graphen und Graphenalgorithmen

2008-06-18T15:13:54Z

Thorben: Gerichteter Graph als Graphik gemacht

== Einführung zu Graphen ==

=== Motivation ===

==== Königsberger - Brückenproblem ====
(1736 Euler)

[[Image:Koenigsberg.jpg]]

Königsberger Brücken:

Spaziergang durch Königsberg, so dass alle Brücken nur einmal überquert werden.

Geometrie:
Topologie

O
|| \
|| \
O O
|| /
|| /
O

* '''Definition: ungerichteter Graph'''

Ein ungerichteter Graph G = ( V, E )

** V ist endliche Menge von Knoten (vertices)
** E c V × V (edges)

Ein Graph heißt ungerichtet, wenn zusätzlich gilt:

(x,y) ∈ E => (y,x) ∈ E (symmetrie)

Bsp:

gerichteter Graph
[[Image:digraph.png|gerichteter Graph]]

ungerichtet

O
|| \
|| \
O O
|| /
|| /
O

Bsp:

* Landkarten:
** Knoten: Länder
** Kanten: gem. Grenzen

* Schaltkreis:
** Knoten: Gatter
** Kanten: Verbindungen

* Chemie (Summenformeln):
** Knoten: Elemente
** Kanten: Bindungen

* Soziologie (StudieVZ)
** Soziogramm
*** Knoten: Personen
*** Kanten: Freund von ...

* '''Definition: Vollständige Graphen'''

Bei vollständigen Graphen ist jeder Knoten mit allen anderen Knoten verbunden.

E = U V (v,w) u (w,v) | v ∈ V, w ∈ V, u != w

{| border="0" cellspacing="0" cellpadding="0" style="margin: 1em auto 1em auto"
|-
| [[Image:k1.png|frame|k1]]
| [[Image:k2.png|frame|k2]]
| [[Image:k3.png|frame|k3]]
|-
| [[Image:k4.png|frame|k4]]
| [[Image:k5.png|frame|k5]]
|
|}

''Rätsel''
Auf einer Party sind Leute. Alle stoßen miteinander an. Es hat 78 mal "Pling" gemacht.
Wieviele Leute waren da?

== Repräsentation von Graphen ==

Sei G = ( V, E ) geg und liege V in einer lineraren Sortierung vor.
V = { v1, ...., vn }

== Adjazenzmatrix ==

AG = aij = {1 falls (vi, vj) ∈ E ; sonst 0}

Bsp:

v = { a,b,c,d } b d
| \ / |
| \/ |
| /\ |
| / \ |
a c

a b c d
-----------
(0 1 0 1) |a
AG = (1 0 1 0) |b
(0 1 0 1) |c
(1 0 1 0) |d

== Adjezenzlisten ==

al(v) = {v' ∈ V | (u,u') ∈ E}
Lg = ((v1, al(v1)), ...., (vn, al(vn))

Python:

Array von Arrays [[...],[...],...,[...]]
0 1 n

* '''Definition: Teilgraphen'''

Ein Graph G' = (v',E') ist ein Teilgraph, wenn gilt:

** v' c V
** E' c E

Er heißt erzegender Graph, wenn zusätzlich gilt:

** v' = V

* '''Definition: Knotengrade'''
Für G = (v,E)und v ∈ V
grad(v) = |{v' ∈ V | v,v'∈ E}|
out_grad(v) = | -""- |
in_grad(v) = |{v'∈ V| (v',v) ∈ E}|

Bsp:

ungerichtet

c
|| \
|| \
b d grad(a) = | {b,b,d} | = 3
|| /
|| /
a

gerichtet

c←
| \
↓ \
b←--d out_grad(d) = 2 = | {c,b} |
| /→ in_grad(d) = 1 = | {a} |
↓ /
a

* '''Definition: Wege'''

Sei G = (v,E)

** Für v0 ∈ V ist (v0) ein Weg in G
** Für Knoten v1,...vn,vn+1 und eine Kante (vn,vn+1) ∈ E ist mit einem Weg (v0,....vn) in G auch (v0,...,vn,vn+1) ein Weg in G.

Also: Nichtleere Folgen von Knoten die durch eine Kante verbunden sind.

== Eulerweg ==

O
/ \
O----O
| \/ |
| /\ | "Das Haus vom Nikolaus" Alle ''Kanten'' werden nur ''einmal'' passiert
O----O

== Hamiltonweg ==

O
/
O----O
/
/ Alle ''Knoten'' werden nur ''einmal'' passiert
O----O

== Kreis ==

O
/ \
O O
| | v0 = vn
| | vi != vj Für Alle i,j i !=j; i,j >0; i,j < n
O----O

== Zyklen ==

O
/ \
O O
\ |
\ | Wie Kreis nur ohne (vi != vj)
O====O

* '''Definition: planare Graphen'''

Ist ein Graph, der auf einer Ebene gezeichnet werden ''kann'', sodass sich die Kanten nicht schneiden!

Bsp:

1)

O
/|\
/ O \
/ / \ \
O O

2)

O
/ \
O----O
| \/ |
| /\ |
O----O

3)

|----O @
| /@ \
| O----O
| |@ / |
| | / @|
| O----O @ entspricht ''Regionen'' auch ausserhalb der Figur ist eine Region
|@ |
|-------|

1),2) und 3) sind planare Graphen.

Der K5 Graph ist kein planarer Graph da sich zwangsweise Kanten schneiden.

* '''Definition: dualer Graph'''

Der duale Graph eines geg. planaren Graphs G' ist ein Graph mit

** Knoten für jede Region
** Für jede Kante aus E gilt es gibt eine Kante, die die angrenzende Region mit Knoten verbindet.

dualer Graph

O------O
| /| \
|-|-@ / | @\---|
| | |\/ |/| O |
| | |/\ /| |/ |
| | / @ | / |
| O-+--+-O | |
| | | | |
|---|--@---|----|

* '''Definition: erreichbar'''

W ∈ V ist erreichbar von v ∈ G gdw.:
es Existiert Weg(v,...w)

* '''Definition: Zusammenhang'''

G heißt zusammenhängend, wenn für Alle v,w ∈V gilt:
w ist erreichbar von V

== Bäume ==

* '''Definition: Baum'''

Ein Baum ist ein zusammenhängender, kreisfreier Graph.

Bsp.: Binary Search Tree

* '''Definition: erzeugender Baum'''

für G = (v,E) ist ein erzeigender Teilgraph mit Baumeigenschaft

Bsp.:

O O
/ /
O O O
| / /
| / /
O----O----O

== Durchlaufen von Graphen ==

=== Tiefensuche in Graphen ===

Sei der Graph geg als Liste von Listen = g

def dfs (g,node,v=0):
if v == 0:
v = [0]*len(g) #visited-Liste
v[node] = 1 #besuche node
for t in g[node]: #gehe zu allen Nachbarn
if v[t] == 0: #falls diese noch nicht besucht
dfs(g,t,v) #Rekursion

[[Image:Tiefens.jpg]]

Aufruf dfs(g,1)

=>Folge 1,2,4,3,6,7,5

=== Breitensuche ===

from Queue import *
def bfs(g,startnode)
v = [0]*len(g)
q = Queue()
v = [startnode] = 1 #besuche
q.put(startnode) #in Schlange
while not q.get()
node = q.get()
for t in q[node]
if v[t] == 0:
v[t] = 1
q.put(t)

[[Image:Breitens.jpg]]

=>Folge 1,2,3,4,5,6,7

== Damenproblem ==

---------------
| | X | | |
|---|---|---|---|
| | | | X |
|---|---|---|---|
| X | | | |
|---|---|---|---|
| | | | X |
---------------

4 Damen auf einem vereinfachten Schachbrett so Positionieren, dass sich keine bedroht.

erster Durchlauf:

[[Image:Suche1.jpg]]

zweiter Durchlauf:

[[Image:Suche2.jpg]]

File:Digraph.png

2008-06-18T15:12:23Z

Thorben:

Talk:Graphen und Graphenalgorithmen

2008-06-18T15:08:19Z

Thorben:

Talk:Graphen und Graphenalgorithmen

2008-06-18T15:07:25Z

Thorben: New page: Habe die Graphen k1 bis k5 mit Graphviz gezeichnet und die Bilder gegen die ASCII Art ausgetauscht. Hier meine Quelltext: k1.dot: graph { 1 } k2.dot: graph { 1 -- 2 } k3...

Graphen und Graphenalgorithmen

2008-06-18T15:03:14Z

Thorben: Graphen mit Graphviz gezeichnet --> siehe Talk

== Einführung zu Graphen ==

=== Motivation ===

==== Königsberger - Brückenproblem ====
(1736 Euler)

[[Image:Koenigsberg.jpg]]

Königsberger Brücken:

Spaziergang durch Königsberg, so dass alle Brücken nur einmal überquert werden.

Geometrie:
Topologie

O
|| \
|| \
O O
|| /
|| /
O

* '''Definition: ungerichteter Graph'''

Ein ungerichteter Graph G = ( V, E )

** V ist endliche Menge von Knoten (vertices)
** E c V × V (edges)

Ein Graph heißt ungerichtet, wenn zusätzlich gilt:

(x,y) ∈ E => (y,x) ∈ E (symmetrie)

Bsp:

gerichtet

O----→O
| ↑
↓ |
O←----O

ungerichtet

O
|| \
|| \
O O
|| /
|| /
O

Bsp:

* Landkarten:
** Knoten: Länder
** Kanten: gem. Grenzen

* Schaltkreis:
** Knoten: Gatter
** Kanten: Verbindungen

* Chemie (Summenformeln):
** Knoten: Elemente
** Kanten: Bindungen

* Soziologie (StudieVZ)
** Soziogramm
*** Knoten: Personen
*** Kanten: Freund von ...

* '''Definition: Vollständige Graphen'''

Bei vollständigen Graphen ist jeder Knoten mit allen anderen Knoten verbunden.

E = U V (v,w) u (w,v) | v ∈ V, w ∈ V, u != w

{| border="0" cellspacing="0" cellpadding="0" style="margin: 1em auto 1em auto"
|-
| [[Image:k1.png|frame|k1]]
| [[Image:k2.png|frame|k2]]
| [[Image:k3.png|frame|k3]]
|-
| [[Image:k4.png|frame|k4]]
| [[Image:k5.png|frame|k5]]
|
|}

''Rätsel''
Auf einer Party sind Leute. Alle stoßen miteinander an. Es hat 78 mal "Pling" gemacht.
Wieviele Leute waren da?

== Repräsentation von Graphen ==

Sei G = ( V, E ) geg und liege V in einer lineraren Sortierung vor.
V = { v1, ...., vn }

== Adjazenzmatrix ==

AG = aij = {1 falls (vi, vj) ∈ E ; sonst 0}

Bsp:

v = { a,b,c,d } b d
| \ / |
| \/ |
| /\ |
| / \ |
a c

a b c d
-----------
(0 1 0 1) |a
AG = (1 0 1 0) |b
(0 1 0 1) |c
(1 0 1 0) |d

== Adjezenzlisten ==

al(v) = {v' ∈ V | (u,u') ∈ E}
Lg = ((v1, al(v1)), ...., (vn, al(vn))

Python:

Array von Arrays [[...],[...],...,[...]]
0 1 n

* '''Definition: Teilgraphen'''

Ein Graph G' = (v',E') ist ein Teilgraph, wenn gilt:

** v' c V
** E' c E

Er heißt erzegender Graph, wenn zusätzlich gilt:

** v' = V

* '''Definition: Knotengrade'''
Für G = (v,E)und v ∈ V
grad(v) = |{v' ∈ V | v,v'∈ E}|
out_grad(v) = | -""- |
in_grad(v) = |{v'∈ V| (v',v) ∈ E}|

Bsp:

ungerichtet

c
|| \
|| \
b d grad(a) = | {b,b,d} | = 3
|| /
|| /
a

gerichtet

c←
| \
↓ \
b←--d out_grad(d) = 2 = | {c,b} |
| /→ in_grad(d) = 1 = | {a} |
↓ /
a

* '''Definition: Wege'''

Sei G = (v,E)

** Für v0 ∈ V ist (v0) ein Weg in G
** Für Knoten v1,...vn,vn+1 und eine Kante (vn,vn+1) ∈ E ist mit einem Weg (v0,....vn) in G auch (v0,...,vn,vn+1) ein Weg in G.

Also: Nichtleere Folgen von Knoten die durch eine Kante verbunden sind.

== Eulerweg ==

O
/ \
O----O
| \/ |
| /\ | "Das Haus vom Nikolaus" Alle ''Kanten'' werden nur ''einmal'' passiert
O----O

== Hamiltonweg ==

O
/
O----O
/
/ Alle ''Knoten'' werden nur ''einmal'' passiert
O----O

== Kreis ==

O
/ \
O O
| | v0 = vn
| | vi != vj Für Alle i,j i !=j; i,j >0; i,j < n
O----O

== Zyklen ==

O
/ \
O O
\ |
\ | Wie Kreis nur ohne (vi != vj)
O====O

* '''Definition: planare Graphen'''

Ist ein Graph, der auf einer Ebene gezeichnet werden ''kann'', sodass sich die Kanten nicht schneiden!

Bsp:

1)

O
/|\
/ O \
/ / \ \
O O

2)

O
/ \
O----O
| \/ |
| /\ |
O----O

3)

|----O @
| /@ \
| O----O
| |@ / |
| | / @|
| O----O @ entspricht ''Regionen'' auch ausserhalb der Figur ist eine Region
|@ |
|-------|

1),2) und 3) sind planare Graphen.

Der K5 Graph ist kein planarer Graph da sich zwangsweise Kanten schneiden.

* '''Definition: dualer Graph'''

Der duale Graph eines geg. planaren Graphs G' ist ein Graph mit

** Knoten für jede Region
** Für jede Kante aus E gilt es gibt eine Kante, die die angrenzende Region mit Knoten verbindet.

dualer Graph

O------O
| /| \
|-|-@ / | @\---|
| | |\/ |/| O |
| | |/\ /| |/ |
| | / @ | / |
| O-+--+-O | |
| | | | |
|---|--@---|----|

* '''Definition: erreichbar'''

W ∈ V ist erreichbar von v ∈ G gdw.:
es Existiert Weg(v,...w)

* '''Definition: Zusammenhang'''

G heißt zusammenhängend, wenn für Alle v,w ∈V gilt:
w ist erreichbar von V

== Bäume ==

* '''Definition: Baum'''

Ein Baum ist ein zusammenhängender, kreisfreier Graph.

Bsp.: Binary Search Tree

* '''Definition: erzeugender Baum'''

für G = (v,E) ist ein erzeigender Teilgraph mit Baumeigenschaft

Bsp.:

O O
/ /
O O O
| / /
| / /
O----O----O

== Durchlaufen von Graphen ==

=== Tiefensuche in Graphen ===

Sei der Graph geg als Liste von Listen = g

def dfs (g,node,v=0):
if v == 0:
v = [0]*len(g) #visited-Liste
v[node] = 1 #besuche node
for t in g[node]: #gehe zu allen Nachbarn
if v[t] == 0: #falls diese noch nicht besucht
dfs(g,t,v) #Rekursion

[[Image:Tiefens.jpg]]

Aufruf dfs(g,1)

=>Folge 1,2,4,3,6,7,5

=== Breitensuche ===

from Queue import *
def bfs(g,startnode)
v = [0]*len(g)
q = Queue()
v = [startnode] = 1 #besuche
q.put(startnode) #in Schlange
while not q.get()
node = q.get()
for t in q[node]
if v[t] == 0:
v[t] = 1
q.put(t)

[[Image:Breitens.jpg]]

=>Folge 1,2,3,4,5,6,7

== Damenproblem ==

---------------
| | X | | |
|---|---|---|---|
| | | | X |
|---|---|---|---|
| X | | | |
|---|---|---|---|
| | | | X |
---------------

4 Damen auf einem vereinfachten Schachbrett so Positionieren, dass sich keine bedroht.

erster Durchlauf:

[[Image:Suche1.jpg]]

zweiter Durchlauf:

[[Image:Suche2.jpg]]

File:K5.png

2008-06-18T14:47:31Z

Thorben:

File:K4.png

2008-06-18T14:47:09Z

Thorben:

File:K3.png

2008-06-18T14:46:48Z

Thorben:

File:K2.png

2008-06-18T14:46:16Z

Thorben:

File:K1.png

2008-06-18T14:45:53Z

Thorben:

Talk:Main Page

2008-06-10T23:10:38Z

Thorben: /* Spam */

== Änderungsvorschläge ==

=== zum Übungsbetrieb ===

Bitte die Email-Adressen der Tutoren eintragen, so wie es schon für Thomas Gerlach der Fall ist.
:Ich hatte jetzt nur die von Daniel (Do Gruppe) parat, habe sie mal eingetragen [[Special:Contributions/83.189.36.163|83.189.36.163]] 13:41, 13 April 2008 (UTC)

Die Übungen sind ja auch mal wieder extrem einfach und beanspruchen fast grkeine Zeit... Ich sitze jetzt schon so ziemlich den ganzen Tag der zweiten Aufgabe und keine Ende in sicht... als ob wir sonst keine Uni hätten.

==Zu Übungsblatt 2:==
In-place sortieren bei selection- und quick-sort ist mir ja noch einsichtig - aber bei merge-sort? ist der algorithmus nicht so spezifiziert, dass man eine neue liste/ein neues array aufbaut? oder sollen wir einfach noch ne kapsel-funktion schreiben, und die neu-aufgebaute liste am ende auf die ausgangsliste verweisen lassen; das wäre zwar kein in-place sortieren im eigentlichen sinne, aber anders kann ich es mir gerade nicht vorstellen.
:Also ich denke eher, dass das ein Fehler in der Aufgabenstellung ist. Quick und Merge in-place ist doch schon ziemlich kontroproduktiv...
::U. Köthe: In-place war in der Aufgabe nicht so gemeint, dass die Algorithmen intern keinen zusätzlichen Speicher verwenden dürfen, sondern dass das sortierte Array am Ende das unsortierte überschreiben soll.

Vllt. hilft das ja noch jemandem, der mit seinem quick-sort nicht zu Rande kommt: hab die Erfahrung gemacht, dass es keine korrekten Ergebnisse liefert, wenn man die repeat-untils aus der Spezifikation aus der Vorlesung einfach in whiles mit umgekehrter Bedingung macht (also aus repeat...until a[j]<=a[p] etwa while a[j]>a[p]) - python hat zwar keine repeat-untils, aber mit einem while True...und einem den Block abschließenden if a[j]<=a[p]:break kann man das simulieren, und dann kann man einfach die spezifikationen in python eintippen.

== Spam ==

Ich schlage vor einfach mal alle nicht deutsch(sprachig)en IPs zu verbieten, da die Bots wohl aus USA/AU kommen (http://www.who.is/whois-ip/ip-address/208.17.80.5/).
Ausserdem vorsicht beim reverten, vorhin sind da ein paar Einträge verlorengegangen.

Eine weitere Möglichkeit besteht darin, die Website unter Passwortschutz zu stellen und das Passwort in der Vorlesung bekanntzugeben. Dieses Passwort muss ja kein großes Geheimnis sein, sondern soll nur Bots daran hindern, die Seite zu manipulieren.

Finde ich alles nicht so sinnvoll. Reicht es nicht, dass man sich registrieren muss? Hat den weiteren Vorteil das man den Autoren mal Namen zuordnen kann... [[User:Thorben|Thorben]]

File:HASHTB12.svg.png

2008-06-10T23:01:00Z

Thorben: from Wikipedia: http://upload.wikimedia.org/wikipedia/commons/thumb/9/90/HASHTB12.svg/362px-HASHTB12.svg.png

from Wikipedia: http://upload.wikimedia.org/wikipedia/commons/thumb/9/90/HASHTB12.svg/362px-HASHTB12.svg.png

Hashing und assoziative Arrays

2008-06-10T23:00:30Z

Thorben: /* Hashtabelle mit offener Adressierung (offenes Hashing) */

Mitschrift gibts [http://hci.iwr.uni-heidelberg.de/alda/images/AlDa.pdf hier] als PDF und [http://hci.iwr.uni-heidelberg.de/alda/images/Alda_source.pdf hier] gibts die TeX-Sourcen, leider als PDF weil man wohl keine .TeXs hochladen darf. Originale gibts auf Anfrage bei kirchner at cl dot uni minus heidelberg dot de. Wird das Package "listings" verwendet, das gibts bei [http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/ http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/]

Tipp- und sonstige Fehler dürfen gerne verbessert und erneut hochgeladen werden, oder gebt mir per Email Bescheid, dann pflege ich die Korrektur ein :)

Ich Finde dein Aufschrieb sollte ins Wiki übetragen werden, das bietet auch alles, was
du mit Latex machen kannst. Die Bäume kannst du z.B. mit Latex zeichnen, einen pro Seite und diese dann in eine png Datei umwandeln. Wie sowas geht kann man z.B. in den Quellen von doxygen oder mediawiki selbst nachlesen. Oder man zoomt rein und macht einen Screenshot :-)

== Hashtabelle mit linearer Verkettung ==
[[Image:HASHTB32.svg.png|frame|Prinzip ([http://en.wikipedia.org/wiki/Hash_table Quelle])]]

Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem
Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

===Implementation in Python===
''HashNode'' ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert
und mit Hilfe von ''next'' eine verkettete Liste realisiert
class HashNode:
def __init__(self,key,data,next):
self.key = key
self.data = data
self.next = next # Verkettung!

Die eigentliche Hashtabelle wird in der Klasse ''HashTable'' implementiert:
class HashTable:
def __init__(self):
self.capacity = ... # Geeignete Werte siehe unten
self.size = 0
self.array = [None]*self.capacity

In Python ([http://docs.python.org/ref/sequence-types.html Python Docs zum Thema]) wird der Zugriffsoperator ''[ ]'' für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:
def __setitem__(self, key, value)

so dass im Programmtext dann folgende Syntax möglich ist: <tt>a[key] = value</tt> (schreibender Zugriff auf <tt>a[key]</tt>).
Analog wird der lesende Zugriff <tt>value = a[key]</tt> wie folgt umgesetzt:
def __getitem__(self, key, value)

Implementierung der <tt>__setitem__</tt>-Funktion in der <tt>HashTable</tt>-Klasse:
def __setitem__(self, key, value):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key:
# Element key ist schon in der Tabelle
#Überschreibe die Daten mit dem neuen Wert
node.data = value
return
# Kollision des Hashwerts, probiere nächsten Key aus
node = node.next
# Kein Element hatte den richtigen Schlüssel.
# ==>Es gibt diesen Schlüssel noch nicht
# Füge also ein neues Element in die Hashtabelle ein

self.array[index] = HashNode(key, value, self.array[index])
# Der alte Anfang der Liste wurde der Nachfolger des neu eingefügten
# ersten Elements

self.size += 1

Und die Implementierung der <tt>__getitem__</tt> Funktionen:
def __getitem__(self, key):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key: # Gefunden!
return node.data
node = node.next
raise KeyError(key)

==== Wahl der Kapazität ====
In der C++ Standardbibliothek (Klasse <tt> [http://www.sgi.com/tech/stl/hash_map.htmlstd::hash_map std::hash_map]</tt>) wird die Hashtabelle häufig mit Hilfe der linearen Verkettung
imlementiert. Dabei wird <tt>capacity</tt> immer als ''Primzahl'' gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:
53, 97, 193, 398, 769, ...
[http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc++-v3/src/hashtable.cc GCC hashtable.cc (Primzahlen)] [http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc++-v3/include/tr1_impl/hashtable_policy.h GCC Hash Implementation]

Das hat zur Folge, dass <tt>hash(key) % self.capacity</tt> ''alle'' Bits von h benutzt (Eigenschaft aus der Zahlentheorie). Die Kapizität wird vergrößert, wenn <tt>size == capacity</tt> erreicht wird. Analog zum dynamischen Array werden die Daten dann aus dem alten Array (<tt>self.array</tt>) in ein entsprechend vergrößertes neues Array kopiert.

== Hashtabelle mit offener Adressierung (offenes Hashing) ==
[[Image:HASHTB12.svg.png|frame|Prinzip ([http://en.wikipedia.org/wiki/Hash_table Quelle])]]

[http://de.wikipedia.org/wiki/Hashtabelle#Hashing_mit_offener_Adressierung Wikipedia (de)]
[http://en.wikipedia.org/wiki/Open_addressing Wikipedia (en)]

Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

=== Idee ===
Wenn <tt>array[index]</tt> durch Kollision bereits vergeben ist, probiere einen
anderen Index aus.

* Das Array enthält pro Element höchstens ein (key,value)-Paar
* Das Array muss stets mindestens ''einen'' freien Platz haben (sonst gäbe es beim Ausprobieren anderer Indizes eine Endlosschleife). Es gilt immer <tt>self.size < self.capacity</tt>. Dies war bei der vorigen Hash-Implementation mit linearer Verkettung nicht notwendig (aber im Sinne schneller zugriffszeiten trotzdem wünschenswert).

=== Vorgehen bei Kollisionen ===

==== Sequentielles Sondieren====
Probiere den nächsten Index: <tt>index = (index+1) % capacity</tt>

* Vorteil: einfach
* Nachteil: Clusterbildung

Clusterbildung heißt, dass sich größere zusammenhängende Bereiche bilden die belegt sind, unterbrochen von Bereichen die komplett frei sind. Beim Versuche des Einfügens eines Elements an einen Platz, der schon belegt ist, muss jetzt das ganze Cluster sequentiell durchlaufen werden, bis ein freier Platz gefunden wird. Damit entspricht die Komplexität der Suche der mittleren Länge der belegten Bereiche, was sich entsprechend in einer langsamen Suche widerspiegelt.

==== Doppeltes Hashing ====
[http://de.wikipedia.org/wiki/Doppel-Hashing Wikipedia (de)] [http://en.wikipedia.org/wiki/Double_hashing Wikipedia (en)]

Bestimme einen neuen Index (bei Kollisionen) durch eine ''2. Hashfunktion''.

Das doppelte Hashing wird typischerweise in der Praxis angewendet und liegt auch der Python Implementierung des Datentyps [http://docs.python.org/tut/node7.html#SECTION007500000000000000000 Dictionary] (Syntax <tt>{'a':1, 'b':2, 'c':3}</tt> zugrunde.

Eine effiziente Implementierung dieses Datentyps ist für die Performance der Skriptsprache Python extrem wichtig, da z.B. beim Aufruf einer Funktion der auszuführunde Code in einem Dictionary unter dem Schlüssel ''Funktionsname'' nachgeschlagen wird oder die Werte lokaler Variablen innerhalb einer Funktion ebenfalls in einem Dictionary zu finden sind.

Für die Implementierung in Python werden wieder die obigen Klassen <tt>HashNode</tt> (das Attribut <tt>next</tt> kann allerdings jetzt entfernt werden) und <tt>HashTable</tt> benötigt, es folgen die angepassten Implementationen von <tt>__setitem__</tt> und <tt>__getitem__</tt>:

def __setitem__(self, key, value):
h = hash(key)
index = h % self.capacity
while True:
if self.array[index] is None or self.array[index].key is None:
# das Feld ist frei (1. Abfrage)
# oder das Feld ist als frei markiert (2. Abfrage)
self.array[index] = HashNode(key, value)
self.size +=1
return
if self.array[index].key == key:
# Es gibt diesen Schlüssel schon,
# überschreibe die Daten
self.array[index].data = value
return
# Letzter Fall: Kollision => neuer Index durch 2. Hashfunktion
index = (5*index+1+h) % self.capacity
h = h >> 5
(für den <tt>>></tt>-Operator, siehe die [http://docs.python.org/ref/shifting.html Python Dokumentation])

Die vorgestellte Implementierung orientiert sich an Pythons interner Dictionary Implementierung, der zugehörige Quelltext (mit ausführlichem Kommentar) findet sich unter [http://svn.python.org/view/*checkout*/python/trunk/Objects/dictobject.c dictobject.c Python Implementation (SVN)]

===== Beispiel =====
Mit Zahlen <math>2^5</math> statt <math>2^{32}</math>.
h=25, capacity=8
i_0 = 25%8 = 1
Es finde eine Kollision statt.
i_1 = (5*1+h)%8 = 31%8 = 7
h = h>>2 <==> h = (0b11001)>>2 = 0b00110 = 6
Es finde eine Kollision statt.
i_2 = (5*7+1+h)%8 =42%8 = 2
h = h>>2 <==> h=1
Es finde eine Kollision statt.
i_3 = (5*2+1+h)%8 = 12%8 = 4
h = h>>2 <==> h=0
Es finde eine Kollision statt.
i_4 = (5*4+1+0)%8 = 5
i_5 = (5*5+1)%8 = 2
i_6 = (5*2+1)%8 = 3
...
Allen Indizes werden erreicht bevor sich die Folge wiederholt.

===== Komplexität des offenen Hashings =====

* Annahme: uniformes Hashing, das heißt alle Indizes haben gleiche Wahrscheinlichkeit
* Füllstand <math>\alpha = \frac{\text{size}}{\text{capacity}}</math>

* '''Erfolglose Suche''' (d.h. es wird entweder ein neues Element eingefügt oder ein <tt>KeyError</tt> geworfen): Untere Schranke für die Komplexität ist <math>\Omega\left(\frac{1}{1-\alpha}\right)</math> Schritte (= Anzahl der notwendigen index-Berechnungen).
* '''Erfolgreiche Suche''' <math>\Omega\left(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\right)</math> Schritte.

{| border="1" cellspacing="0" cellpadding="5" align="center"
! <math>\alpha</math>
! 0.5
! 0.9
|-
| erfolglos
| 2.0
| 10
|-
| erfolgreich
| 1.4
| 2.6
|}

===== Wahl der Kapazität =====
In Python wird <tt>capacity</tt> Aufgrund der obigen Beobachtung so gewählt, dass <math>\alpha \leq 2/3</math>. Falls <math>\alpha</math> größer werden sollte, verdopple die Kapazität und kopiere das alte array in das neue Array (analog zum dynamischen Array)

In Python werden die Kapazitätsgrößen als Zweierpotenzen gewählt, also 4,8,16,32,...,
so dass <tt>h % self.capacity</tt> nur die unteren Bits von <tt>h</tt> benutzt.

== Anwendung von Hashing ==

* Hashtabelle, assoziatives Aray
* Sortieren in linearer Zeit (Übungsaufgabe 6.2)
* Suchen von Strings in Texten: Rabin-Karp-Algorithmus
* ...

=== Rabin Karp Algorithmus ===
[http://de.wikipedia.org/wiki/Rabin-Karp-Algorithmus Wikipedia (de)] [http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm Wikipedia (en)]

In Textverarbeitungsanwendungen ist eine häufig benutzte Funktion die ''Search & Replace'' Funktionalität. Die Suche sollte in O(len(text)) möglich sein, aber ein naiver Algorithmus braucht O(len(text)*len(searchstring))

==== Naive Implementierung der Suche ====
def search(text, s):
M, N = len(text), len(s)
for k in range(M-N):
if s==text[k:k+N]: # O(N), da N Zeichen verglichen werden müssen
return k
return -1 #nicht gefunden

==== Idee des Rabin Karp Algorithmus ====
Statt Vergleichen <tt>s==text[k:k+N]</tt>, die O(N) benötigen da N Vergleiche der Buchstaben durchgeführt werden müssen, Vergleiche die Hashs von Suchstring und dem zu untersuchenden Textabschnitt: <tt>hash(s) == hash(text[k:k+N])</tt>. Dabei muss natürlich <tt>hash(s)</tt> nur einmal berechnet werden, wohingegen <tt>hash(text[k:k+N])</tt> immer wieder neu berechnet werden muss. Damit der Vergleich O(1) sein kann, ist es deswegen erforderlich, eine solche Hashfunktion zu haben, die nicht alle Zeichen (das wäre O(N) ) einlesen muss, sondern die vorhergehende Hashfunktion mit einbezieht.

Eine solche Hashfunktion heißt ''Running Hash'' und funktioniert analog zum ''Sliding Mean''.

Die Running Hash Funktion berechnet in O(1) den hash von <tt>text[k+1:k+1+N]</tt> ausgehend vom hash für <tt>text[k:k+N]</tt>.

Idee: Interpretiere den Text als Ziffern in einer base d Darstellung:

<math>h_k = \text{text}[k]\cdot d^{N-1} + \text{text}[k]\cdot d^{N-2} + \cdots + \text{text}[k+N-1]</math>

Für die Basis 10 (Dezimalsystem) ergibt sich also

<math>h_k = \text{text}[k]\cdot {10}^{N-1} + \text{text}[k]\cdot {10}^{N-2} + \cdots + \text{text}[k+N-1]</math>

Daraus folgt

<math>h_{k+1} = 10\cdot h_k - \text{text}[k]\cdot {10}^{N} + \text{text}[k+N]</math>

Die Komplexität dieses Updates ist O(1), falls man <math>{10}^{N}</math> vorberechnet hat.

In der Realität wählt man dann d=32 und benutzt noch an einigen Stellen modulo Operationen, um die Zahlen nicht zu groß werden zu lassen.

==== Implementation ====
def searchRabinKarp(text, s):
ht, hs, dN = 0, 0, 1
M, N = len(text), len(s)
d, q = 32, 33554393
#q ist eine große Primzahl, aber so,
#dass d*q < 2**32 (um Überlauf zu vermeiden)

#Initialisierung
for k in range(N):
ht = (ht*d + ord(text[k])) % q
#ord() gibt die ASCIInummer des übergebenen Zeichens zurück
ds = (hs*d + ord( s[k] )) % q
dN = (dN*a) % q
#Die Variablen sind jetzt wie folgt initialisiert:
#ht = hash(text[0:N])
#hs = hash(s)
#dN = (d**N) % q

#Hauptschleife
k = 0
while k < M-N:
if hs == ht and s==text[k:k+N]:
return k # serch string an Position k gefunden
if k+N < M:
ht = (d*ht - dN * ord(text[k]) + dN*q + ord(text[k+N]) ) % q
k +=1
return -1 # search string nicht gefunden

Hashing und assoziative Arrays

2008-06-10T22:57:50Z

Thorben: /* Hashtabelle mit linearer Verkettung */

Mitschrift gibts [http://hci.iwr.uni-heidelberg.de/alda/images/AlDa.pdf hier] als PDF und [http://hci.iwr.uni-heidelberg.de/alda/images/Alda_source.pdf hier] gibts die TeX-Sourcen, leider als PDF weil man wohl keine .TeXs hochladen darf. Originale gibts auf Anfrage bei kirchner at cl dot uni minus heidelberg dot de. Wird das Package "listings" verwendet, das gibts bei [http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/ http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/]

Tipp- und sonstige Fehler dürfen gerne verbessert und erneut hochgeladen werden, oder gebt mir per Email Bescheid, dann pflege ich die Korrektur ein :)

Ich Finde dein Aufschrieb sollte ins Wiki übetragen werden, das bietet auch alles, was
du mit Latex machen kannst. Die Bäume kannst du z.B. mit Latex zeichnen, einen pro Seite und diese dann in eine png Datei umwandeln. Wie sowas geht kann man z.B. in den Quellen von doxygen oder mediawiki selbst nachlesen. Oder man zoomt rein und macht einen Screenshot :-)

== Hashtabelle mit linearer Verkettung ==
[[Image:HASHTB32.svg.png|frame|Prinzip ([http://en.wikipedia.org/wiki/Hash_table Quelle])]]

Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem
Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

===Implementation in Python===
''HashNode'' ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert
und mit Hilfe von ''next'' eine verkettete Liste realisiert
class HashNode:
def __init__(self,key,data,next):
self.key = key
self.data = data
self.next = next # Verkettung!

Die eigentliche Hashtabelle wird in der Klasse ''HashTable'' implementiert:
class HashTable:
def __init__(self):
self.capacity = ... # Geeignete Werte siehe unten
self.size = 0
self.array = [None]*self.capacity

In Python ([http://docs.python.org/ref/sequence-types.html Python Docs zum Thema]) wird der Zugriffsoperator ''[ ]'' für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:
def __setitem__(self, key, value)

so dass im Programmtext dann folgende Syntax möglich ist: <tt>a[key] = value</tt> (schreibender Zugriff auf <tt>a[key]</tt>).
Analog wird der lesende Zugriff <tt>value = a[key]</tt> wie folgt umgesetzt:
def __getitem__(self, key, value)

Implementierung der <tt>__setitem__</tt>-Funktion in der <tt>HashTable</tt>-Klasse:
def __setitem__(self, key, value):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key:
# Element key ist schon in der Tabelle
#Überschreibe die Daten mit dem neuen Wert
node.data = value
return
# Kollision des Hashwerts, probiere nächsten Key aus
node = node.next
# Kein Element hatte den richtigen Schlüssel.
# ==>Es gibt diesen Schlüssel noch nicht
# Füge also ein neues Element in die Hashtabelle ein

self.array[index] = HashNode(key, value, self.array[index])
# Der alte Anfang der Liste wurde der Nachfolger des neu eingefügten
# ersten Elements

self.size += 1

Und die Implementierung der <tt>__getitem__</tt> Funktionen:
def __getitem__(self, key):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key: # Gefunden!
return node.data
node = node.next
raise KeyError(key)

==== Wahl der Kapazität ====
In der C++ Standardbibliothek (Klasse <tt> [http://www.sgi.com/tech/stl/hash_map.htmlstd::hash_map std::hash_map]</tt>) wird die Hashtabelle häufig mit Hilfe der linearen Verkettung
imlementiert. Dabei wird <tt>capacity</tt> immer als ''Primzahl'' gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:
53, 97, 193, 398, 769, ...
[http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc++-v3/src/hashtable.cc GCC hashtable.cc (Primzahlen)] [http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc++-v3/include/tr1_impl/hashtable_policy.h GCC Hash Implementation]

Das hat zur Folge, dass <tt>hash(key) % self.capacity</tt> ''alle'' Bits von h benutzt (Eigenschaft aus der Zahlentheorie). Die Kapizität wird vergrößert, wenn <tt>size == capacity</tt> erreicht wird. Analog zum dynamischen Array werden die Daten dann aus dem alten Array (<tt>self.array</tt>) in ein entsprechend vergrößertes neues Array kopiert.

== Hashtabelle mit offener Adressierung (offenes Hashing) ==
[http://de.wikipedia.org/wiki/Hashtabelle#Hashing_mit_offener_Adressierung Wikipedia (de)]
[http://en.wikipedia.org/wiki/Open_addressing Wikipedia (en)]

Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

=== Idee ===
Wenn <tt>array[index]</tt> durch Kollision bereits vergeben ist, probiere einen
anderen Index aus.

* Das Array enthält pro Element höchstens ein (key,value)-Paar
* Das Array muss stets mindestens ''einen'' freien Platz haben (sonst gäbe es beim Ausprobieren anderer Indizes eine Endlosschleife). Es gilt immer <tt>self.size < self.capacity</tt>. Dies war bei der vorigen Hash-Implementation mit linearer Verkettung nicht notwendig (aber im Sinne schneller zugriffszeiten trotzdem wünschenswert).

=== Vorgehen bei Kollisionen ===

==== Sequentielles Sondieren====
Probiere den nächsten Index: <tt>index = (index+1) % capacity</tt>

* Vorteil: einfach
* Nachteil: Clusterbildung

Clusterbildung heißt, dass sich größere zusammenhängende Bereiche bilden die belegt sind, unterbrochen von Bereichen die komplett frei sind. Beim Versuche des Einfügens eines Elements an einen Platz, der schon belegt ist, muss jetzt das ganze Cluster sequentiell durchlaufen werden, bis ein freier Platz gefunden wird. Damit entspricht die Komplexität der Suche der mittleren Länge der belegten Bereiche, was sich entsprechend in einer langsamen Suche widerspiegelt.

==== Doppeltes Hashing ====
[http://de.wikipedia.org/wiki/Doppel-Hashing Wikipedia (de)] [http://en.wikipedia.org/wiki/Double_hashing Wikipedia (en)]

Bestimme einen neuen Index (bei Kollisionen) durch eine ''2. Hashfunktion''.

Das doppelte Hashing wird typischerweise in der Praxis angewendet und liegt auch der Python Implementierung des Datentyps [http://docs.python.org/tut/node7.html#SECTION007500000000000000000 Dictionary] (Syntax <tt>{'a':1, 'b':2, 'c':3}</tt> zugrunde.

Eine effiziente Implementierung dieses Datentyps ist für die Performance der Skriptsprache Python extrem wichtig, da z.B. beim Aufruf einer Funktion der auszuführunde Code in einem Dictionary unter dem Schlüssel ''Funktionsname'' nachgeschlagen wird oder die Werte lokaler Variablen innerhalb einer Funktion ebenfalls in einem Dictionary zu finden sind.

Für die Implementierung in Python werden wieder die obigen Klassen <tt>HashNode</tt> (das Attribut <tt>next</tt> kann allerdings jetzt entfernt werden) und <tt>HashTable</tt> benötigt, es folgen die angepassten Implementationen von <tt>__setitem__</tt> und <tt>__getitem__</tt>:

def __setitem__(self, key, value):
h = hash(key)
index = h % self.capacity
while True:
if self.array[index] is None or self.array[index].key is None:
# das Feld ist frei (1. Abfrage)
# oder das Feld ist als frei markiert (2. Abfrage)
self.array[index] = HashNode(key, value)
self.size +=1
return
if self.array[index].key == key:
# Es gibt diesen Schlüssel schon,
# überschreibe die Daten
self.array[index].data = value
return
# Letzter Fall: Kollision => neuer Index durch 2. Hashfunktion
index = (5*index+1+h) % self.capacity
h = h >> 5
(für den <tt>>></tt>-Operator, siehe die [http://docs.python.org/ref/shifting.html Python Dokumentation])

Die vorgestellte Implementierung orientiert sich an Pythons interner Dictionary Implementierung, der zugehörige Quelltext (mit ausführlichem Kommentar) findet sich unter [http://svn.python.org/view/*checkout*/python/trunk/Objects/dictobject.c dictobject.c Python Implementation (SVN)]

===== Beispiel =====
Mit Zahlen <math>2^5</math> statt <math>2^{32}</math>.
h=25, capacity=8
i_0 = 25%8 = 1
Es finde eine Kollision statt.
i_1 = (5*1+h)%8 = 31%8 = 7
h = h>>2 <==> h = (0b11001)>>2 = 0b00110 = 6
Es finde eine Kollision statt.
i_2 = (5*7+1+h)%8 =42%8 = 2
h = h>>2 <==> h=1
Es finde eine Kollision statt.
i_3 = (5*2+1+h)%8 = 12%8 = 4
h = h>>2 <==> h=0
Es finde eine Kollision statt.
i_4 = (5*4+1+0)%8 = 5
i_5 = (5*5+1)%8 = 2
i_6 = (5*2+1)%8 = 3
...
Allen Indizes werden erreicht bevor sich die Folge wiederholt.

===== Komplexität des offenen Hashings =====

* Annahme: uniformes Hashing, das heißt alle Indizes haben gleiche Wahrscheinlichkeit
* Füllstand <math>\alpha = \frac{\text{size}}{\text{capacity}}</math>

* '''Erfolglose Suche''' (d.h. es wird entweder ein neues Element eingefügt oder ein <tt>KeyError</tt> geworfen): Untere Schranke für die Komplexität ist <math>\Omega\left(\frac{1}{1-\alpha}\right)</math> Schritte (= Anzahl der notwendigen index-Berechnungen).
* '''Erfolgreiche Suche''' <math>\Omega\left(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\right)</math> Schritte.

{| border="1" cellspacing="0" cellpadding="5" align="center"
! <math>\alpha</math>
! 0.5
! 0.9
|-
| erfolglos
| 2.0
| 10
|-
| erfolgreich
| 1.4
| 2.6
|}

===== Wahl der Kapazität =====
In Python wird <tt>capacity</tt> Aufgrund der obigen Beobachtung so gewählt, dass <math>\alpha \leq 2/3</math>. Falls <math>\alpha</math> größer werden sollte, verdopple die Kapazität und kopiere das alte array in das neue Array (analog zum dynamischen Array)

In Python werden die Kapazitätsgrößen als Zweierpotenzen gewählt, also 4,8,16,32,...,
so dass <tt>h % self.capacity</tt> nur die unteren Bits von <tt>h</tt> benutzt.

== Anwendung von Hashing ==

* Hashtabelle, assoziatives Aray
* Sortieren in linearer Zeit (Übungsaufgabe 6.2)
* Suchen von Strings in Texten: Rabin-Karp-Algorithmus
* ...

=== Rabin Karp Algorithmus ===
[http://de.wikipedia.org/wiki/Rabin-Karp-Algorithmus Wikipedia (de)] [http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm Wikipedia (en)]

In Textverarbeitungsanwendungen ist eine häufig benutzte Funktion die ''Search & Replace'' Funktionalität. Die Suche sollte in O(len(text)) möglich sein, aber ein naiver Algorithmus braucht O(len(text)*len(searchstring))

==== Naive Implementierung der Suche ====
def search(text, s):
M, N = len(text), len(s)
for k in range(M-N):
if s==text[k:k+N]: # O(N), da N Zeichen verglichen werden müssen
return k
return -1 #nicht gefunden

==== Idee des Rabin Karp Algorithmus ====
Statt Vergleichen <tt>s==text[k:k+N]</tt>, die O(N) benötigen da N Vergleiche der Buchstaben durchgeführt werden müssen, Vergleiche die Hashs von Suchstring und dem zu untersuchenden Textabschnitt: <tt>hash(s) == hash(text[k:k+N])</tt>. Dabei muss natürlich <tt>hash(s)</tt> nur einmal berechnet werden, wohingegen <tt>hash(text[k:k+N])</tt> immer wieder neu berechnet werden muss. Damit der Vergleich O(1) sein kann, ist es deswegen erforderlich, eine solche Hashfunktion zu haben, die nicht alle Zeichen (das wäre O(N) ) einlesen muss, sondern die vorhergehende Hashfunktion mit einbezieht.

Eine solche Hashfunktion heißt ''Running Hash'' und funktioniert analog zum ''Sliding Mean''.

Die Running Hash Funktion berechnet in O(1) den hash von <tt>text[k+1:k+1+N]</tt> ausgehend vom hash für <tt>text[k:k+N]</tt>.

Idee: Interpretiere den Text als Ziffern in einer base d Darstellung:

<math>h_k = \text{text}[k]\cdot d^{N-1} + \text{text}[k]\cdot d^{N-2} + \cdots + \text{text}[k+N-1]</math>

Für die Basis 10 (Dezimalsystem) ergibt sich also

<math>h_k = \text{text}[k]\cdot {10}^{N-1} + \text{text}[k]\cdot {10}^{N-2} + \cdots + \text{text}[k+N-1]</math>

Daraus folgt

<math>h_{k+1} = 10\cdot h_k - \text{text}[k]\cdot {10}^{N} + \text{text}[k+N]</math>

Die Komplexität dieses Updates ist O(1), falls man <math>{10}^{N}</math> vorberechnet hat.

In der Realität wählt man dann d=32 und benutzt noch an einigen Stellen modulo Operationen, um die Zahlen nicht zu groß werden zu lassen.

==== Implementation ====
def searchRabinKarp(text, s):
ht, hs, dN = 0, 0, 1
M, N = len(text), len(s)
d, q = 32, 33554393
#q ist eine große Primzahl, aber so,
#dass d*q < 2**32 (um Überlauf zu vermeiden)

#Initialisierung
for k in range(N):
ht = (ht*d + ord(text[k])) % q
#ord() gibt die ASCIInummer des übergebenen Zeichens zurück
ds = (hs*d + ord( s[k] )) % q
dN = (dN*a) % q
#Die Variablen sind jetzt wie folgt initialisiert:
#ht = hash(text[0:N])
#hs = hash(s)
#dN = (d**N) % q

#Hauptschleife
k = 0
while k < M-N:
if hs == ht and s==text[k:k+N]:
return k # serch string an Position k gefunden
if k+N < M:
ht = (d*ht - dN * ord(text[k]) + dN*q + ord(text[k+N]) ) % q
k +=1
return -1 # search string nicht gefunden

File:HASHTB32.svg.png

2008-06-10T22:56:03Z

Thorben: from Wikipedia: http://en.wikipedia.org/wiki/Hash_table

from Wikipedia: http://en.wikipedia.org/wiki/Hash_table

Hashing und assoziative Arrays

2008-06-10T22:47:27Z

Thorben: /* Doppeltes Hashing */

Mitschrift gibts [http://hci.iwr.uni-heidelberg.de/alda/images/AlDa.pdf hier] als PDF und [http://hci.iwr.uni-heidelberg.de/alda/images/Alda_source.pdf hier] gibts die TeX-Sourcen, leider als PDF weil man wohl keine .TeXs hochladen darf. Originale gibts auf Anfrage bei kirchner at cl dot uni minus heidelberg dot de. Wird das Package "listings" verwendet, das gibts bei [http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/ http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/]

Tipp- und sonstige Fehler dürfen gerne verbessert und erneut hochgeladen werden, oder gebt mir per Email Bescheid, dann pflege ich die Korrektur ein :)

Ich Finde dein Aufschrieb sollte ins Wiki übetragen werden, das bietet auch alles, was
du mit Latex machen kannst. Die Bäume kannst du z.B. mit Latex zeichnen, einen pro Seite und diese dann in eine png Datei umwandeln. Wie sowas geht kann man z.B. in den Quellen von doxygen oder mediawiki selbst nachlesen. Oder man zoomt rein und macht einen Screenshot :-)

== Hashtabelle mit linearer Verkettung ==
Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem
Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

===Implementation in Python===
''HashNode'' ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert
und mit Hilfe von ''next'' eine verkettete Liste realisiert
class HashNode:
def __init__(self,key,data,next):
self.key = key
self.data = data
self.next = next # Verkettung!

Die eigentliche Hashtabelle wird in der Klasse ''HashTable'' implementiert:
class HashTable:
def __init__(self):
self.capacity = ... # Geeignete Werte siehe unten
self.size = 0
self.array = [None]*self.capacity

In Python ([http://docs.python.org/ref/sequence-types.html Python Docs zum Thema]) wird der Zugriffsoperator ''[ ]'' für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:
def __setitem__(self, key, value)

so dass im Programmtext dann folgende Syntax möglich ist: <tt>a[key] = value</tt> (schreibender Zugriff auf <tt>a[key]</tt>).
Analog wird der lesende Zugriff <tt>value = a[key]</tt> wie folgt umgesetzt:
def __getitem__(self, key, value)

Implementierung der <tt>__setitem__</tt>-Funktion in der <tt>HashTable</tt>-Klasse:
def __setitem__(self, key, value):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key:
# Element key ist schon in der Tabelle
#Überschreibe die Daten mit dem neuen Wert
node.data = value
return
# Kollision des Hashwerts, probiere nächsten Key aus
node = node.next
# Kein Element hatte den richtigen Schlüssel.
# ==>Es gibt diesen Schlüssel noch nicht
# Füge also ein neues Element in die Hashtabelle ein

self.array[index] = HashNode(key, value, self.array[index])
# Der alte Anfang der Liste wurde der Nachfolger des neu eingefügten
# ersten Elements

self.size += 1

Und die Implementierung der <tt>__getitem__</tt> Funktionen:
def __getitem__(self, key):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key: # Gefunden!
return node.data
node = node.next
raise KeyError(key)

==== Wahl der Kapazität ====
In der C++ Standardbibliothek (Klasse <tt> [http://www.sgi.com/tech/stl/hash_map.htmlstd::hash_map std::hash_map]</tt>) wird die Hashtabelle häufig mit Hilfe der linearen Verkettung
imlementiert. Dabei wird <tt>capacity</tt> immer als ''Primzahl'' gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:
53, 97, 193, 398, 769, ...
[http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc++-v3/src/hashtable.cc GCC hashtable.cc (Primzahlen)] [http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc++-v3/include/tr1_impl/hashtable_policy.h GCC Hash Implementation]

Das hat zur Folge, dass <tt>hash(key) % self.capacity</tt> ''alle'' Bits von h benutzt (Eigenschaft aus der Zahlentheorie). Die Kapizität wird vergrößert, wenn <tt>size == capacity</tt> erreicht wird. Analog zum dynamischen Array werden die Daten dann aus dem alten Array (<tt>self.array</tt>) in ein entsprechend vergrößertes neues Array kopiert.

== Hashtabelle mit offener Adressierung (offenes Hashing) ==
[http://de.wikipedia.org/wiki/Hashtabelle#Hashing_mit_offener_Adressierung Wikipedia (de)]
[http://en.wikipedia.org/wiki/Open_addressing Wikipedia (en)]

Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

=== Idee ===
Wenn <tt>array[index]</tt> durch Kollision bereits vergeben ist, probiere einen
anderen Index aus.

* Das Array enthält pro Element höchstens ein (key,value)-Paar
* Das Array muss stets mindestens ''einen'' freien Platz haben (sonst gäbe es beim Ausprobieren anderer Indizes eine Endlosschleife). Es gilt immer <tt>self.size < self.capacity</tt>. Dies war bei der vorigen Hash-Implementation mit linearer Verkettung nicht notwendig (aber im Sinne schneller zugriffszeiten trotzdem wünschenswert).

=== Vorgehen bei Kollisionen ===

==== Sequentielles Sondieren====
Probiere den nächsten Index: <tt>index = (index+1) % capacity</tt>

* Vorteil: einfach
* Nachteil: Clusterbildung

Clusterbildung heißt, dass sich größere zusammenhängende Bereiche bilden die belegt sind, unterbrochen von Bereichen die komplett frei sind. Beim Versuche des Einfügens eines Elements an einen Platz, der schon belegt ist, muss jetzt das ganze Cluster sequentiell durchlaufen werden, bis ein freier Platz gefunden wird. Damit entspricht die Komplexität der Suche der mittleren Länge der belegten Bereiche, was sich entsprechend in einer langsamen Suche widerspiegelt.

==== Doppeltes Hashing ====
[http://de.wikipedia.org/wiki/Doppel-Hashing Wikipedia (de)] [http://en.wikipedia.org/wiki/Double_hashing Wikipedia (en)]

Bestimme einen neuen Index (bei Kollisionen) durch eine ''2. Hashfunktion''.

Das doppelte Hashing wird typischerweise in der Praxis angewendet und liegt auch der Python Implementierung des Datentyps [http://docs.python.org/tut/node7.html#SECTION007500000000000000000 Dictionary] (Syntax <tt>{'a':1, 'b':2, 'c':3}</tt> zugrunde.

Eine effiziente Implementierung dieses Datentyps ist für die Performance der Skriptsprache Python extrem wichtig, da z.B. beim Aufruf einer Funktion der auszuführunde Code in einem Dictionary unter dem Schlüssel ''Funktionsname'' nachgeschlagen wird oder die Werte lokaler Variablen innerhalb einer Funktion ebenfalls in einem Dictionary zu finden sind.

Für die Implementierung in Python werden wieder die obigen Klassen <tt>HashNode</tt> (das Attribut <tt>next</tt> kann allerdings jetzt entfernt werden) und <tt>HashTable</tt> benötigt, es folgen die angepassten Implementationen von <tt>__setitem__</tt> und <tt>__getitem__</tt>:

def __setitem__(self, key, value):
h = hash(key)
index = h % self.capacity
while True:
if self.array[index] is None or self.array[index].key is None:
# das Feld ist frei (1. Abfrage)
# oder das Feld ist als frei markiert (2. Abfrage)
self.array[index] = HashNode(key, value)
self.size +=1
return
if self.array[index].key == key:
# Es gibt diesen Schlüssel schon,
# überschreibe die Daten
self.array[index].data = value
return
# Letzter Fall: Kollision => neuer Index durch 2. Hashfunktion
index = (5*index+1+h) % self.capacity
h = h >> 5
(für den <tt>>></tt>-Operator, siehe die [http://docs.python.org/ref/shifting.html Python Dokumentation])

Die vorgestellte Implementierung orientiert sich an Pythons interner Dictionary Implementierung, der zugehörige Quelltext (mit ausführlichem Kommentar) findet sich unter [http://svn.python.org/view/*checkout*/python/trunk/Objects/dictobject.c dictobject.c Python Implementation (SVN)]

===== Beispiel =====
Mit Zahlen <math>2^5</math> statt <math>2^{32}</math>.
h=25, capacity=8
i_0 = 25%8 = 1
Es finde eine Kollision statt.
i_1 = (5*1+h)%8 = 31%8 = 7
h = h>>2 <==> h = (0b11001)>>2 = 0b00110 = 6
Es finde eine Kollision statt.
i_2 = (5*7+1+h)%8 =42%8 = 2
h = h>>2 <==> h=1
Es finde eine Kollision statt.
i_3 = (5*2+1+h)%8 = 12%8 = 4
h = h>>2 <==> h=0
Es finde eine Kollision statt.
i_4 = (5*4+1+0)%8 = 5
i_5 = (5*5+1)%8 = 2
i_6 = (5*2+1)%8 = 3
...
Allen Indizes werden erreicht bevor sich die Folge wiederholt.

===== Komplexität des offenen Hashings =====

* Annahme: uniformes Hashing, das heißt alle Indizes haben gleiche Wahrscheinlichkeit
* Füllstand <math>\alpha = \frac{\text{size}}{\text{capacity}}</math>

* '''Erfolglose Suche''' (d.h. es wird entweder ein neues Element eingefügt oder ein <tt>KeyError</tt> geworfen): Untere Schranke für die Komplexität ist <math>\Omega\left(\frac{1}{1-\alpha}\right)</math> Schritte (= Anzahl der notwendigen index-Berechnungen).
* '''Erfolgreiche Suche''' <math>\Omega\left(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\right)</math> Schritte.

{| border="1" cellspacing="0" cellpadding="5" align="center"
! <math>\alpha</math>
! 0.5
! 0.9
|-
| erfolglos
| 2.0
| 10
|-
| erfolgreich
| 1.4
| 2.6
|}

===== Wahl der Kapazität =====
In Python wird <tt>capacity</tt> Aufgrund der obigen Beobachtung so gewählt, dass <math>\alpha \leq 2/3</math>. Falls <math>\alpha</math> größer werden sollte, verdopple die Kapazität und kopiere das alte array in das neue Array (analog zum dynamischen Array)

In Python werden die Kapazitätsgrößen als Zweierpotenzen gewählt, also 4,8,16,32,...,
so dass <tt>h % self.capacity</tt> nur die unteren Bits von <tt>h</tt> benutzt.

== Anwendung von Hashing ==

* Hashtabelle, assoziatives Aray
* Sortieren in linearer Zeit (Übungsaufgabe 6.2)
* Suchen von Strings in Texten: Rabin-Karp-Algorithmus
* ...

=== Rabin Karp Algorithmus ===
[http://de.wikipedia.org/wiki/Rabin-Karp-Algorithmus Wikipedia (de)] [http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm Wikipedia (en)]

In Textverarbeitungsanwendungen ist eine häufig benutzte Funktion die ''Search & Replace'' Funktionalität. Die Suche sollte in O(len(text)) möglich sein, aber ein naiver Algorithmus braucht O(len(text)*len(searchstring))

==== Naive Implementierung der Suche ====
def search(text, s):
M, N = len(text), len(s)
for k in range(M-N):
if s==text[k:k+N]: # O(N), da N Zeichen verglichen werden müssen
return k
return -1 #nicht gefunden

==== Idee des Rabin Karp Algorithmus ====
Statt Vergleichen <tt>s==text[k:k+N]</tt>, die O(N) benötigen da N Vergleiche der Buchstaben durchgeführt werden müssen, Vergleiche die Hashs von Suchstring und dem zu untersuchenden Textabschnitt: <tt>hash(s) == hash(text[k:k+N])</tt>. Dabei muss natürlich <tt>hash(s)</tt> nur einmal berechnet werden, wohingegen <tt>hash(text[k:k+N])</tt> immer wieder neu berechnet werden muss. Damit der Vergleich O(1) sein kann, ist es deswegen erforderlich, eine solche Hashfunktion zu haben, die nicht alle Zeichen (das wäre O(N) ) einlesen muss, sondern die vorhergehende Hashfunktion mit einbezieht.

Eine solche Hashfunktion heißt ''Running Hash'' und funktioniert analog zum ''Sliding Mean''.

Die Running Hash Funktion berechnet in O(1) den hash von <tt>text[k+1:k+1+N]</tt> ausgehend vom hash für <tt>text[k:k+N]</tt>.

Idee: Interpretiere den Text als Ziffern in einer base d Darstellung:

<math>h_k = \text{text}[k]\cdot d^{N-1} + \text{text}[k]\cdot d^{N-2} + \cdots + \text{text}[k+N-1]</math>

Für die Basis 10 (Dezimalsystem) ergibt sich also

<math>h_k = \text{text}[k]\cdot {10}^{N-1} + \text{text}[k]\cdot {10}^{N-2} + \cdots + \text{text}[k+N-1]</math>

Daraus folgt

<math>h_{k+1} = 10\cdot h_k - \text{text}[k]\cdot {10}^{N} + \text{text}[k+N]</math>

Die Komplexität dieses Updates ist O(1), falls man <math>{10}^{N}</math> vorberechnet hat.

In der Realität wählt man dann d=32 und benutzt noch an einigen Stellen modulo Operationen, um die Zahlen nicht zu groß werden zu lassen.

==== Implementation ====
def searchRabinKarp(text, s):
ht, hs, dN = 0, 0, 1
M, N = len(text), len(s)
d, q = 32, 33554393
#q ist eine große Primzahl, aber so,
#dass d*q < 2**32 (um Überlauf zu vermeiden)

#Initialisierung
for k in range(N):
ht = (ht*d + ord(text[k])) % q
#ord() gibt die ASCIInummer des übergebenen Zeichens zurück
ds = (hs*d + ord( s[k] )) % q
dN = (dN*a) % q
#Die Variablen sind jetzt wie folgt initialisiert:
#ht = hash(text[0:N])
#hs = hash(s)
#dN = (d**N) % q

#Hauptschleife
k = 0
while k < M-N:
if hs == ht and s==text[k:k+N]:
return k # serch string an Position k gefunden
if k+N < M:
ht = (d*ht - dN * ord(text[k]) + dN*q + ord(text[k+N]) ) % q
k +=1
return -1 # search string nicht gefunden

Hashing und assoziative Arrays

2008-06-10T22:44:51Z

Thorben: /* Doppeltes Hashing */

Mitschrift gibts [http://hci.iwr.uni-heidelberg.de/alda/images/AlDa.pdf hier] als PDF und [http://hci.iwr.uni-heidelberg.de/alda/images/Alda_source.pdf hier] gibts die TeX-Sourcen, leider als PDF weil man wohl keine .TeXs hochladen darf. Originale gibts auf Anfrage bei kirchner at cl dot uni minus heidelberg dot de. Wird das Package "listings" verwendet, das gibts bei [http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/ http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/]

Tipp- und sonstige Fehler dürfen gerne verbessert und erneut hochgeladen werden, oder gebt mir per Email Bescheid, dann pflege ich die Korrektur ein :)

Ich Finde dein Aufschrieb sollte ins Wiki übetragen werden, das bietet auch alles, was
du mit Latex machen kannst. Die Bäume kannst du z.B. mit Latex zeichnen, einen pro Seite und diese dann in eine png Datei umwandeln. Wie sowas geht kann man z.B. in den Quellen von doxygen oder mediawiki selbst nachlesen. Oder man zoomt rein und macht einen Screenshot :-)

== Hashtabelle mit linearer Verkettung ==
Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem
Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

===Implementation in Python===
''HashNode'' ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert
und mit Hilfe von ''next'' eine verkettete Liste realisiert
class HashNode:
def __init__(self,key,data,next):
self.key = key
self.data = data
self.next = next # Verkettung!

Die eigentliche Hashtabelle wird in der Klasse ''HashTable'' implementiert:
class HashTable:
def __init__(self):
self.capacity = ... # Geeignete Werte siehe unten
self.size = 0
self.array = [None]*self.capacity

In Python ([http://docs.python.org/ref/sequence-types.html Python Docs zum Thema]) wird der Zugriffsoperator ''[ ]'' für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:
def __setitem__(self, key, value)

so dass im Programmtext dann folgende Syntax möglich ist: <tt>a[key] = value</tt> (schreibender Zugriff auf <tt>a[key]</tt>).
Analog wird der lesende Zugriff <tt>value = a[key]</tt> wie folgt umgesetzt:
def __getitem__(self, key, value)

Implementierung der <tt>__setitem__</tt>-Funktion in der <tt>HashTable</tt>-Klasse:
def __setitem__(self, key, value):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key:
# Element key ist schon in der Tabelle
#Überschreibe die Daten mit dem neuen Wert
node.data = value
return
# Kollision des Hashwerts, probiere nächsten Key aus
node = node.next
# Kein Element hatte den richtigen Schlüssel.
# ==>Es gibt diesen Schlüssel noch nicht
# Füge also ein neues Element in die Hashtabelle ein

self.array[index] = HashNode(key, value, self.array[index])
# Der alte Anfang der Liste wurde der Nachfolger des neu eingefügten
# ersten Elements

self.size += 1

Und die Implementierung der <tt>__getitem__</tt> Funktionen:
def __getitem__(self, key):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key: # Gefunden!
return node.data
node = node.next
raise KeyError(key)

==== Wahl der Kapazität ====
In der C++ Standardbibliothek (Klasse <tt> [http://www.sgi.com/tech/stl/hash_map.htmlstd::hash_map std::hash_map]</tt>) wird die Hashtabelle häufig mit Hilfe der linearen Verkettung
imlementiert. Dabei wird <tt>capacity</tt> immer als ''Primzahl'' gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:
53, 97, 193, 398, 769, ...
[http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc++-v3/src/hashtable.cc GCC hashtable.cc (Primzahlen)] [http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc++-v3/include/tr1_impl/hashtable_policy.h GCC Hash Implementation]

Das hat zur Folge, dass <tt>hash(key) % self.capacity</tt> ''alle'' Bits von h benutzt (Eigenschaft aus der Zahlentheorie). Die Kapizität wird vergrößert, wenn <tt>size == capacity</tt> erreicht wird. Analog zum dynamischen Array werden die Daten dann aus dem alten Array (<tt>self.array</tt>) in ein entsprechend vergrößertes neues Array kopiert.

== Hashtabelle mit offener Adressierung (offenes Hashing) ==
[http://de.wikipedia.org/wiki/Hashtabelle#Hashing_mit_offener_Adressierung Wikipedia (de)]
[http://en.wikipedia.org/wiki/Open_addressing Wikipedia (en)]

Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

=== Idee ===
Wenn <tt>array[index]</tt> durch Kollision bereits vergeben ist, probiere einen
anderen Index aus.

* Das Array enthält pro Element höchstens ein (key,value)-Paar
* Das Array muss stets mindestens ''einen'' freien Platz haben (sonst gäbe es beim Ausprobieren anderer Indizes eine Endlosschleife). Es gilt immer <tt>self.size < self.capacity</tt>. Dies war bei der vorigen Hash-Implementation mit linearer Verkettung nicht notwendig (aber im Sinne schneller zugriffszeiten trotzdem wünschenswert).

=== Vorgehen bei Kollisionen ===

==== Sequentielles Sondieren====
Probiere den nächsten Index: <tt>index = (index+1) % capacity</tt>

* Vorteil: einfach
* Nachteil: Clusterbildung

Clusterbildung heißt, dass sich größere zusammenhängende Bereiche bilden die belegt sind, unterbrochen von Bereichen die komplett frei sind. Beim Versuche des Einfügens eines Elements an einen Platz, der schon belegt ist, muss jetzt das ganze Cluster sequentiell durchlaufen werden, bis ein freier Platz gefunden wird. Damit entspricht die Komplexität der Suche der mittleren Länge der belegten Bereiche, was sich entsprechend in einer langsamen Suche widerspiegelt.

==== Doppeltes Hashing ====
[http://de.wikipedia.org/wiki/Doppel-Hashing Wikipedia (de)] [http://en.wikipedia.org/wiki/Double_hashing Wikipedia (en)]

Bestimme einen neuen Index (bei Kollisionen) durch eine ''2. Hashfunktion''.

Das doppelte Hashing wird typischerweise in der Praxis angewendet und liegt auch der Python Implementierung des Datentyps [http://docs.python.org/tut/node7.html#SECTION007500000000000000000 Dictionary] (Syntax <tt>{'a':1, 'b':2, 'c':3}</tt> zugrunde.

Eine effiziente Implementierung dieses Datentyps ist für die Performance der Skriptsprache Python extrem wichtig, da z.B. beim Aufruf einer Funktion der auszuführunde Code in einem Dictionary unter dem Schlüssel ''Funktionsname'' nachgeschlagen wird oder die Werte lokaler Variablen innerhalb einer Funktion ebenfalls in einem Dictionary zu finden sind.

Für die Implementierung in Python werden wieder die obigen Klassen <tt>HashNode</tt> (das Attribut <tt>next</tt> kann allerdings jetzt entfernt werden) und <tt>HashTable</tt> benötigt, es folgen die angepassten Implementationen von <tt>__setitem__</tt> und <tt>__getitem__</tt>:

def __setitem__(self, key, value):
h = hash(key)
index = h % self.capacity
while True:
if self.array[index] is None or self.array[index].key is None:
# das Feld ist frei (1. Abfrage)
# oder das Feld ist als frei markiert (2. Abfrage)
self.array[index] = HashNode(key, value)
self.size +=1
return
if self.array[index].key == key:
# Es gibt diesen Schlüssel schon,
# überschreibe die Daten
self.array[index].data = value
return
# Letzter Fall: Kollision => neuer Index durch 2. Hashfunktion
index = (5*index+1+h) % self.capacity
h = h >> 5

Die vorgestellte Implementierung orientiert sich an Pythons interner Dictionary Implementierung, der zugehörige Quelltext (mit ausführlichem Kommentar) findet sich unter [http://svn.python.org/view/*checkout*/python/trunk/Objects/dictobject.c dictobject.c Python Implementation (SVN)]

===== Beispiel =====
Mit Zahlen <math>2^5</math> statt <math>2^{32}</math>.
h=25, capacity=8
i_0 = 25%8 = 1
Es finde eine Kollision statt.
i_1 = (5*1+h)%8 = 31%8 = 7
h = h>>2 <==> h = (0b11001)>>2 = 0b00110 = 6
Es finde eine Kollision statt.
i_2 = (5*7+1+h)%8 =42%8 = 2
h = h>>2 <==> h=1
Es finde eine Kollision statt.
i_3 = (5*2+1+h)%8 = 12%8 = 4
h = h>>2 <==> h=0
Es finde eine Kollision statt.
i_4 = (5*4+1+0)%8 = 5
i_5 = (5*5+1)%8 = 2
i_6 = (5*2+1)%8 = 3
...
Allen Indizes werden erreicht bevor sich die Folge wiederholt.

===== Komplexität des offenen Hashings =====

* Annahme: uniformes Hashing, das heißt alle Indizes haben gleiche Wahrscheinlichkeit
* Füllstand <math>\alpha = \frac{\text{size}}{\text{capacity}}</math>

* '''Erfolglose Suche''' (d.h. es wird entweder ein neues Element eingefügt oder ein <tt>KeyError</tt> geworfen): Untere Schranke für die Komplexität ist <math>\Omega\left(\frac{1}{1-\alpha}\right)</math> Schritte (= Anzahl der notwendigen index-Berechnungen).
* '''Erfolgreiche Suche''' <math>\Omega\left(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\right)</math> Schritte.

{| border="1" cellspacing="0" cellpadding="5" align="center"
! <math>\alpha</math>
! 0.5
! 0.9
|-
| erfolglos
| 2.0
| 10
|-
| erfolgreich
| 1.4
| 2.6
|}

===== Wahl der Kapazität =====
In Python wird <tt>capacity</tt> Aufgrund der obigen Beobachtung so gewählt, dass <math>\alpha \leq 2/3</math>. Falls <math>\alpha</math> größer werden sollte, verdopple die Kapazität und kopiere das alte array in das neue Array (analog zum dynamischen Array)

In Python werden die Kapazitätsgrößen als Zweierpotenzen gewählt, also 4,8,16,32,...,
so dass <tt>h % self.capacity</tt> nur die unteren Bits von <tt>h</tt> benutzt.

== Anwendung von Hashing ==

* Hashtabelle, assoziatives Aray
* Sortieren in linearer Zeit (Übungsaufgabe 6.2)
* Suchen von Strings in Texten: Rabin-Karp-Algorithmus
* ...

=== Rabin Karp Algorithmus ===
[http://de.wikipedia.org/wiki/Rabin-Karp-Algorithmus Wikipedia (de)] [http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm Wikipedia (en)]

In Textverarbeitungsanwendungen ist eine häufig benutzte Funktion die ''Search & Replace'' Funktionalität. Die Suche sollte in O(len(text)) möglich sein, aber ein naiver Algorithmus braucht O(len(text)*len(searchstring))

==== Naive Implementierung der Suche ====
def search(text, s):
M, N = len(text), len(s)
for k in range(M-N):
if s==text[k:k+N]: # O(N), da N Zeichen verglichen werden müssen
return k
return -1 #nicht gefunden

==== Idee des Rabin Karp Algorithmus ====
Statt Vergleichen <tt>s==text[k:k+N]</tt>, die O(N) benötigen da N Vergleiche der Buchstaben durchgeführt werden müssen, Vergleiche die Hashs von Suchstring und dem zu untersuchenden Textabschnitt: <tt>hash(s) == hash(text[k:k+N])</tt>. Dabei muss natürlich <tt>hash(s)</tt> nur einmal berechnet werden, wohingegen <tt>hash(text[k:k+N])</tt> immer wieder neu berechnet werden muss. Damit der Vergleich O(1) sein kann, ist es deswegen erforderlich, eine solche Hashfunktion zu haben, die nicht alle Zeichen (das wäre O(N) ) einlesen muss, sondern die vorhergehende Hashfunktion mit einbezieht.

Eine solche Hashfunktion heißt ''Running Hash'' und funktioniert analog zum ''Sliding Mean''.

Die Running Hash Funktion berechnet in O(1) den hash von <tt>text[k+1:k+1+N]</tt> ausgehend vom hash für <tt>text[k:k+N]</tt>.

Idee: Interpretiere den Text als Ziffern in einer base d Darstellung:

<math>h_k = \text{text}[k]\cdot d^{N-1} + \text{text}[k]\cdot d^{N-2} + \cdots + \text{text}[k+N-1]</math>

Für die Basis 10 (Dezimalsystem) ergibt sich also

<math>h_k = \text{text}[k]\cdot {10}^{N-1} + \text{text}[k]\cdot {10}^{N-2} + \cdots + \text{text}[k+N-1]</math>

Daraus folgt

<math>h_{k+1} = 10\cdot h_k - \text{text}[k]\cdot {10}^{N} + \text{text}[k+N]</math>

Die Komplexität dieses Updates ist O(1), falls man <math>{10}^{N}</math> vorberechnet hat.

In der Realität wählt man dann d=32 und benutzt noch an einigen Stellen modulo Operationen, um die Zahlen nicht zu groß werden zu lassen.

==== Implementation ====
def searchRabinKarp(text, s):
ht, hs, dN = 0, 0, 1
M, N = len(text), len(s)
d, q = 32, 33554393
#q ist eine große Primzahl, aber so,
#dass d*q < 2**32 (um Überlauf zu vermeiden)

#Initialisierung
for k in range(N):
ht = (ht*d + ord(text[k])) % q
#ord() gibt die ASCIInummer des übergebenen Zeichens zurück
ds = (hs*d + ord( s[k] )) % q
dN = (dN*a) % q
#Die Variablen sind jetzt wie folgt initialisiert:
#ht = hash(text[0:N])
#hs = hash(s)
#dN = (d**N) % q

#Hauptschleife
k = 0
while k < M-N:
if hs == ht and s==text[k:k+N]:
return k # serch string an Position k gefunden
if k+N < M:
ht = (d*ht - dN * ord(text[k]) + dN*q + ord(text[k+N]) ) % q
k +=1
return -1 # search string nicht gefunden

Hashing und assoziative Arrays

2008-06-10T22:32:32Z

Thorben: /* Doppeltes Hashing */

Mitschrift gibts [http://hci.iwr.uni-heidelberg.de/alda/images/AlDa.pdf hier] als PDF und [http://hci.iwr.uni-heidelberg.de/alda/images/Alda_source.pdf hier] gibts die TeX-Sourcen, leider als PDF weil man wohl keine .TeXs hochladen darf. Originale gibts auf Anfrage bei kirchner at cl dot uni minus heidelberg dot de. Wird das Package "listings" verwendet, das gibts bei [http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/ http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/]

Tipp- und sonstige Fehler dürfen gerne verbessert und erneut hochgeladen werden, oder gebt mir per Email Bescheid, dann pflege ich die Korrektur ein :)

Ich Finde dein Aufschrieb sollte ins Wiki übetragen werden, das bietet auch alles, was
du mit Latex machen kannst. Die Bäume kannst du z.B. mit Latex zeichnen, einen pro Seite und diese dann in eine png Datei umwandeln. Wie sowas geht kann man z.B. in den Quellen von doxygen oder mediawiki selbst nachlesen. Oder man zoomt rein und macht einen Screenshot :-)

== Hashtabelle mit linearer Verkettung ==
Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem
Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

===Implementation in Python===
''HashNode'' ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert
und mit Hilfe von ''next'' eine verkettete Liste realisiert
class HashNode:
def __init__(self,key,data,next):
self.key = key
self.data = data
self.next = next # Verkettung!

Die eigentliche Hashtabelle wird in der Klasse ''HashTable'' implementiert:
class HashTable:
def __init__(self):
self.capacity = ... # Geeignete Werte siehe unten
self.size = 0
self.array = [None]*self.capacity

In Python ([http://docs.python.org/ref/sequence-types.html Python Docs zum Thema]) wird der Zugriffsoperator ''[ ]'' für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:
def __setitem__(self, key, value)

so dass im Programmtext dann folgende Syntax möglich ist: <tt>a[key] = value</tt> (schreibender Zugriff auf <tt>a[key]</tt>).
Analog wird der lesende Zugriff <tt>value = a[key]</tt> wie folgt umgesetzt:
def __getitem__(self, key, value)

Implementierung der <tt>__setitem__</tt>-Funktion in der <tt>HashTable</tt>-Klasse:
def __setitem__(self, key, value):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key:
# Element key ist schon in der Tabelle
#Überschreibe die Daten mit dem neuen Wert
node.data = value
return
# Kollision des Hashwerts, probiere nächsten Key aus
node = node.next
# Kein Element hatte den richtigen Schlüssel.
# ==>Es gibt diesen Schlüssel noch nicht
# Füge also ein neues Element in die Hashtabelle ein

self.array[index] = HashNode(key, value, self.array[index])
# Der alte Anfang der Liste wurde der Nachfolger des neu eingefügten
# ersten Elements

self.size += 1

Und die Implementierung der <tt>__getitem__</tt> Funktionen:
def __getitem__(self, key):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key: # Gefunden!
return node.data
node = node.next
raise KeyError(key)

==== Wahl der Kapazität ====
In der C++ Standardbibliothek (Klasse <tt> [http://www.sgi.com/tech/stl/hash_map.htmlstd::hash_map std::hash_map]</tt>) wird die Hashtabelle häufig mit Hilfe der linearen Verkettung
imlementiert. Dabei wird <tt>capacity</tt> immer als ''Primzahl'' gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:
53, 97, 193, 398, 769, ...
[http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc++-v3/src/hashtable.cc GCC hashtable.cc (Primzahlen)] [http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc++-v3/include/tr1_impl/hashtable_policy.h GCC Hash Implementation]

Das hat zur Folge, dass <tt>hash(key) % self.capacity</tt> ''alle'' Bits von h benutzt (Eigenschaft aus der Zahlentheorie). Die Kapizität wird vergrößert, wenn <tt>size == capacity</tt> erreicht wird. Analog zum dynamischen Array werden die Daten dann aus dem alten Array (<tt>self.array</tt>) in ein entsprechend vergrößertes neues Array kopiert.

== Hashtabelle mit offener Adressierung (offenes Hashing) ==
[http://de.wikipedia.org/wiki/Hashtabelle#Hashing_mit_offener_Adressierung Wikipedia (de)]
[http://en.wikipedia.org/wiki/Open_addressing Wikipedia (en)]

Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

=== Idee ===
Wenn <tt>array[index]</tt> durch Kollision bereits vergeben ist, probiere einen
anderen Index aus.

* Das Array enthält pro Element höchstens ein (key,value)-Paar
* Das Array muss stets mindestens ''einen'' freien Platz haben (sonst gäbe es beim Ausprobieren anderer Indizes eine Endlosschleife). Es gilt immer <tt>self.size < self.capacity</tt>. Dies war bei der vorigen Hash-Implementation mit linearer Verkettung nicht notwendig (aber im Sinne schneller zugriffszeiten trotzdem wünschenswert).

=== Vorgehen bei Kollisionen ===

==== Sequentielles Sondieren====
Probiere den nächsten Index: <tt>index = (index+1) % capacity</tt>

* Vorteil: einfach
* Nachteil: Clusterbildung

Clusterbildung heißt, dass sich größere zusammenhängende Bereiche bilden die belegt sind, unterbrochen von Bereichen die komplett frei sind. Beim Versuche des Einfügens eines Elements an einen Platz, der schon belegt ist, muss jetzt das ganze Cluster sequentiell durchlaufen werden, bis ein freier Platz gefunden wird. Damit entspricht die Komplexität der Suche der mittleren Länge der belegten Bereiche, was sich entsprechend in einer langsamen Suche widerspiegelt.

==== Doppeltes Hashing ====
[http://de.wikipedia.org/wiki/Doppel-Hashing Wikipedia (de)] [http://en.wikipedia.org/wiki/Double_hashing Wikipedia (en)]

Bestimme einen neuen Index (bei Kollisionen) durch eine ''2. Hashfunktion''.

Das doppelte Hashing wird typischerweise in der Praxis angewendet und liegt auch der Python Implementierung des Datentyps [http://docs.python.org/tut/node7.html#SECTION007500000000000000000 Dictionary] (Syntax <tt>{'a':1, 'b':2, 'c':3}</tt> zugrunde.

Eine effiziente Implementierung dieses Datentyps ist für die Performance der Skriptsprache Python extrem wichtig, da z.B. beim Aufruf einer Funktion der auszuführunde Code in einem Dictionary unter dem Schlüssel ''Funktionsname'' nachgeschlagen wird oder die Werte lokaler Variablen innerhalb einer Funktion ebenfalls in einem Dictionary zu finden sind.

Für die Implementierung in Python werden wieder die obigen Klassen <tt>HashNode</tt> (das Attribut <tt>next</tt> kann allerdings jetzt entfernt werden) und <tt>HashTable</tt> benötigt, es folgen die angepassten Implementationen von <tt>__setitem__</tt> und <tt>__getitem__</tt>:

def __setitem__(self, key, value):
h = hash(key)
index = h % self.capacity
while True:
if self.array[index] is None or self.array[index].key is None:
# das Feld ist frei (1. Abfrage)
# oder das Feld ist als frei markiert (2. Abfrage)
self.array[index] = HashNode(key, value)
self.size +=1
return
if self.array[index].key == key:
# Es gibt diesen Schlüssel schon,
# überschreibe die Daten
self.array[index].data = value
return
# Letzter Fall: Kollision => neuer Index durch 2. Hashfunktion
index = (5*index+1+h) % self.capacity
h = h >> 5

Die vorgestellte Implementierung orientiert sich an Pythons interner Dictionary Implementierung, der zugehörige Quelltext (mit ausführlichem Kommentar) findet sich unter [http://svn.python.org/view/*checkout*/python/trunk/Objects/dictobject.c dictobject.c Python Implementation (SVN)]

===== Komplexität des offenen Hashings =====

* Annahme: uniformes Hashing, das heißt alle Indizes haben gleiche Wahrscheinlichkeit
* Füllstand <math>\alpha = \frac{\text{size}}{\text{capacity}}</math>

* '''Erfolglose Suche''' (d.h. es wird entweder ein neues Element eingefügt oder ein <tt>KeyError</tt> geworfen): Untere Schranke für die Komplexität ist <math>\Omega\left(\frac{1}{1-\alpha}\right)</math> Schritte (= Anzahl der notwendigen index-Berechnungen).
* '''Erfolgreiche Suche''' <math>\Omega\left(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\right)</math> Schritte.

{| border="1" cellspacing="0" cellpadding="5" align="center"
! <math>\alpha</math>
! 0.5
! 0.9
|-
| erfolglos
| 2.0
| 10
|-
| erfolgreich
| 1.4
| 2.6
|}

===== Wahl der Kapazität =====
In Python wird <tt>capacity</tt> Aufgrund der obigen Beobachtung so gewählt, dass <math>\alpha \leq 2/3</math>. Falls <math>\alpha</math> größer werden sollte, verdopple die Kapazität und kopiere das alte array in das neue Array (analog zum dynamischen Array)

In Python werden die Kapazitätsgrößen als Zweierpotenzen gewählt, also 4,8,16,32,...,
so dass <tt>h % self.capacity</tt> nur die unteren Bits von <tt>h</tt> benutzt.

== Anwendung von Hashing ==

* Hashtabelle, assoziatives Aray
* Sortieren in linearer Zeit (Übungsaufgabe 6.2)
* Suchen von Strings in Texten: Rabin-Karp-Algorithmus
* ...

=== Rabin Karp Algorithmus ===
[http://de.wikipedia.org/wiki/Rabin-Karp-Algorithmus Wikipedia (de)] [http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm Wikipedia (en)]

In Textverarbeitungsanwendungen ist eine häufig benutzte Funktion die ''Search & Replace'' Funktionalität. Die Suche sollte in O(len(text)) möglich sein, aber ein naiver Algorithmus braucht O(len(text)*len(searchstring))

==== Naive Implementierung der Suche ====
def search(text, s):
M, N = len(text), len(s)
for k in range(M-N):
if s==text[k:k+N]: # O(N), da N Zeichen verglichen werden müssen
return k
return -1 #nicht gefunden

==== Idee des Rabin Karp Algorithmus ====
Statt Vergleichen <tt>s==text[k:k+N]</tt>, die O(N) benötigen da N Vergleiche der Buchstaben durchgeführt werden müssen, Vergleiche die Hashs von Suchstring und dem zu untersuchenden Textabschnitt: <tt>hash(s) == hash(text[k:k+N])</tt>. Dabei muss natürlich <tt>hash(s)</tt> nur einmal berechnet werden, wohingegen <tt>hash(text[k:k+N])</tt> immer wieder neu berechnet werden muss. Damit der Vergleich O(1) sein kann, ist es deswegen erforderlich, eine solche Hashfunktion zu haben, die nicht alle Zeichen (das wäre O(N) ) einlesen muss, sondern die vorhergehende Hashfunktion mit einbezieht.

Eine solche Hashfunktion heißt ''Running Hash'' und funktioniert analog zum ''Sliding Mean''.

Die Running Hash Funktion berechnet in O(1) den hash von <tt>text[k+1:k+1+N]</tt> ausgehend vom hash für <tt>text[k:k+N]</tt>.

Idee: Interpretiere den Text als Ziffern in einer base d Darstellung:

<math>h_k = \text{text}[k]\cdot d^{N-1} + \text{text}[k]\cdot d^{N-2} + \cdots + \text{text}[k+N-1]</math>

Für die Basis 10 (Dezimalsystem) ergibt sich also

<math>h_k = \text{text}[k]\cdot {10}^{N-1} + \text{text}[k]\cdot {10}^{N-2} + \cdots + \text{text}[k+N-1]</math>

Daraus folgt

<math>h_{k+1} = 10\cdot h_k - \text{text}[k]\cdot {10}^{N} + \text{text}[k+N]</math>

Die Komplexität dieses Updates ist O(1), falls man <math>{10}^{N}</math> vorberechnet hat.

In der Realität wählt man dann d=32 und benutzt noch an einigen Stellen modulo Operationen, um die Zahlen nicht zu groß werden zu lassen.

==== Implementation ====
def searchRabinKarp(text, s):
ht, hs, dN = 0, 0, 1
M, N = len(text), len(s)
d, q = 32, 33554393
#q ist eine große Primzahl, aber so,
#dass d*q < 2**32 (um Überlauf zu vermeiden)

#Initialisierung
for k in range(N):
ht = (ht*d + ord(text[k])) % q
#ord() gibt die ASCIInummer des übergebenen Zeichens zurück
ds = (hs*d + ord( s[k] )) % q
dN = (dN*a) % q
#Die Variablen sind jetzt wie folgt initialisiert:
#ht = hash(text[0:N])
#hs = hash(s)
#dN = (d**N) % q

#Hauptschleife
k = 0
while k < M-N:
if hs == ht and s==text[k:k+N]:
return k # serch string an Position k gefunden
if k+N < M:
ht = (d*ht - dN * ord(text[k]) + dN*q + ord(text[k+N]) ) % q
k +=1
return -1 # search string nicht gefunden

Hashing und assoziative Arrays

2008-06-10T22:31:24Z

Thorben: /* Doppeltes Hashing */

Mitschrift gibts [http://hci.iwr.uni-heidelberg.de/alda/images/AlDa.pdf hier] als PDF und [http://hci.iwr.uni-heidelberg.de/alda/images/Alda_source.pdf hier] gibts die TeX-Sourcen, leider als PDF weil man wohl keine .TeXs hochladen darf. Originale gibts auf Anfrage bei kirchner at cl dot uni minus heidelberg dot de. Wird das Package "listings" verwendet, das gibts bei [http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/ http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/]

Tipp- und sonstige Fehler dürfen gerne verbessert und erneut hochgeladen werden, oder gebt mir per Email Bescheid, dann pflege ich die Korrektur ein :)

Ich Finde dein Aufschrieb sollte ins Wiki übetragen werden, das bietet auch alles, was
du mit Latex machen kannst. Die Bäume kannst du z.B. mit Latex zeichnen, einen pro Seite und diese dann in eine png Datei umwandeln. Wie sowas geht kann man z.B. in den Quellen von doxygen oder mediawiki selbst nachlesen. Oder man zoomt rein und macht einen Screenshot :-)

== Hashtabelle mit linearer Verkettung ==
Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem
Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

===Implementation in Python===
''HashNode'' ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert
und mit Hilfe von ''next'' eine verkettete Liste realisiert
class HashNode:
def __init__(self,key,data,next):
self.key = key
self.data = data
self.next = next # Verkettung!

Die eigentliche Hashtabelle wird in der Klasse ''HashTable'' implementiert:
class HashTable:
def __init__(self):
self.capacity = ... # Geeignete Werte siehe unten
self.size = 0
self.array = [None]*self.capacity

In Python ([http://docs.python.org/ref/sequence-types.html Python Docs zum Thema]) wird der Zugriffsoperator ''[ ]'' für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:
def __setitem__(self, key, value)

so dass im Programmtext dann folgende Syntax möglich ist: <tt>a[key] = value</tt> (schreibender Zugriff auf <tt>a[key]</tt>).
Analog wird der lesende Zugriff <tt>value = a[key]</tt> wie folgt umgesetzt:
def __getitem__(self, key, value)

Implementierung der <tt>__setitem__</tt>-Funktion in der <tt>HashTable</tt>-Klasse:
def __setitem__(self, key, value):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key:
# Element key ist schon in der Tabelle
#Überschreibe die Daten mit dem neuen Wert
node.data = value
return
# Kollision des Hashwerts, probiere nächsten Key aus
node = node.next
# Kein Element hatte den richtigen Schlüssel.
# ==>Es gibt diesen Schlüssel noch nicht
# Füge also ein neues Element in die Hashtabelle ein

self.array[index] = HashNode(key, value, self.array[index])
# Der alte Anfang der Liste wurde der Nachfolger des neu eingefügten
# ersten Elements

self.size += 1

Und die Implementierung der <tt>__getitem__</tt> Funktionen:
def __getitem__(self, key):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key: # Gefunden!
return node.data
node = node.next
raise KeyError(key)

==== Wahl der Kapazität ====
In der C++ Standardbibliothek (Klasse <tt> [http://www.sgi.com/tech/stl/hash_map.htmlstd::hash_map std::hash_map]</tt>) wird die Hashtabelle häufig mit Hilfe der linearen Verkettung
imlementiert. Dabei wird <tt>capacity</tt> immer als ''Primzahl'' gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:
53, 97, 193, 398, 769, ...
[http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc++-v3/src/hashtable.cc GCC hashtable.cc (Primzahlen)] [http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc++-v3/include/tr1_impl/hashtable_policy.h GCC Hash Implementation]

Das hat zur Folge, dass <tt>hash(key) % self.capacity</tt> ''alle'' Bits von h benutzt (Eigenschaft aus der Zahlentheorie). Die Kapizität wird vergrößert, wenn <tt>size == capacity</tt> erreicht wird. Analog zum dynamischen Array werden die Daten dann aus dem alten Array (<tt>self.array</tt>) in ein entsprechend vergrößertes neues Array kopiert.

== Hashtabelle mit offener Adressierung (offenes Hashing) ==
[http://de.wikipedia.org/wiki/Hashtabelle#Hashing_mit_offener_Adressierung Wikipedia (de)]
[http://en.wikipedia.org/wiki/Open_addressing Wikipedia (en)]

Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

=== Idee ===
Wenn <tt>array[index]</tt> durch Kollision bereits vergeben ist, probiere einen
anderen Index aus.

* Das Array enthält pro Element höchstens ein (key,value)-Paar
* Das Array muss stets mindestens ''einen'' freien Platz haben (sonst gäbe es beim Ausprobieren anderer Indizes eine Endlosschleife). Es gilt immer <tt>self.size < self.capacity</tt>. Dies war bei der vorigen Hash-Implementation mit linearer Verkettung nicht notwendig (aber im Sinne schneller zugriffszeiten trotzdem wünschenswert).

=== Vorgehen bei Kollisionen ===

==== Sequentielles Sondieren====
Probiere den nächsten Index: <tt>index = (index+1) % capacity</tt>

* Vorteil: einfach
* Nachteil: Clusterbildung

Clusterbildung heißt, dass sich größere zusammenhängende Bereiche bilden die belegt sind, unterbrochen von Bereichen die komplett frei sind. Beim Versuche des Einfügens eines Elements an einen Platz, der schon belegt ist, muss jetzt das ganze Cluster sequentiell durchlaufen werden, bis ein freier Platz gefunden wird. Damit entspricht die Komplexität der Suche der mittleren Länge der belegten Bereiche, was sich entsprechend in einer langsamen Suche widerspiegelt.

==== Doppeltes Hashing ====
[http://de.wikipedia.org/wiki/Doppel-Hashing Wikipedia (de)] [http://en.wikipedia.org/wiki/Double_hashing Wikipedia (en)]

Bestimme einen neuen Index (bei Kollisionen) durch eine ''2. Hashfunktion''.

Das doppelte Hashing wird typischerweise in der Praxis angewendet und liegt auch der Python Implementierung des Datentyps ''Dictionary'' (Syntax <tt>{'a':1, 'b':2, 'c':3}</tt> zugrunde.

Eine effiziente Implementierung dieses Datentyps ist für die Performance der Skriptsprache Python extrem wichtig, da z.B. beim Aufruf einer Funktion der auszuführunde Code in einem Dictionary unter dem Schlüssel ''Funktionsname'' nachgeschlagen wird oder die Werte lokaler Variablen innerhalb einer Funktion ebenfalls in einem Dictionary zu finden sind.

Für die Implementierung in Python werden wieder die obigen Klassen <tt>HashNode</tt> (das Attribut <tt>next</tt> kann allerdings jetzt entfernt werden) und <tt>HashTable</tt> benötigt, es folgen die angepassten Implementationen von <tt>__setitem__</tt> und <tt>__getitem__</tt>:

def __setitem__(self, key, value):
h = hash(key)
index = h % self.capacity
while True:
if self.array[index] is None or self.array[index].key is None:
# das Feld ist frei (1. Abfrage)
# oder das Feld ist als frei markiert (2. Abfrage)
self.array[index] = HashNode(key, value)
self.size +=1
return
if self.array[index].key == key:
# Es gibt diesen Schlüssel schon,
# überschreibe die Daten
self.array[index].data = value
return
# Letzter Fall: Kollision => neuer Index durch 2. Hashfunktion
index = (5*index+1+h) % self.capacity
h = h >> 5

Die vorgestellte Implementierung orientiert sich an Pythons interner Dictionary Implementierung, der zugehörige Quelltext (mit ausführlichem Kommentar) findet sich unter [http://svn.python.org/view/*checkout*/python/trunk/Objects/dictobject.c dictobject.c Python Implementation (SVN)]

===== Komplexität des offenen Hashings =====

* Annahme: uniformes Hashing, das heißt alle Indizes haben gleiche Wahrscheinlichkeit
* Füllstand <math>\alpha = \frac{\text{size}}{\text{capacity}}</math>

* '''Erfolglose Suche''' (d.h. es wird entweder ein neues Element eingefügt oder ein <tt>KeyError</tt> geworfen): Untere Schranke für die Komplexität ist <math>\Omega\left(\frac{1}{1-\alpha}\right)</math> Schritte (= Anzahl der notwendigen index-Berechnungen).
* '''Erfolgreiche Suche''' <math>\Omega\left(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\right)</math> Schritte.

{| border="1" cellspacing="0" cellpadding="5" align="center"
! <math>\alpha</math>
! 0.5
! 0.9
|-
| erfolglos
| 2.0
| 10
|-
| erfolgreich
| 1.4
| 2.6
|}

===== Wahl der Kapazität =====
In Python wird <tt>capacity</tt> Aufgrund der obigen Beobachtung so gewählt, dass <math>\alpha \leq 2/3</math>. Falls <math>\alpha</math> größer werden sollte, verdopple die Kapazität und kopiere das alte array in das neue Array (analog zum dynamischen Array)

In Python werden die Kapazitätsgrößen als Zweierpotenzen gewählt, also 4,8,16,32,...,
so dass <tt>h % self.capacity</tt> nur die unteren Bits von <tt>h</tt> benutzt.

== Anwendung von Hashing ==

* Hashtabelle, assoziatives Aray
* Sortieren in linearer Zeit (Übungsaufgabe 6.2)
* Suchen von Strings in Texten: Rabin-Karp-Algorithmus
* ...

=== Rabin Karp Algorithmus ===
[http://de.wikipedia.org/wiki/Rabin-Karp-Algorithmus Wikipedia (de)] [http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm Wikipedia (en)]

In Textverarbeitungsanwendungen ist eine häufig benutzte Funktion die ''Search & Replace'' Funktionalität. Die Suche sollte in O(len(text)) möglich sein, aber ein naiver Algorithmus braucht O(len(text)*len(searchstring))

==== Naive Implementierung der Suche ====
def search(text, s):
M, N = len(text), len(s)
for k in range(M-N):
if s==text[k:k+N]: # O(N), da N Zeichen verglichen werden müssen
return k
return -1 #nicht gefunden

==== Idee des Rabin Karp Algorithmus ====
Statt Vergleichen <tt>s==text[k:k+N]</tt>, die O(N) benötigen da N Vergleiche der Buchstaben durchgeführt werden müssen, Vergleiche die Hashs von Suchstring und dem zu untersuchenden Textabschnitt: <tt>hash(s) == hash(text[k:k+N])</tt>. Dabei muss natürlich <tt>hash(s)</tt> nur einmal berechnet werden, wohingegen <tt>hash(text[k:k+N])</tt> immer wieder neu berechnet werden muss. Damit der Vergleich O(1) sein kann, ist es deswegen erforderlich, eine solche Hashfunktion zu haben, die nicht alle Zeichen (das wäre O(N) ) einlesen muss, sondern die vorhergehende Hashfunktion mit einbezieht.

Eine solche Hashfunktion heißt ''Running Hash'' und funktioniert analog zum ''Sliding Mean''.

Die Running Hash Funktion berechnet in O(1) den hash von <tt>text[k+1:k+1+N]</tt> ausgehend vom hash für <tt>text[k:k+N]</tt>.

Idee: Interpretiere den Text als Ziffern in einer base d Darstellung:

<math>h_k = \text{text}[k]\cdot d^{N-1} + \text{text}[k]\cdot d^{N-2} + \cdots + \text{text}[k+N-1]</math>

Für die Basis 10 (Dezimalsystem) ergibt sich also

<math>h_k = \text{text}[k]\cdot {10}^{N-1} + \text{text}[k]\cdot {10}^{N-2} + \cdots + \text{text}[k+N-1]</math>

Daraus folgt

<math>h_{k+1} = 10\cdot h_k - \text{text}[k]\cdot {10}^{N} + \text{text}[k+N]</math>

Die Komplexität dieses Updates ist O(1), falls man <math>{10}^{N}</math> vorberechnet hat.

In der Realität wählt man dann d=32 und benutzt noch an einigen Stellen modulo Operationen, um die Zahlen nicht zu groß werden zu lassen.

==== Implementation ====
def searchRabinKarp(text, s):
ht, hs, dN = 0, 0, 1
M, N = len(text), len(s)
d, q = 32, 33554393
#q ist eine große Primzahl, aber so,
#dass d*q < 2**32 (um Überlauf zu vermeiden)

#Initialisierung
for k in range(N):
ht = (ht*d + ord(text[k])) % q
#ord() gibt die ASCIInummer des übergebenen Zeichens zurück
ds = (hs*d + ord( s[k] )) % q
dN = (dN*a) % q
#Die Variablen sind jetzt wie folgt initialisiert:
#ht = hash(text[0:N])
#hs = hash(s)
#dN = (d**N) % q

#Hauptschleife
k = 0
while k < M-N:
if hs == ht and s==text[k:k+N]:
return k # serch string an Position k gefunden
if k+N < M:
ht = (d*ht - dN * ord(text[k]) + dN*q + ord(text[k+N]) ) % q
k +=1
return -1 # search string nicht gefunden

Hashing und assoziative Arrays

2008-06-10T22:30:33Z

Thorben: /* Wahl der Kapazität */

Mitschrift gibts [http://hci.iwr.uni-heidelberg.de/alda/images/AlDa.pdf hier] als PDF und [http://hci.iwr.uni-heidelberg.de/alda/images/Alda_source.pdf hier] gibts die TeX-Sourcen, leider als PDF weil man wohl keine .TeXs hochladen darf. Originale gibts auf Anfrage bei kirchner at cl dot uni minus heidelberg dot de. Wird das Package "listings" verwendet, das gibts bei [http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/ http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/]

Tipp- und sonstige Fehler dürfen gerne verbessert und erneut hochgeladen werden, oder gebt mir per Email Bescheid, dann pflege ich die Korrektur ein :)

Ich Finde dein Aufschrieb sollte ins Wiki übetragen werden, das bietet auch alles, was
du mit Latex machen kannst. Die Bäume kannst du z.B. mit Latex zeichnen, einen pro Seite und diese dann in eine png Datei umwandeln. Wie sowas geht kann man z.B. in den Quellen von doxygen oder mediawiki selbst nachlesen. Oder man zoomt rein und macht einen Screenshot :-)

== Hashtabelle mit linearer Verkettung ==
Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem
Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

===Implementation in Python===
''HashNode'' ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert
und mit Hilfe von ''next'' eine verkettete Liste realisiert
class HashNode:
def __init__(self,key,data,next):
self.key = key
self.data = data
self.next = next # Verkettung!

Die eigentliche Hashtabelle wird in der Klasse ''HashTable'' implementiert:
class HashTable:
def __init__(self):
self.capacity = ... # Geeignete Werte siehe unten
self.size = 0
self.array = [None]*self.capacity

In Python ([http://docs.python.org/ref/sequence-types.html Python Docs zum Thema]) wird der Zugriffsoperator ''[ ]'' für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:
def __setitem__(self, key, value)

so dass im Programmtext dann folgende Syntax möglich ist: <tt>a[key] = value</tt> (schreibender Zugriff auf <tt>a[key]</tt>).
Analog wird der lesende Zugriff <tt>value = a[key]</tt> wie folgt umgesetzt:
def __getitem__(self, key, value)

Implementierung der <tt>__setitem__</tt>-Funktion in der <tt>HashTable</tt>-Klasse:
def __setitem__(self, key, value):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key:
# Element key ist schon in der Tabelle
#Überschreibe die Daten mit dem neuen Wert
node.data = value
return
# Kollision des Hashwerts, probiere nächsten Key aus
node = node.next
# Kein Element hatte den richtigen Schlüssel.
# ==>Es gibt diesen Schlüssel noch nicht
# Füge also ein neues Element in die Hashtabelle ein

self.array[index] = HashNode(key, value, self.array[index])
# Der alte Anfang der Liste wurde der Nachfolger des neu eingefügten
# ersten Elements

self.size += 1

Und die Implementierung der <tt>__getitem__</tt> Funktionen:
def __getitem__(self, key):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key: # Gefunden!
return node.data
node = node.next
raise KeyError(key)

==== Wahl der Kapazität ====
In der C++ Standardbibliothek (Klasse <tt> [http://www.sgi.com/tech/stl/hash_map.htmlstd::hash_map std::hash_map]</tt>) wird die Hashtabelle häufig mit Hilfe der linearen Verkettung
imlementiert. Dabei wird <tt>capacity</tt> immer als ''Primzahl'' gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:
53, 97, 193, 398, 769, ...
[http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc++-v3/src/hashtable.cc GCC hashtable.cc (Primzahlen)] [http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc++-v3/include/tr1_impl/hashtable_policy.h GCC Hash Implementation]

Das hat zur Folge, dass <tt>hash(key) % self.capacity</tt> ''alle'' Bits von h benutzt (Eigenschaft aus der Zahlentheorie). Die Kapizität wird vergrößert, wenn <tt>size == capacity</tt> erreicht wird. Analog zum dynamischen Array werden die Daten dann aus dem alten Array (<tt>self.array</tt>) in ein entsprechend vergrößertes neues Array kopiert.

== Hashtabelle mit offener Adressierung (offenes Hashing) ==
[http://de.wikipedia.org/wiki/Hashtabelle#Hashing_mit_offener_Adressierung Wikipedia (de)]
[http://en.wikipedia.org/wiki/Open_addressing Wikipedia (en)]

Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

=== Idee ===
Wenn <tt>array[index]</tt> durch Kollision bereits vergeben ist, probiere einen
anderen Index aus.

* Das Array enthält pro Element höchstens ein (key,value)-Paar
* Das Array muss stets mindestens ''einen'' freien Platz haben (sonst gäbe es beim Ausprobieren anderer Indizes eine Endlosschleife). Es gilt immer <tt>self.size < self.capacity</tt>. Dies war bei der vorigen Hash-Implementation mit linearer Verkettung nicht notwendig (aber im Sinne schneller zugriffszeiten trotzdem wünschenswert).

=== Vorgehen bei Kollisionen ===

==== Sequentielles Sondieren====
Probiere den nächsten Index: <tt>index = (index+1) % capacity</tt>

* Vorteil: einfach
* Nachteil: Clusterbildung

Clusterbildung heißt, dass sich größere zusammenhängende Bereiche bilden die belegt sind, unterbrochen von Bereichen die komplett frei sind. Beim Versuche des Einfügens eines Elements an einen Platz, der schon belegt ist, muss jetzt das ganze Cluster sequentiell durchlaufen werden, bis ein freier Platz gefunden wird. Damit entspricht die Komplexität der Suche der mittleren Länge der belegten Bereiche, was sich entsprechend in einer langsamen Suche widerspiegelt.

==== Doppeltes Hashing ====
[http://de.wikipedia.org/wiki/Doppel-Hashing Wikipedia (de)] [http://en.wikipedia.org/wiki/Double_hashing Wikipedia (en)]

Bestimme einen neuen Index (bei Kollisionen) durch eine ''2. Hashfunktion''.

Das doppelte Hashing wird typischerweise in der Praxis angewendet und liegt auch der Python Implementierung des Datentyps ''Dictionary'' (Syntax <tt>{'a':1, 'b':2, 'c':3}</tt> zugrunde.

Eine effiziente Implementierung dieses Datentyps ist für die Performance der Skriptsprache Python extrem wichtig, da z.B. beim Aufruf einer Funktion der auszuführunde Code in einem Dictionary unter dem Schlüssel ''Funktionsname'' nachgeschlagen wird oder die Werte lokaler Variablen innerhalb einer Funktion ebenfalls in einem Dictionary zu finden sind.

Für die Implementierung in Python werden wieder die obigen Klassen <tt>HashNode</tt> (das Attribut <tt>next</tt> kann allerdings jetzt entfernt werden) und <tt>HashTable</tt> benötigt, es folgen die angepassten Implementationen von <tt>__setitem</tt> und <tt>__getitem__</tt>:

def __setitem__(self, key, value):
h = hash(key)
index = h % self.capacity
while True:
if self.array[index] is None or self.array[index].key is None:
# das Feld ist frei (1. Abfrage)
# oder das Feld ist als frei markiert (2. Abfrage)
self.array[index] = HashNode(key, value)
self.size +=1
return
if self.array[index].key == key:
# Es gibt diesen Schlüssel schon,
# überschreibe die Daten
self.array[index].data = value
return
# Letzter Fall: Kollision => neuer Index durch 2. Hashfunktion
index = (5*index+1+h) % self.capacity
h = h >> 5

Die vorgestellte Implementierung orientiert sich an Pythons interner Dictionary Implementierung, der zugehörige Quelltext (mit ausführlichem Kommentar) findet sich unter [http://svn.python.org/view/*checkout*/python/trunk/Objects/dictobject.c dictobject.c Python Implementation (SVN)]

===== Komplexität des offenen Hashings =====

* Annahme: uniformes Hashing, das heißt alle Indizes haben gleiche Wahrscheinlichkeit
* Füllstand <math>\alpha = \frac{\text{size}}{\text{capacity}}</math>

* '''Erfolglose Suche''' (d.h. es wird entweder ein neues Element eingefügt oder ein <tt>KeyError</tt> geworfen): Untere Schranke für die Komplexität ist <math>\Omega\left(\frac{1}{1-\alpha}\right)</math> Schritte (= Anzahl der notwendigen index-Berechnungen).
* '''Erfolgreiche Suche''' <math>\Omega\left(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\right)</math> Schritte.

{| border="1" cellspacing="0" cellpadding="5" align="center"
! <math>\alpha</math>
! 0.5
! 0.9
|-
| erfolglos
| 2.0
| 10
|-
| erfolgreich
| 1.4
| 2.6
|}

===== Wahl der Kapazität =====
In Python wird <tt>capacity</tt> Aufgrund der obigen Beobachtung so gewählt, dass <math>\alpha \leq 2/3</math>. Falls <math>\alpha</math> größer werden sollte, verdopple die Kapazität und kopiere das alte array in das neue Array (analog zum dynamischen Array)

In Python werden die Kapazitätsgrößen als Zweierpotenzen gewählt, also 4,8,16,32,...,
so dass <tt>h % self.capacity</tt> nur die unteren Bits von <tt>h</tt> benutzt.

== Anwendung von Hashing ==

* Hashtabelle, assoziatives Aray
* Sortieren in linearer Zeit (Übungsaufgabe 6.2)
* Suchen von Strings in Texten: Rabin-Karp-Algorithmus
* ...

=== Rabin Karp Algorithmus ===
[http://de.wikipedia.org/wiki/Rabin-Karp-Algorithmus Wikipedia (de)] [http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm Wikipedia (en)]

In Textverarbeitungsanwendungen ist eine häufig benutzte Funktion die ''Search & Replace'' Funktionalität. Die Suche sollte in O(len(text)) möglich sein, aber ein naiver Algorithmus braucht O(len(text)*len(searchstring))

==== Naive Implementierung der Suche ====
def search(text, s):
M, N = len(text), len(s)
for k in range(M-N):
if s==text[k:k+N]: # O(N), da N Zeichen verglichen werden müssen
return k
return -1 #nicht gefunden

==== Idee des Rabin Karp Algorithmus ====
Statt Vergleichen <tt>s==text[k:k+N]</tt>, die O(N) benötigen da N Vergleiche der Buchstaben durchgeführt werden müssen, Vergleiche die Hashs von Suchstring und dem zu untersuchenden Textabschnitt: <tt>hash(s) == hash(text[k:k+N])</tt>. Dabei muss natürlich <tt>hash(s)</tt> nur einmal berechnet werden, wohingegen <tt>hash(text[k:k+N])</tt> immer wieder neu berechnet werden muss. Damit der Vergleich O(1) sein kann, ist es deswegen erforderlich, eine solche Hashfunktion zu haben, die nicht alle Zeichen (das wäre O(N) ) einlesen muss, sondern die vorhergehende Hashfunktion mit einbezieht.

Eine solche Hashfunktion heißt ''Running Hash'' und funktioniert analog zum ''Sliding Mean''.

Die Running Hash Funktion berechnet in O(1) den hash von <tt>text[k+1:k+1+N]</tt> ausgehend vom hash für <tt>text[k:k+N]</tt>.

Idee: Interpretiere den Text als Ziffern in einer base d Darstellung:

<math>h_k = \text{text}[k]\cdot d^{N-1} + \text{text}[k]\cdot d^{N-2} + \cdots + \text{text}[k+N-1]</math>

Für die Basis 10 (Dezimalsystem) ergibt sich also

<math>h_k = \text{text}[k]\cdot {10}^{N-1} + \text{text}[k]\cdot {10}^{N-2} + \cdots + \text{text}[k+N-1]</math>

Daraus folgt

<math>h_{k+1} = 10\cdot h_k - \text{text}[k]\cdot {10}^{N} + \text{text}[k+N]</math>

Die Komplexität dieses Updates ist O(1), falls man <math>{10}^{N}</math> vorberechnet hat.

In der Realität wählt man dann d=32 und benutzt noch an einigen Stellen modulo Operationen, um die Zahlen nicht zu groß werden zu lassen.

==== Implementation ====
def searchRabinKarp(text, s):
ht, hs, dN = 0, 0, 1
M, N = len(text), len(s)
d, q = 32, 33554393
#q ist eine große Primzahl, aber so,
#dass d*q < 2**32 (um Überlauf zu vermeiden)

#Initialisierung
for k in range(N):
ht = (ht*d + ord(text[k])) % q
#ord() gibt die ASCIInummer des übergebenen Zeichens zurück
ds = (hs*d + ord( s[k] )) % q
dN = (dN*a) % q
#Die Variablen sind jetzt wie folgt initialisiert:
#ht = hash(text[0:N])
#hs = hash(s)
#dN = (d**N) % q

#Hauptschleife
k = 0
while k < M-N:
if hs == ht and s==text[k:k+N]:
return k # serch string an Position k gefunden
if k+N < M:
ht = (d*ht - dN * ord(text[k]) + dN*q + ord(text[k+N]) ) % q
k +=1
return -1 # search string nicht gefunden

Hashing und assoziative Arrays

2008-06-10T22:28:19Z

Thorben: /* Implementation in Python */

Mitschrift gibts [http://hci.iwr.uni-heidelberg.de/alda/images/AlDa.pdf hier] als PDF und [http://hci.iwr.uni-heidelberg.de/alda/images/Alda_source.pdf hier] gibts die TeX-Sourcen, leider als PDF weil man wohl keine .TeXs hochladen darf. Originale gibts auf Anfrage bei kirchner at cl dot uni minus heidelberg dot de. Wird das Package "listings" verwendet, das gibts bei [http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/ http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/]

Tipp- und sonstige Fehler dürfen gerne verbessert und erneut hochgeladen werden, oder gebt mir per Email Bescheid, dann pflege ich die Korrektur ein :)

Ich Finde dein Aufschrieb sollte ins Wiki übetragen werden, das bietet auch alles, was
du mit Latex machen kannst. Die Bäume kannst du z.B. mit Latex zeichnen, einen pro Seite und diese dann in eine png Datei umwandeln. Wie sowas geht kann man z.B. in den Quellen von doxygen oder mediawiki selbst nachlesen. Oder man zoomt rein und macht einen Screenshot :-)

== Hashtabelle mit linearer Verkettung ==
Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem
Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

===Implementation in Python===
''HashNode'' ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert
und mit Hilfe von ''next'' eine verkettete Liste realisiert
class HashNode:
def __init__(self,key,data,next):
self.key = key
self.data = data
self.next = next # Verkettung!

Die eigentliche Hashtabelle wird in der Klasse ''HashTable'' implementiert:
class HashTable:
def __init__(self):
self.capacity = ... # Geeignete Werte siehe unten
self.size = 0
self.array = [None]*self.capacity

In Python ([http://docs.python.org/ref/sequence-types.html Python Docs zum Thema]) wird der Zugriffsoperator ''[ ]'' für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:
def __setitem__(self, key, value)

so dass im Programmtext dann folgende Syntax möglich ist: <tt>a[key] = value</tt> (schreibender Zugriff auf <tt>a[key]</tt>).
Analog wird der lesende Zugriff <tt>value = a[key]</tt> wie folgt umgesetzt:
def __getitem__(self, key, value)

Implementierung der <tt>__setitem__</tt>-Funktion in der <tt>HashTable</tt>-Klasse:
def __setitem__(self, key, value):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key:
# Element key ist schon in der Tabelle
#Überschreibe die Daten mit dem neuen Wert
node.data = value
return
# Kollision des Hashwerts, probiere nächsten Key aus
node = node.next
# Kein Element hatte den richtigen Schlüssel.
# ==>Es gibt diesen Schlüssel noch nicht
# Füge also ein neues Element in die Hashtabelle ein

self.array[index] = HashNode(key, value, self.array[index])
# Der alte Anfang der Liste wurde der Nachfolger des neu eingefügten
# ersten Elements

self.size += 1

Und die Implementierung der <tt>__getitem__</tt> Funktionen:
def __getitem__(self, key):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key: # Gefunden!
return node.data
node = node.next
raise KeyError(key)

==== Wahl der Kapazität ====
In der C++ Standardbibliothek (Klasse <tt> [http://www.sgi.com/tech/stl/hash_map.htmlstd::hash_map std::hash_map]</tt>) wird die Hashtabelle häufig mit Hilfe der linearen Verkettung
imlementiert. Dabei wird <tt>capacity</tt> immer als ''Primzahl'' gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:
53, 97, 193, 398, 769, ...
[http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc++-v3/src/hashtable.cc Gcc hashtable.cc (Primzahlen)] [http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc++-v3/include/tr1_impl/hashtable_policy.h GCC Hash Implementation]

Das hat zur Folge, dass <tt>hash(key) % self.capacity</tt> ''alle'' Bits von h benutzt (Eigenschaft aus der Zahlentheorie). Die Kapizität wird vergrößert, wenn <tt>size == capacity</tt> erreicht wird. Analog zum dynamischen Array werden die Daten dann aus dem alten Array (<tt>self.array</tt>) in ein entsprechend vergrößertes neues Array kopiert.

== Hashtabelle mit offener Adressierung (offenes Hashing) ==
[http://de.wikipedia.org/wiki/Hashtabelle#Hashing_mit_offener_Adressierung Wikipedia (de)]
[http://en.wikipedia.org/wiki/Open_addressing Wikipedia (en)]

Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

=== Idee ===
Wenn <tt>array[index]</tt> durch Kollision bereits vergeben ist, probiere einen
anderen Index aus.

* Das Array enthält pro Element höchstens ein (key,value)-Paar
* Das Array muss stets mindestens ''einen'' freien Platz haben (sonst gäbe es beim Ausprobieren anderer Indizes eine Endlosschleife). Es gilt immer <tt>self.size < self.capacity</tt>. Dies war bei der vorigen Hash-Implementation mit linearer Verkettung nicht notwendig (aber im Sinne schneller zugriffszeiten trotzdem wünschenswert).

=== Vorgehen bei Kollisionen ===

==== Sequentielles Sondieren====
Probiere den nächsten Index: <tt>index = (index+1) % capacity</tt>

* Vorteil: einfach
* Nachteil: Clusterbildung

Clusterbildung heißt, dass sich größere zusammenhängende Bereiche bilden die belegt sind, unterbrochen von Bereichen die komplett frei sind. Beim Versuche des Einfügens eines Elements an einen Platz, der schon belegt ist, muss jetzt das ganze Cluster sequentiell durchlaufen werden, bis ein freier Platz gefunden wird. Damit entspricht die Komplexität der Suche der mittleren Länge der belegten Bereiche, was sich entsprechend in einer langsamen Suche widerspiegelt.

==== Doppeltes Hashing ====
[http://de.wikipedia.org/wiki/Doppel-Hashing Wikipedia (de)] [http://en.wikipedia.org/wiki/Double_hashing Wikipedia (en)]

Bestimme einen neuen Index (bei Kollisionen) durch eine ''2. Hashfunktion''.

Das doppelte Hashing wird typischerweise in der Praxis angewendet und liegt auch der Python Implementierung des Datentyps ''Dictionary'' (Syntax <tt>{'a':1, 'b':2, 'c':3}</tt> zugrunde.

Eine effiziente Implementierung dieses Datentyps ist für die Performance der Skriptsprache Python extrem wichtig, da z.B. beim Aufruf einer Funktion der auszuführunde Code in einem Dictionary unter dem Schlüssel ''Funktionsname'' nachgeschlagen wird oder die Werte lokaler Variablen innerhalb einer Funktion ebenfalls in einem Dictionary zu finden sind.

Für die Implementierung in Python werden wieder die obigen Klassen <tt>HashNode</tt> (das Attribut <tt>next</tt> kann allerdings jetzt entfernt werden) und <tt>HashTable</tt> benötigt, es folgen die angepassten Implementationen von <tt>__setitem</tt> und <tt>__getitem__</tt>:

def __setitem__(self, key, value):
h = hash(key)
index = h % self.capacity
while True:
if self.array[index] is None or self.array[index].key is None:
# das Feld ist frei (1. Abfrage)
# oder das Feld ist als frei markiert (2. Abfrage)
self.array[index] = HashNode(key, value)
self.size +=1
return
if self.array[index].key == key:
# Es gibt diesen Schlüssel schon,
# überschreibe die Daten
self.array[index].data = value
return
# Letzter Fall: Kollision => neuer Index durch 2. Hashfunktion
index = (5*index+1+h) % self.capacity
h = h >> 5

Die vorgestellte Implementierung orientiert sich an Pythons interner Dictionary Implementierung, der zugehörige Quelltext (mit ausführlichem Kommentar) findet sich unter [http://svn.python.org/view/*checkout*/python/trunk/Objects/dictobject.c dictobject.c Python Implementation (SVN)]

===== Komplexität des offenen Hashings =====

* Annahme: uniformes Hashing, das heißt alle Indizes haben gleiche Wahrscheinlichkeit
* Füllstand <math>\alpha = \frac{\text{size}}{\text{capacity}}</math>

* '''Erfolglose Suche''' (d.h. es wird entweder ein neues Element eingefügt oder ein <tt>KeyError</tt> geworfen): Untere Schranke für die Komplexität ist <math>\Omega\left(\frac{1}{1-\alpha}\right)</math> Schritte (= Anzahl der notwendigen index-Berechnungen).
* '''Erfolgreiche Suche''' <math>\Omega\left(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\right)</math> Schritte.

{| border="1" cellspacing="0" cellpadding="5" align="center"
! <math>\alpha</math>
! 0.5
! 0.9
|-
| erfolglos
| 2.0
| 10
|-
| erfolgreich
| 1.4
| 2.6
|}

===== Wahl der Kapazität =====
In Python wird <tt>capacity</tt> Aufgrund der obigen Beobachtung so gewählt, dass <math>\alpha \leq 2/3</math>. Falls <math>\alpha</math> größer werden sollte, verdopple die Kapazität und kopiere das alte array in das neue Array (analog zum dynamischen Array)

In Python werden die Kapazitätsgrößen als Zweierpotenzen gewählt, also 4,8,16,32,...,
so dass <tt>h % self.capacity</tt> nur die unteren Bits von <tt>h</tt> benutzt.

== Anwendung von Hashing ==

* Hashtabelle, assoziatives Aray
* Sortieren in linearer Zeit (Übungsaufgabe 6.2)
* Suchen von Strings in Texten: Rabin-Karp-Algorithmus
* ...

=== Rabin Karp Algorithmus ===
[http://de.wikipedia.org/wiki/Rabin-Karp-Algorithmus Wikipedia (de)] [http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm Wikipedia (en)]

In Textverarbeitungsanwendungen ist eine häufig benutzte Funktion die ''Search & Replace'' Funktionalität. Die Suche sollte in O(len(text)) möglich sein, aber ein naiver Algorithmus braucht O(len(text)*len(searchstring))

==== Naive Implementierung der Suche ====
def search(text, s):
M, N = len(text), len(s)
for k in range(M-N):
if s==text[k:k+N]: # O(N), da N Zeichen verglichen werden müssen
return k
return -1 #nicht gefunden

==== Idee des Rabin Karp Algorithmus ====
Statt Vergleichen <tt>s==text[k:k+N]</tt>, die O(N) benötigen da N Vergleiche der Buchstaben durchgeführt werden müssen, Vergleiche die Hashs von Suchstring und dem zu untersuchenden Textabschnitt: <tt>hash(s) == hash(text[k:k+N])</tt>. Dabei muss natürlich <tt>hash(s)</tt> nur einmal berechnet werden, wohingegen <tt>hash(text[k:k+N])</tt> immer wieder neu berechnet werden muss. Damit der Vergleich O(1) sein kann, ist es deswegen erforderlich, eine solche Hashfunktion zu haben, die nicht alle Zeichen (das wäre O(N) ) einlesen muss, sondern die vorhergehende Hashfunktion mit einbezieht.

Eine solche Hashfunktion heißt ''Running Hash'' und funktioniert analog zum ''Sliding Mean''.

Die Running Hash Funktion berechnet in O(1) den hash von <tt>text[k+1:k+1+N]</tt> ausgehend vom hash für <tt>text[k:k+N]</tt>.

Idee: Interpretiere den Text als Ziffern in einer base d Darstellung:

<math>h_k = \text{text}[k]\cdot d^{N-1} + \text{text}[k]\cdot d^{N-2} + \cdots + \text{text}[k+N-1]</math>

Für die Basis 10 (Dezimalsystem) ergibt sich also

<math>h_k = \text{text}[k]\cdot {10}^{N-1} + \text{text}[k]\cdot {10}^{N-2} + \cdots + \text{text}[k+N-1]</math>

Daraus folgt

<math>h_{k+1} = 10\cdot h_k - \text{text}[k]\cdot {10}^{N} + \text{text}[k+N]</math>

Die Komplexität dieses Updates ist O(1), falls man <math>{10}^{N}</math> vorberechnet hat.

In der Realität wählt man dann d=32 und benutzt noch an einigen Stellen modulo Operationen, um die Zahlen nicht zu groß werden zu lassen.

==== Implementation ====
def searchRabinKarp(text, s):
ht, hs, dN = 0, 0, 1
M, N = len(text), len(s)
d, q = 32, 33554393
#q ist eine große Primzahl, aber so,
#dass d*q < 2**32 (um Überlauf zu vermeiden)

#Initialisierung
for k in range(N):
ht = (ht*d + ord(text[k])) % q
#ord() gibt die ASCIInummer des übergebenen Zeichens zurück
ds = (hs*d + ord( s[k] )) % q
dN = (dN*a) % q
#Die Variablen sind jetzt wie folgt initialisiert:
#ht = hash(text[0:N])
#hs = hash(s)
#dN = (d**N) % q

#Hauptschleife
k = 0
while k < M-N:
if hs == ht and s==text[k:k+N]:
return k # serch string an Position k gefunden
if k+N < M:
ht = (d*ht - dN * ord(text[k]) + dN*q + ord(text[k+N]) ) % q
k +=1
return -1 # search string nicht gefunden

Hashing und assoziative Arrays

2008-06-10T22:28:00Z

Thorben: /* Implementation in Python */

Mitschrift gibts [http://hci.iwr.uni-heidelberg.de/alda/images/AlDa.pdf hier] als PDF und [http://hci.iwr.uni-heidelberg.de/alda/images/Alda_source.pdf hier] gibts die TeX-Sourcen, leider als PDF weil man wohl keine .TeXs hochladen darf. Originale gibts auf Anfrage bei kirchner at cl dot uni minus heidelberg dot de. Wird das Package "listings" verwendet, das gibts bei [http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/ http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/]

Tipp- und sonstige Fehler dürfen gerne verbessert und erneut hochgeladen werden, oder gebt mir per Email Bescheid, dann pflege ich die Korrektur ein :)

Ich Finde dein Aufschrieb sollte ins Wiki übetragen werden, das bietet auch alles, was
du mit Latex machen kannst. Die Bäume kannst du z.B. mit Latex zeichnen, einen pro Seite und diese dann in eine png Datei umwandeln. Wie sowas geht kann man z.B. in den Quellen von doxygen oder mediawiki selbst nachlesen. Oder man zoomt rein und macht einen Screenshot :-)

== Hashtabelle mit linearer Verkettung ==
Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem
Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

===Implementation in Python===
''HashNode'' ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert
und mit Hilfe von ''next'' eine verkettete Liste realisiert
class HashNode:
def __init__(self,key,data,next):
self.key = key
self.data = data
self.next = next # Verkettung!

Die eigentliche Hashtabelle wird in der Klasse ''HashTable'' implementiert:
class HashTable:
def __init__(self):
self.capacity = ... # Geeignete Werte siehe unten
self.size = 0
self.array = [None]*self.capacity

In Python ([ http://docs.python.org/ref/sequence-types.html Python Docs zum Thema]) wird der Zugriffsoperator ''[ ]'' für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:
def __setitem__(self, key, value)

so dass im Programmtext dann folgende Syntax möglich ist: <tt>a[key] = value</tt> (schreibender Zugriff auf <tt>a[key]</tt>).
Analog wird der lesende Zugriff <tt>value = a[key]</tt> wie folgt umgesetzt:
def __getitem__(self, key, value)

Implementierung der <tt>__setitem__</tt>-Funktion in der <tt>HashTable</tt>-Klasse:
def __setitem__(self, key, value):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key:
# Element key ist schon in der Tabelle
#Überschreibe die Daten mit dem neuen Wert
node.data = value
return
# Kollision des Hashwerts, probiere nächsten Key aus
node = node.next
# Kein Element hatte den richtigen Schlüssel.
# ==>Es gibt diesen Schlüssel noch nicht
# Füge also ein neues Element in die Hashtabelle ein

self.array[index] = HashNode(key, value, self.array[index])
# Der alte Anfang der Liste wurde der Nachfolger des neu eingefügten
# ersten Elements

self.size += 1

Und die Implementierung der <tt>__getitem__</tt> Funktionen:
def __getitem__(self, key):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key: # Gefunden!
return node.data
node = node.next
raise KeyError(key)

==== Wahl der Kapazität ====
In der C++ Standardbibliothek (Klasse <tt> [http://www.sgi.com/tech/stl/hash_map.htmlstd::hash_map std::hash_map]</tt>) wird die Hashtabelle häufig mit Hilfe der linearen Verkettung
imlementiert. Dabei wird <tt>capacity</tt> immer als ''Primzahl'' gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:
53, 97, 193, 398, 769, ...
[http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc++-v3/src/hashtable.cc Gcc hashtable.cc (Primzahlen)] [http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc++-v3/include/tr1_impl/hashtable_policy.h GCC Hash Implementation]

Das hat zur Folge, dass <tt>hash(key) % self.capacity</tt> ''alle'' Bits von h benutzt (Eigenschaft aus der Zahlentheorie). Die Kapizität wird vergrößert, wenn <tt>size == capacity</tt> erreicht wird. Analog zum dynamischen Array werden die Daten dann aus dem alten Array (<tt>self.array</tt>) in ein entsprechend vergrößertes neues Array kopiert.

== Hashtabelle mit offener Adressierung (offenes Hashing) ==
[http://de.wikipedia.org/wiki/Hashtabelle#Hashing_mit_offener_Adressierung Wikipedia (de)]
[http://en.wikipedia.org/wiki/Open_addressing Wikipedia (en)]

Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

=== Idee ===
Wenn <tt>array[index]</tt> durch Kollision bereits vergeben ist, probiere einen
anderen Index aus.

* Das Array enthält pro Element höchstens ein (key,value)-Paar
* Das Array muss stets mindestens ''einen'' freien Platz haben (sonst gäbe es beim Ausprobieren anderer Indizes eine Endlosschleife). Es gilt immer <tt>self.size < self.capacity</tt>. Dies war bei der vorigen Hash-Implementation mit linearer Verkettung nicht notwendig (aber im Sinne schneller zugriffszeiten trotzdem wünschenswert).

=== Vorgehen bei Kollisionen ===

==== Sequentielles Sondieren====
Probiere den nächsten Index: <tt>index = (index+1) % capacity</tt>

* Vorteil: einfach
* Nachteil: Clusterbildung

Clusterbildung heißt, dass sich größere zusammenhängende Bereiche bilden die belegt sind, unterbrochen von Bereichen die komplett frei sind. Beim Versuche des Einfügens eines Elements an einen Platz, der schon belegt ist, muss jetzt das ganze Cluster sequentiell durchlaufen werden, bis ein freier Platz gefunden wird. Damit entspricht die Komplexität der Suche der mittleren Länge der belegten Bereiche, was sich entsprechend in einer langsamen Suche widerspiegelt.

==== Doppeltes Hashing ====
[http://de.wikipedia.org/wiki/Doppel-Hashing Wikipedia (de)] [http://en.wikipedia.org/wiki/Double_hashing Wikipedia (en)]

Bestimme einen neuen Index (bei Kollisionen) durch eine ''2. Hashfunktion''.

Das doppelte Hashing wird typischerweise in der Praxis angewendet und liegt auch der Python Implementierung des Datentyps ''Dictionary'' (Syntax <tt>{'a':1, 'b':2, 'c':3}</tt> zugrunde.

Eine effiziente Implementierung dieses Datentyps ist für die Performance der Skriptsprache Python extrem wichtig, da z.B. beim Aufruf einer Funktion der auszuführunde Code in einem Dictionary unter dem Schlüssel ''Funktionsname'' nachgeschlagen wird oder die Werte lokaler Variablen innerhalb einer Funktion ebenfalls in einem Dictionary zu finden sind.

Für die Implementierung in Python werden wieder die obigen Klassen <tt>HashNode</tt> (das Attribut <tt>next</tt> kann allerdings jetzt entfernt werden) und <tt>HashTable</tt> benötigt, es folgen die angepassten Implementationen von <tt>__setitem</tt> und <tt>__getitem__</tt>:

def __setitem__(self, key, value):
h = hash(key)
index = h % self.capacity
while True:
if self.array[index] is None or self.array[index].key is None:
# das Feld ist frei (1. Abfrage)
# oder das Feld ist als frei markiert (2. Abfrage)
self.array[index] = HashNode(key, value)
self.size +=1
return
if self.array[index].key == key:
# Es gibt diesen Schlüssel schon,
# überschreibe die Daten
self.array[index].data = value
return
# Letzter Fall: Kollision => neuer Index durch 2. Hashfunktion
index = (5*index+1+h) % self.capacity
h = h >> 5

Die vorgestellte Implementierung orientiert sich an Pythons interner Dictionary Implementierung, der zugehörige Quelltext (mit ausführlichem Kommentar) findet sich unter [http://svn.python.org/view/*checkout*/python/trunk/Objects/dictobject.c dictobject.c Python Implementation (SVN)]

===== Komplexität des offenen Hashings =====

* Annahme: uniformes Hashing, das heißt alle Indizes haben gleiche Wahrscheinlichkeit
* Füllstand <math>\alpha = \frac{\text{size}}{\text{capacity}}</math>

* '''Erfolglose Suche''' (d.h. es wird entweder ein neues Element eingefügt oder ein <tt>KeyError</tt> geworfen): Untere Schranke für die Komplexität ist <math>\Omega\left(\frac{1}{1-\alpha}\right)</math> Schritte (= Anzahl der notwendigen index-Berechnungen).
* '''Erfolgreiche Suche''' <math>\Omega\left(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\right)</math> Schritte.

{| border="1" cellspacing="0" cellpadding="5" align="center"
! <math>\alpha</math>
! 0.5
! 0.9
|-
| erfolglos
| 2.0
| 10
|-
| erfolgreich
| 1.4
| 2.6
|}

===== Wahl der Kapazität =====
In Python wird <tt>capacity</tt> Aufgrund der obigen Beobachtung so gewählt, dass <math>\alpha \leq 2/3</math>. Falls <math>\alpha</math> größer werden sollte, verdopple die Kapazität und kopiere das alte array in das neue Array (analog zum dynamischen Array)

In Python werden die Kapazitätsgrößen als Zweierpotenzen gewählt, also 4,8,16,32,...,
so dass <tt>h % self.capacity</tt> nur die unteren Bits von <tt>h</tt> benutzt.

== Anwendung von Hashing ==

* Hashtabelle, assoziatives Aray
* Sortieren in linearer Zeit (Übungsaufgabe 6.2)
* Suchen von Strings in Texten: Rabin-Karp-Algorithmus
* ...

=== Rabin Karp Algorithmus ===
[http://de.wikipedia.org/wiki/Rabin-Karp-Algorithmus Wikipedia (de)] [http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm Wikipedia (en)]

In Textverarbeitungsanwendungen ist eine häufig benutzte Funktion die ''Search & Replace'' Funktionalität. Die Suche sollte in O(len(text)) möglich sein, aber ein naiver Algorithmus braucht O(len(text)*len(searchstring))

==== Naive Implementierung der Suche ====
def search(text, s):
M, N = len(text), len(s)
for k in range(M-N):
if s==text[k:k+N]: # O(N), da N Zeichen verglichen werden müssen
return k
return -1 #nicht gefunden

==== Idee des Rabin Karp Algorithmus ====
Statt Vergleichen <tt>s==text[k:k+N]</tt>, die O(N) benötigen da N Vergleiche der Buchstaben durchgeführt werden müssen, Vergleiche die Hashs von Suchstring und dem zu untersuchenden Textabschnitt: <tt>hash(s) == hash(text[k:k+N])</tt>. Dabei muss natürlich <tt>hash(s)</tt> nur einmal berechnet werden, wohingegen <tt>hash(text[k:k+N])</tt> immer wieder neu berechnet werden muss. Damit der Vergleich O(1) sein kann, ist es deswegen erforderlich, eine solche Hashfunktion zu haben, die nicht alle Zeichen (das wäre O(N) ) einlesen muss, sondern die vorhergehende Hashfunktion mit einbezieht.

Eine solche Hashfunktion heißt ''Running Hash'' und funktioniert analog zum ''Sliding Mean''.

Die Running Hash Funktion berechnet in O(1) den hash von <tt>text[k+1:k+1+N]</tt> ausgehend vom hash für <tt>text[k:k+N]</tt>.

Idee: Interpretiere den Text als Ziffern in einer base d Darstellung:

<math>h_k = \text{text}[k]\cdot d^{N-1} + \text{text}[k]\cdot d^{N-2} + \cdots + \text{text}[k+N-1]</math>

Für die Basis 10 (Dezimalsystem) ergibt sich also

<math>h_k = \text{text}[k]\cdot {10}^{N-1} + \text{text}[k]\cdot {10}^{N-2} + \cdots + \text{text}[k+N-1]</math>

Daraus folgt

<math>h_{k+1} = 10\cdot h_k - \text{text}[k]\cdot {10}^{N} + \text{text}[k+N]</math>

Die Komplexität dieses Updates ist O(1), falls man <math>{10}^{N}</math> vorberechnet hat.

In der Realität wählt man dann d=32 und benutzt noch an einigen Stellen modulo Operationen, um die Zahlen nicht zu groß werden zu lassen.

==== Implementation ====
def searchRabinKarp(text, s):
ht, hs, dN = 0, 0, 1
M, N = len(text), len(s)
d, q = 32, 33554393
#q ist eine große Primzahl, aber so,
#dass d*q < 2**32 (um Überlauf zu vermeiden)

#Initialisierung
for k in range(N):
ht = (ht*d + ord(text[k])) % q
#ord() gibt die ASCIInummer des übergebenen Zeichens zurück
ds = (hs*d + ord( s[k] )) % q
dN = (dN*a) % q
#Die Variablen sind jetzt wie folgt initialisiert:
#ht = hash(text[0:N])
#hs = hash(s)
#dN = (d**N) % q

#Hauptschleife
k = 0
while k < M-N:
if hs == ht and s==text[k:k+N]:
return k # serch string an Position k gefunden
if k+N < M:
ht = (d*ht - dN * ord(text[k]) + dN*q + ord(text[k+N]) ) % q
k +=1
return -1 # search string nicht gefunden

Hashing und assoziative Arrays

2008-06-10T22:24:46Z

Thorben: /* Wahl der Kapazität */

Mitschrift gibts [http://hci.iwr.uni-heidelberg.de/alda/images/AlDa.pdf hier] als PDF und [http://hci.iwr.uni-heidelberg.de/alda/images/Alda_source.pdf hier] gibts die TeX-Sourcen, leider als PDF weil man wohl keine .TeXs hochladen darf. Originale gibts auf Anfrage bei kirchner at cl dot uni minus heidelberg dot de. Wird das Package "listings" verwendet, das gibts bei [http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/ http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/]

Tipp- und sonstige Fehler dürfen gerne verbessert und erneut hochgeladen werden, oder gebt mir per Email Bescheid, dann pflege ich die Korrektur ein :)

Ich Finde dein Aufschrieb sollte ins Wiki übetragen werden, das bietet auch alles, was
du mit Latex machen kannst. Die Bäume kannst du z.B. mit Latex zeichnen, einen pro Seite und diese dann in eine png Datei umwandeln. Wie sowas geht kann man z.B. in den Quellen von doxygen oder mediawiki selbst nachlesen. Oder man zoomt rein und macht einen Screenshot :-)

== Hashtabelle mit linearer Verkettung ==
Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem
Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

===Implementation in Python===
''HashNode'' ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert
und mit Hilfe von ''next'' eine verkettete Liste realisiert
class HashNode:
def __init__(self,key,data,next):
self.key = key
self.data = data
self.next = next # Verkettung!

Die eigentliche Hashtabelle wird in der Klasse ''HashTable'' implementiert:
class HashTable:
def __init__(self):
self.capacity = ... # Geeignete Werte siehe unten
self.size = 0
self.array = [None]*self.capacity

In Python wird der Zugriffsoperator ''[ ]'' für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:
def __setitem__(self, key, value)

so dass im Programmtext dann folgende Syntax möglich ist: <tt>a[key] = value</tt> (schreibender Zugriff auf <tt>a[key]</tt>).
Analog wird der lesende Zugriff <tt>value = a[key]</tt> wie folgt umgesetzt:
def __getitem__(self, key, value)

Implementierung der <tt>__setitem__</tt>-Funktion in der <tt>HashTable</tt>-Klasse:
def __setitem__(self, key, value):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key:
# Element key ist schon in der Tabelle
#Überschreibe die Daten mit dem neuen Wert
node.data = value
return
# Kollision des Hashwerts, probiere nächsten Key aus
node = node.next
# Kein Element hatte den richtigen Schlüssel.
# ==>Es gibt diesen Schlüssel noch nicht
# Füge also ein neues Element in die Hashtabelle ein

self.array[index] = HashNode(key, value, self.array[index])
# Der alte Anfang der Liste wurde der Nachfolger des neu eingefügten
# ersten Elements

self.size += 1

Und die Implementierung der <tt>__getitem__</tt> Funktionen:
def __getitem__(self, key):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key: # Gefunden!
return node.data
node = node.next
raise KeyError(key)

==== Wahl der Kapazität ====
In der C++ Standardbibliothek (Klasse <tt> [http://www.sgi.com/tech/stl/hash_map.htmlstd::hash_map std::hash_map]</tt>) wird die Hashtabelle häufig mit Hilfe der linearen Verkettung
imlementiert. Dabei wird <tt>capacity</tt> immer als ''Primzahl'' gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:
53, 97, 193, 398, 769, ...
[http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc++-v3/src/hashtable.cc Gcc hashtable.cc (Primzahlen)] [http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc++-v3/include/tr1_impl/hashtable_policy.h GCC Hash Implementation]

Das hat zur Folge, dass <tt>hash(key) % self.capacity</tt> ''alle'' Bits von h benutzt (Eigenschaft aus der Zahlentheorie). Die Kapizität wird vergrößert, wenn <tt>size == capacity</tt> erreicht wird. Analog zum dynamischen Array werden die Daten dann aus dem alten Array (<tt>self.array</tt>) in ein entsprechend vergrößertes neues Array kopiert.

== Hashtabelle mit offener Adressierung (offenes Hashing) ==
[http://de.wikipedia.org/wiki/Hashtabelle#Hashing_mit_offener_Adressierung Wikipedia (de)]
[http://en.wikipedia.org/wiki/Open_addressing Wikipedia (en)]

Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

=== Idee ===
Wenn <tt>array[index]</tt> durch Kollision bereits vergeben ist, probiere einen
anderen Index aus.

* Das Array enthält pro Element höchstens ein (key,value)-Paar
* Das Array muss stets mindestens ''einen'' freien Platz haben (sonst gäbe es beim Ausprobieren anderer Indizes eine Endlosschleife). Es gilt immer <tt>self.size < self.capacity</tt>. Dies war bei der vorigen Hash-Implementation mit linearer Verkettung nicht notwendig (aber im Sinne schneller zugriffszeiten trotzdem wünschenswert).

=== Vorgehen bei Kollisionen ===

==== Sequentielles Sondieren====
Probiere den nächsten Index: <tt>index = (index+1) % capacity</tt>

* Vorteil: einfach
* Nachteil: Clusterbildung

Clusterbildung heißt, dass sich größere zusammenhängende Bereiche bilden die belegt sind, unterbrochen von Bereichen die komplett frei sind. Beim Versuche des Einfügens eines Elements an einen Platz, der schon belegt ist, muss jetzt das ganze Cluster sequentiell durchlaufen werden, bis ein freier Platz gefunden wird. Damit entspricht die Komplexität der Suche der mittleren Länge der belegten Bereiche, was sich entsprechend in einer langsamen Suche widerspiegelt.

==== Doppeltes Hashing ====
[http://de.wikipedia.org/wiki/Doppel-Hashing Wikipedia (de)] [http://en.wikipedia.org/wiki/Double_hashing Wikipedia (en)]

Bestimme einen neuen Index (bei Kollisionen) durch eine ''2. Hashfunktion''.

Das doppelte Hashing wird typischerweise in der Praxis angewendet und liegt auch der Python Implementierung des Datentyps ''Dictionary'' (Syntax <tt>{'a':1, 'b':2, 'c':3}</tt> zugrunde.

Eine effiziente Implementierung dieses Datentyps ist für die Performance der Skriptsprache Python extrem wichtig, da z.B. beim Aufruf einer Funktion der auszuführunde Code in einem Dictionary unter dem Schlüssel ''Funktionsname'' nachgeschlagen wird oder die Werte lokaler Variablen innerhalb einer Funktion ebenfalls in einem Dictionary zu finden sind.

Für die Implementierung in Python werden wieder die obigen Klassen <tt>HashNode</tt> (das Attribut <tt>next</tt> kann allerdings jetzt entfernt werden) und <tt>HashTable</tt> benötigt, es folgen die angepassten Implementationen von <tt>__setitem</tt> und <tt>__getitem__</tt>:

def __setitem__(self, key, value):
h = hash(key)
index = h % self.capacity
while True:
if self.array[index] is None or self.array[index].key is None:
# das Feld ist frei (1. Abfrage)
# oder das Feld ist als frei markiert (2. Abfrage)
self.array[index] = HashNode(key, value)
self.size +=1
return
if self.array[index].key == key:
# Es gibt diesen Schlüssel schon,
# überschreibe die Daten
self.array[index].data = value
return
# Letzter Fall: Kollision => neuer Index durch 2. Hashfunktion
index = (5*index+1+h) % self.capacity
h = h >> 5

Die vorgestellte Implementierung orientiert sich an Pythons interner Dictionary Implementierung, der zugehörige Quelltext (mit ausführlichem Kommentar) findet sich unter [http://svn.python.org/view/*checkout*/python/trunk/Objects/dictobject.c dictobject.c Python Implementation (SVN)]

===== Komplexität des offenen Hashings =====

* Annahme: uniformes Hashing, das heißt alle Indizes haben gleiche Wahrscheinlichkeit
* Füllstand <math>\alpha = \frac{\text{size}}{\text{capacity}}</math>

* '''Erfolglose Suche''' (d.h. es wird entweder ein neues Element eingefügt oder ein <tt>KeyError</tt> geworfen): Untere Schranke für die Komplexität ist <math>\Omega\left(\frac{1}{1-\alpha}\right)</math> Schritte (= Anzahl der notwendigen index-Berechnungen).
* '''Erfolgreiche Suche''' <math>\Omega\left(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\right)</math> Schritte.

{| border="1" cellspacing="0" cellpadding="5" align="center"
! <math>\alpha</math>
! 0.5
! 0.9
|-
| erfolglos
| 2.0
| 10
|-
| erfolgreich
| 1.4
| 2.6
|}

===== Wahl der Kapazität =====
In Python wird <tt>capacity</tt> Aufgrund der obigen Beobachtung so gewählt, dass <math>\alpha \leq 2/3</math>. Falls <math>\alpha</math> größer werden sollte, verdopple die Kapazität und kopiere das alte array in das neue Array (analog zum dynamischen Array)

In Python werden die Kapazitätsgrößen als Zweierpotenzen gewählt, also 4,8,16,32,...,
so dass <tt>h % self.capacity</tt> nur die unteren Bits von <tt>h</tt> benutzt.

== Anwendung von Hashing ==

* Hashtabelle, assoziatives Aray
* Sortieren in linearer Zeit (Übungsaufgabe 6.2)
* Suchen von Strings in Texten: Rabin-Karp-Algorithmus
* ...

=== Rabin Karp Algorithmus ===
[http://de.wikipedia.org/wiki/Rabin-Karp-Algorithmus Wikipedia (de)] [http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm Wikipedia (en)]

In Textverarbeitungsanwendungen ist eine häufig benutzte Funktion die ''Search & Replace'' Funktionalität. Die Suche sollte in O(len(text)) möglich sein, aber ein naiver Algorithmus braucht O(len(text)*len(searchstring))

==== Naive Implementierung der Suche ====
def search(text, s):
M, N = len(text), len(s)
for k in range(M-N):
if s==text[k:k+N]: # O(N), da N Zeichen verglichen werden müssen
return k
return -1 #nicht gefunden

==== Idee des Rabin Karp Algorithmus ====
Statt Vergleichen <tt>s==text[k:k+N]</tt>, die O(N) benötigen da N Vergleiche der Buchstaben durchgeführt werden müssen, Vergleiche die Hashs von Suchstring und dem zu untersuchenden Textabschnitt: <tt>hash(s) == hash(text[k:k+N])</tt>. Dabei muss natürlich <tt>hash(s)</tt> nur einmal berechnet werden, wohingegen <tt>hash(text[k:k+N])</tt> immer wieder neu berechnet werden muss. Damit der Vergleich O(1) sein kann, ist es deswegen erforderlich, eine solche Hashfunktion zu haben, die nicht alle Zeichen (das wäre O(N) ) einlesen muss, sondern die vorhergehende Hashfunktion mit einbezieht.

Eine solche Hashfunktion heißt ''Running Hash'' und funktioniert analog zum ''Sliding Mean''.

Die Running Hash Funktion berechnet in O(1) den hash von <tt>text[k+1:k+1+N]</tt> ausgehend vom hash für <tt>text[k:k+N]</tt>.

Idee: Interpretiere den Text als Ziffern in einer base d Darstellung:

<math>h_k = \text{text}[k]\cdot d^{N-1} + \text{text}[k]\cdot d^{N-2} + \cdots + \text{text}[k+N-1]</math>

Für die Basis 10 (Dezimalsystem) ergibt sich also

<math>h_k = \text{text}[k]\cdot {10}^{N-1} + \text{text}[k]\cdot {10}^{N-2} + \cdots + \text{text}[k+N-1]</math>

Daraus folgt

<math>h_{k+1} = 10\cdot h_k - \text{text}[k]\cdot {10}^{N} + \text{text}[k+N]</math>

Die Komplexität dieses Updates ist O(1), falls man <math>{10}^{N}</math> vorberechnet hat.

In der Realität wählt man dann d=32 und benutzt noch an einigen Stellen modulo Operationen, um die Zahlen nicht zu groß werden zu lassen.

==== Implementation ====
def searchRabinKarp(text, s):
ht, hs, dN = 0, 0, 1
M, N = len(text), len(s)
d, q = 32, 33554393
#q ist eine große Primzahl, aber so,
#dass d*q < 2**32 (um Überlauf zu vermeiden)

#Initialisierung
for k in range(N):
ht = (ht*d + ord(text[k])) % q
#ord() gibt die ASCIInummer des übergebenen Zeichens zurück
ds = (hs*d + ord( s[k] )) % q
dN = (dN*a) % q
#Die Variablen sind jetzt wie folgt initialisiert:
#ht = hash(text[0:N])
#hs = hash(s)
#dN = (d**N) % q

#Hauptschleife
k = 0
while k < M-N:
if hs == ht and s==text[k:k+N]:
return k # serch string an Position k gefunden
if k+N < M:
ht = (d*ht - dN * ord(text[k]) + dN*q + ord(text[k+N]) ) % q
k +=1
return -1 # search string nicht gefunden

Hashing und assoziative Arrays

2008-06-10T21:47:13Z

Thorben: /* Implementation */

Mitschrift gibts [http://hci.iwr.uni-heidelberg.de/alda/images/AlDa.pdf hier] als PDF und [http://hci.iwr.uni-heidelberg.de/alda/images/Alda_source.pdf hier] gibts die TeX-Sourcen, leider als PDF weil man wohl keine .TeXs hochladen darf. Originale gibts auf Anfrage bei kirchner at cl dot uni minus heidelberg dot de. Wird das Package "listings" verwendet, das gibts bei [http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/ http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/]

Tipp- und sonstige Fehler dürfen gerne verbessert und erneut hochgeladen werden, oder gebt mir per Email Bescheid, dann pflege ich die Korrektur ein :)

Ich Finde dein Aufschrieb sollte ins Wiki übetragen werden, das bietet auch alles, was
du mit Latex machen kannst. Die Bäume kannst du z.B. mit Latex zeichnen, einen pro Seite und diese dann in eine png Datei umwandeln. Wie sowas geht kann man z.B. in den Quellen von doxygen oder mediawiki selbst nachlesen. Oder man zoomt rein und macht einen Screenshot :-)

== Hashtabelle mit linearer Verkettung ==
Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem
Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

===Implementation in Python===
''HashNode'' ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert
und mit Hilfe von ''next'' eine verkettete Liste realisiert
class HashNode:
def __init__(self,key,data,next):
self.key = key
self.data = data
self.next = next # Verkettung!

Die eigentliche Hashtabelle wird in der Klasse ''HashTable'' implementiert:
class HashTable:
def __init__(self):
self.capacity = ... # Geeignete Werte siehe unten
self.size = 0
self.array = [None]*self.capacity

In Python wird der Zugriffsoperator ''[ ]'' für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:
def __setitem__(self, key, value)

so dass im Programmtext dann folgende Syntax möglich ist: <tt>a[key] = value</tt> (schreibender Zugriff auf <tt>a[key]</tt>).
Analog wird der lesende Zugriff <tt>value = a[key]</tt> wie folgt umgesetzt:
def __getitem__(self, key, value)

Implementierung der <tt>__setitem__</tt>-Funktion in der <tt>HashTable</tt>-Klasse:
def __setitem__(self, key, value):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key:
# Element key ist schon in der Tabelle
#Überschreibe die Daten mit dem neuen Wert
node.data = value
return
# Kollision des Hashwerts, probiere nächsten Key aus
node = node.next
# Kein Element hatte den richtigen Schlüssel.
# ==>Es gibt diesen Schlüssel noch nicht
# Füge also ein neues Element in die Hashtabelle ein

self.array[index] = HashNode(key, value, self.array[index])
# Der alte Anfang der Liste wurde der Nachfolger des neu eingefügten
# ersten Elements

self.size += 1

Und die Implementierung der <tt>__getitem__</tt> Funktionen:
def __getitem__(self, key):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key: # Gefunden!
return node.data
node = node.next
raise KeyError(key)

==== Wahl der Kapazität ====
In der C++ Standardbibliothek (Klasse <tt>std::hash_map</tt>) wird die Hashtabelle häufig mit Hilfe der linearen Verkettung
imlementiert. Dabei wird <tt>capacity</tt> immer als ''Primzahl'' gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:
53, 97, 193, 398, 769, ...

Das hat zur Folge, dass <tt>hash(key) % self.capacity</tt> ''alle'' Bits von h benutzt (Eigenschaft aus der Zahlentheorie). Die Kapizität wird vergrößert, wenn <tt>size == capacity</tt> erreicht wird. Analog zum dynamischen Array werden die Daten dann aus dem alten Array (<tt>self.array</tt>) in ein entsprechend vergrößertes neues Array kopiert.

== Hashtabelle mit offener Adressierung (offenes Hashing) ==
[http://de.wikipedia.org/wiki/Hashtabelle#Hashing_mit_offener_Adressierung Wikipedia (de)]
[http://en.wikipedia.org/wiki/Open_addressing Wikipedia (en)]

Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

=== Idee ===
Wenn <tt>array[index]</tt> durch Kollision bereits vergeben ist, probiere einen
anderen Index aus.

* Das Array enthält pro Element höchstens ein (key,value)-Paar
* Das Array muss stets mindestens ''einen'' freien Platz haben (sonst gäbe es beim Ausprobieren anderer Indizes eine Endlosschleife). Es gilt immer <tt>self.size < self.capacity</tt>. Dies war bei der vorigen Hash-Implementation mit linearer Verkettung nicht notwendig (aber im Sinne schneller zugriffszeiten trotzdem wünschenswert).

=== Vorgehen bei Kollisionen ===

==== Sequentielles Sondieren====
Probiere den nächsten Index: <tt>index = (index+1) % capacity</tt>

* Vorteil: einfach
* Nachteil: Clusterbildung

Clusterbildung heißt, dass sich größere zusammenhängende Bereiche bilden die belegt sind, unterbrochen von Bereichen die komplett frei sind. Beim Versuche des Einfügens eines Elements an einen Platz, der schon belegt ist, muss jetzt das ganze Cluster sequentiell durchlaufen werden, bis ein freier Platz gefunden wird. Damit entspricht die Komplexität der Suche der mittleren Länge der belegten Bereiche, was sich entsprechend in einer langsamen Suche widerspiegelt.

==== Doppeltes Hashing ====
[http://de.wikipedia.org/wiki/Doppel-Hashing Wikipedia (de)] [http://en.wikipedia.org/wiki/Double_hashing Wikipedia (en)]

Bestimme einen neuen Index (bei Kollisionen) durch eine ''2. Hashfunktion''.

Das doppelte Hashing wird typischerweise in der Praxis angewendet und liegt auch der Python Implementierung des Datentyps ''Dictionary'' (Syntax <tt>{'a':1, 'b':2, 'c':3}</tt> zugrunde.

Eine effiziente Implementierung dieses Datentyps ist für die Performance der Skriptsprache Python extrem wichtig, da z.B. beim Aufruf einer Funktion der auszuführunde Code in einem Dictionary unter dem Schlüssel ''Funktionsname'' nachgeschlagen wird oder die Werte lokaler Variablen innerhalb einer Funktion ebenfalls in einem Dictionary zu finden sind.

Für die Implementierung in Python werden wieder die obigen Klassen <tt>HashNode</tt> (das Attribut <tt>next</tt> kann allerdings jetzt entfernt werden) und <tt>HashTable</tt> benötigt, es folgen die angepassten Implementationen von <tt>__setitem</tt> und <tt>__getitem__</tt>:

def __setitem__(self, key, value):
h = hash(key)
index = h % self.capacity
while True:
if self.array[index] is None or self.array[index].key is None:
# das Feld ist frei (1. Abfrage)
# oder das Feld ist als frei markiert (2. Abfrage)
self.array[index] = HashNode(key, value)
self.size +=1
return
if self.array[index].key == key:
# Es gibt diesen Schlüssel schon,
# überschreibe die Daten
self.array[index].data = value
return
# Letzter Fall: Kollision => neuer Index durch 2. Hashfunktion
index = (5*index+1+h) % self.capacity
h = h >> 5

Die vorgestellte Implementierung orientiert sich an Pythons interner Dictionary Implementierung, der zugehörige Quelltext (mit ausführlichem Kommentar) findet sich unter [http://svn.python.org/view/*checkout*/python/trunk/Objects/dictobject.c dictobject.c Python Implementation (SVN)]

===== Komplexität des offenen Hashings =====

* Annahme: uniformes Hashing, das heißt alle Indizes haben gleiche Wahrscheinlichkeit
* Füllstand <math>\alpha = \frac{\text{size}}{\text{capacity}}</math>

* '''Erfolglose Suche''' (d.h. es wird entweder ein neues Element eingefügt oder ein <tt>KeyError</tt> geworfen): Untere Schranke für die Komplexität ist <math>\Omega\left(\frac{1}{1-\alpha}\right)</math> Schritte (= Anzahl der notwendigen index-Berechnungen).
* '''Erfolgreiche Suche''' <math>\Omega\left(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\right)</math> Schritte.

{| border="1" cellspacing="0" cellpadding="5" align="center"
! <math>\alpha</math>
! 0.5
! 0.9
|-
| erfolglos
| 2.0
| 10
|-
| erfolgreich
| 1.4
| 2.6
|}

===== Wahl der Kapazität =====
In Python wird <tt>capacity</tt> Aufgrund der obigen Beobachtung so gewählt, dass <math>\alpha \leq 2/3</math>. Falls <math>\alpha</math> größer werden sollte, verdopple die Kapazität und kopiere das alte array in das neue Array (analog zum dynamischen Array)

In Python werden die Kapazitätsgrößen als Zweierpotenzen gewählt, also 4,8,16,32,...,
so dass <tt>h % self.capacity</tt> nur die unteren Bits von <tt>h</tt> benutzt.

== Anwendung von Hashing ==

* Hashtabelle, assoziatives Aray
* Sortieren in linearer Zeit (Übungsaufgabe 6.2)
* Suchen von Strings in Texten: Rabin-Karp-Algorithmus
* ...

=== Rabin Karp Algorithmus ===
[http://de.wikipedia.org/wiki/Rabin-Karp-Algorithmus Wikipedia (de)] [http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm Wikipedia (en)]

In Textverarbeitungsanwendungen ist eine häufig benutzte Funktion die ''Search & Replace'' Funktionalität. Die Suche sollte in O(len(text)) möglich sein, aber ein naiver Algorithmus braucht O(len(text)*len(searchstring))

==== Naive Implementierung der Suche ====
def search(text, s):
M, N = len(text), len(s)
for k in range(M-N):
if s==text[k:k+N]: # O(N), da N Zeichen verglichen werden müssen
return k
return -1 #nicht gefunden

==== Idee des Rabin Karp Algorithmus ====
Statt Vergleichen <tt>s==text[k:k+N]</tt>, die O(N) benötigen da N Vergleiche der Buchstaben durchgeführt werden müssen, Vergleiche die Hashs von Suchstring und dem zu untersuchenden Textabschnitt: <tt>hash(s) == hash(text[k:k+N])</tt>. Dabei muss natürlich <tt>hash(s)</tt> nur einmal berechnet werden, wohingegen <tt>hash(text[k:k+N])</tt> immer wieder neu berechnet werden muss. Damit der Vergleich O(1) sein kann, ist es deswegen erforderlich, eine solche Hashfunktion zu haben, die nicht alle Zeichen (das wäre O(N) ) einlesen muss, sondern die vorhergehende Hashfunktion mit einbezieht.

Eine solche Hashfunktion heißt ''Running Hash'' und funktioniert analog zum ''Sliding Mean''.

Die Running Hash Funktion berechnet in O(1) den hash von <tt>text[k+1:k+1+N]</tt> ausgehend vom hash für <tt>text[k:k+N]</tt>.

Idee: Interpretiere den Text als Ziffern in einer base d Darstellung:

<math>h_k = \text{text}[k]\cdot d^{N-1} + \text{text}[k]\cdot d^{N-2} + \cdots + \text{text}[k+N-1]</math>

Für die Basis 10 (Dezimalsystem) ergibt sich also

<math>h_k = \text{text}[k]\cdot {10}^{N-1} + \text{text}[k]\cdot {10}^{N-2} + \cdots + \text{text}[k+N-1]</math>

Daraus folgt

<math>h_{k+1} = 10\cdot h_k - \text{text}[k]\cdot {10}^{N} + \text{text}[k+N]</math>

Die Komplexität dieses Updates ist O(1), falls man <math>{10}^{N}</math> vorberechnet hat.

In der Realität wählt man dann d=32 und benutzt noch an einigen Stellen modulo Operationen, um die Zahlen nicht zu groß werden zu lassen.

==== Implementation ====
def searchRabinKarp(text, s):
ht, hs, dN = 0, 0, 1
M, N = len(text), len(s)
d, q = 32, 33554393
#q ist eine große Primzahl, aber so,
#dass d*q < 2**32 (um Überlauf zu vermeiden)

#Initialisierung
for k in range(N):
ht = (ht*d + ord(text[k])) % q
#ord() gibt die ASCIInummer des übergebenen Zeichens zurück
ds = (hs*d + ord( s[k] )) % q
dN = (dN*a) % q
#Die Variablen sind jetzt wie folgt initialisiert:
#ht = hash(text[0:N])
#hs = hash(s)
#dN = (d**N) % q

#Hauptschleife
k = 0
while k < M-N:
if hs == ht and s==text[k:k+N]:
return k # serch string an Position k gefunden
if k+N < M:
ht = (d*ht - dN * ord(text[k]) + dN*q + ord(text[k+N]) ) % q
k +=1
return -1 # search string nicht gefunden

Hashing und assoziative Arrays

2008-06-10T21:45:14Z

Thorben: /* Rabin Karp Algorithmus */

Mitschrift gibts [http://hci.iwr.uni-heidelberg.de/alda/images/AlDa.pdf hier] als PDF und [http://hci.iwr.uni-heidelberg.de/alda/images/Alda_source.pdf hier] gibts die TeX-Sourcen, leider als PDF weil man wohl keine .TeXs hochladen darf. Originale gibts auf Anfrage bei kirchner at cl dot uni minus heidelberg dot de. Wird das Package "listings" verwendet, das gibts bei [http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/ http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/]

Tipp- und sonstige Fehler dürfen gerne verbessert und erneut hochgeladen werden, oder gebt mir per Email Bescheid, dann pflege ich die Korrektur ein :)

Ich Finde dein Aufschrieb sollte ins Wiki übetragen werden, das bietet auch alles, was
du mit Latex machen kannst. Die Bäume kannst du z.B. mit Latex zeichnen, einen pro Seite und diese dann in eine png Datei umwandeln. Wie sowas geht kann man z.B. in den Quellen von doxygen oder mediawiki selbst nachlesen. Oder man zoomt rein und macht einen Screenshot :-)

== Hashtabelle mit linearer Verkettung ==
Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem
Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

===Implementation in Python===
''HashNode'' ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert
und mit Hilfe von ''next'' eine verkettete Liste realisiert
class HashNode:
def __init__(self,key,data,next):
self.key = key
self.data = data
self.next = next # Verkettung!

Die eigentliche Hashtabelle wird in der Klasse ''HashTable'' implementiert:
class HashTable:
def __init__(self):
self.capacity = ... # Geeignete Werte siehe unten
self.size = 0
self.array = [None]*self.capacity

In Python wird der Zugriffsoperator ''[ ]'' für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:
def __setitem__(self, key, value)

so dass im Programmtext dann folgende Syntax möglich ist: <tt>a[key] = value</tt> (schreibender Zugriff auf <tt>a[key]</tt>).
Analog wird der lesende Zugriff <tt>value = a[key]</tt> wie folgt umgesetzt:
def __getitem__(self, key, value)

Implementierung der <tt>__setitem__</tt>-Funktion in der <tt>HashTable</tt>-Klasse:
def __setitem__(self, key, value):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key:
# Element key ist schon in der Tabelle
#Überschreibe die Daten mit dem neuen Wert
node.data = value
return
# Kollision des Hashwerts, probiere nächsten Key aus
node = node.next
# Kein Element hatte den richtigen Schlüssel.
# ==>Es gibt diesen Schlüssel noch nicht
# Füge also ein neues Element in die Hashtabelle ein

self.array[index] = HashNode(key, value, self.array[index])
# Der alte Anfang der Liste wurde der Nachfolger des neu eingefügten
# ersten Elements

self.size += 1

Und die Implementierung der <tt>__getitem__</tt> Funktionen:
def __getitem__(self, key):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key: # Gefunden!
return node.data
node = node.next
raise KeyError(key)

==== Wahl der Kapazität ====
In der C++ Standardbibliothek (Klasse <tt>std::hash_map</tt>) wird die Hashtabelle häufig mit Hilfe der linearen Verkettung
imlementiert. Dabei wird <tt>capacity</tt> immer als ''Primzahl'' gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:
53, 97, 193, 398, 769, ...

Das hat zur Folge, dass <tt>hash(key) % self.capacity</tt> ''alle'' Bits von h benutzt (Eigenschaft aus der Zahlentheorie). Die Kapizität wird vergrößert, wenn <tt>size == capacity</tt> erreicht wird. Analog zum dynamischen Array werden die Daten dann aus dem alten Array (<tt>self.array</tt>) in ein entsprechend vergrößertes neues Array kopiert.

== Hashtabelle mit offener Adressierung (offenes Hashing) ==
[http://de.wikipedia.org/wiki/Hashtabelle#Hashing_mit_offener_Adressierung Wikipedia (de)]
[http://en.wikipedia.org/wiki/Open_addressing Wikipedia (en)]

Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

=== Idee ===
Wenn <tt>array[index]</tt> durch Kollision bereits vergeben ist, probiere einen
anderen Index aus.

* Das Array enthält pro Element höchstens ein (key,value)-Paar
* Das Array muss stets mindestens ''einen'' freien Platz haben (sonst gäbe es beim Ausprobieren anderer Indizes eine Endlosschleife). Es gilt immer <tt>self.size < self.capacity</tt>. Dies war bei der vorigen Hash-Implementation mit linearer Verkettung nicht notwendig (aber im Sinne schneller zugriffszeiten trotzdem wünschenswert).

=== Vorgehen bei Kollisionen ===

==== Sequentielles Sondieren====
Probiere den nächsten Index: <tt>index = (index+1) % capacity</tt>

* Vorteil: einfach
* Nachteil: Clusterbildung

Clusterbildung heißt, dass sich größere zusammenhängende Bereiche bilden die belegt sind, unterbrochen von Bereichen die komplett frei sind. Beim Versuche des Einfügens eines Elements an einen Platz, der schon belegt ist, muss jetzt das ganze Cluster sequentiell durchlaufen werden, bis ein freier Platz gefunden wird. Damit entspricht die Komplexität der Suche der mittleren Länge der belegten Bereiche, was sich entsprechend in einer langsamen Suche widerspiegelt.

==== Doppeltes Hashing ====
[http://de.wikipedia.org/wiki/Doppel-Hashing Wikipedia (de)] [http://en.wikipedia.org/wiki/Double_hashing Wikipedia (en)]

Bestimme einen neuen Index (bei Kollisionen) durch eine ''2. Hashfunktion''.

Das doppelte Hashing wird typischerweise in der Praxis angewendet und liegt auch der Python Implementierung des Datentyps ''Dictionary'' (Syntax <tt>{'a':1, 'b':2, 'c':3}</tt> zugrunde.

Eine effiziente Implementierung dieses Datentyps ist für die Performance der Skriptsprache Python extrem wichtig, da z.B. beim Aufruf einer Funktion der auszuführunde Code in einem Dictionary unter dem Schlüssel ''Funktionsname'' nachgeschlagen wird oder die Werte lokaler Variablen innerhalb einer Funktion ebenfalls in einem Dictionary zu finden sind.

Für die Implementierung in Python werden wieder die obigen Klassen <tt>HashNode</tt> (das Attribut <tt>next</tt> kann allerdings jetzt entfernt werden) und <tt>HashTable</tt> benötigt, es folgen die angepassten Implementationen von <tt>__setitem</tt> und <tt>__getitem__</tt>:

def __setitem__(self, key, value):
h = hash(key)
index = h % self.capacity
while True:
if self.array[index] is None or self.array[index].key is None:
# das Feld ist frei (1. Abfrage)
# oder das Feld ist als frei markiert (2. Abfrage)
self.array[index] = HashNode(key, value)
self.size +=1
return
if self.array[index].key == key:
# Es gibt diesen Schlüssel schon,
# überschreibe die Daten
self.array[index].data = value
return
# Letzter Fall: Kollision => neuer Index durch 2. Hashfunktion
index = (5*index+1+h) % self.capacity
h = h >> 5

Die vorgestellte Implementierung orientiert sich an Pythons interner Dictionary Implementierung, der zugehörige Quelltext (mit ausführlichem Kommentar) findet sich unter [http://svn.python.org/view/*checkout*/python/trunk/Objects/dictobject.c dictobject.c Python Implementation (SVN)]

===== Komplexität des offenen Hashings =====

* Annahme: uniformes Hashing, das heißt alle Indizes haben gleiche Wahrscheinlichkeit
* Füllstand <math>\alpha = \frac{\text{size}}{\text{capacity}}</math>

* '''Erfolglose Suche''' (d.h. es wird entweder ein neues Element eingefügt oder ein <tt>KeyError</tt> geworfen): Untere Schranke für die Komplexität ist <math>\Omega\left(\frac{1}{1-\alpha}\right)</math> Schritte (= Anzahl der notwendigen index-Berechnungen).
* '''Erfolgreiche Suche''' <math>\Omega\left(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\right)</math> Schritte.

{| border="1" cellspacing="0" cellpadding="5" align="center"
! <math>\alpha</math>
! 0.5
! 0.9
|-
| erfolglos
| 2.0
| 10
|-
| erfolgreich
| 1.4
| 2.6
|}

===== Wahl der Kapazität =====
In Python wird <tt>capacity</tt> Aufgrund der obigen Beobachtung so gewählt, dass <math>\alpha \leq 2/3</math>. Falls <math>\alpha</math> größer werden sollte, verdopple die Kapazität und kopiere das alte array in das neue Array (analog zum dynamischen Array)

In Python werden die Kapazitätsgrößen als Zweierpotenzen gewählt, also 4,8,16,32,...,
so dass <tt>h % self.capacity</tt> nur die unteren Bits von <tt>h</tt> benutzt.

== Anwendung von Hashing ==

* Hashtabelle, assoziatives Aray
* Sortieren in linearer Zeit (Übungsaufgabe 6.2)
* Suchen von Strings in Texten: Rabin-Karp-Algorithmus
* ...

=== Rabin Karp Algorithmus ===
[http://de.wikipedia.org/wiki/Rabin-Karp-Algorithmus Wikipedia (de)] [http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm Wikipedia (en)]

In Textverarbeitungsanwendungen ist eine häufig benutzte Funktion die ''Search & Replace'' Funktionalität. Die Suche sollte in O(len(text)) möglich sein, aber ein naiver Algorithmus braucht O(len(text)*len(searchstring))

==== Naive Implementierung der Suche ====
def search(text, s):
M, N = len(text), len(s)
for k in range(M-N):
if s==text[k:k+N]: # O(N), da N Zeichen verglichen werden müssen
return k
return -1 #nicht gefunden

==== Idee des Rabin Karp Algorithmus ====
Statt Vergleichen <tt>s==text[k:k+N]</tt>, die O(N) benötigen da N Vergleiche der Buchstaben durchgeführt werden müssen, Vergleiche die Hashs von Suchstring und dem zu untersuchenden Textabschnitt: <tt>hash(s) == hash(text[k:k+N])</tt>. Dabei muss natürlich <tt>hash(s)</tt> nur einmal berechnet werden, wohingegen <tt>hash(text[k:k+N])</tt> immer wieder neu berechnet werden muss. Damit der Vergleich O(1) sein kann, ist es deswegen erforderlich, eine solche Hashfunktion zu haben, die nicht alle Zeichen (das wäre O(N) ) einlesen muss, sondern die vorhergehende Hashfunktion mit einbezieht.

Eine solche Hashfunktion heißt ''Running Hash'' und funktioniert analog zum ''Sliding Mean''.

Die Running Hash Funktion berechnet in O(1) den hash von <tt>text[k+1:k+1+N]</tt> ausgehend vom hash für <tt>text[k:k+N]</tt>.

Idee: Interpretiere den Text als Ziffern in einer base d Darstellung:

<math>h_k = \text{text}[k]\cdot d^{N-1} + \text{text}[k]\cdot d^{N-2} + \cdots + \text{text}[k+N-1]</math>

Für die Basis 10 (Dezimalsystem) ergibt sich also

<math>h_k = \text{text}[k]\cdot {10}^{N-1} + \text{text}[k]\cdot {10}^{N-2} + \cdots + \text{text}[k+N-1]</math>

Daraus folgt

<math>h_{k+1} = 10\cdot h_k - \text{text}[k]\cdot {10}^{N} + \text{text}[k+N]</math>

Die Komplexität dieses Updates ist O(1), falls man <math>{10}^{N}</math> vorberechnet hat.

In der Realität wählt man dann d=32 und benutzt noch an einigen Stellen modulo Operationen, um die Zahlen nicht zu groß werden zu lassen.

==== Implementation ====
def searchRabinKarp(text, s):
ht, hs, dN = 0, 0, 1
M, N = len(text), len(s)
d, q = 32, 33554393 # q ist eine große Primzahl, aber so, dass d*q < 2**32 (um Überlauf zu vermeiden)

#Initialisierung
for k in range(N):
ht = (ht*d + ord(text[k])) % q
#ord() gibt die ASCIInummer des übergebenen Zeichens zurück
ds = (hs*d + ord( s[k] )) % q
dN = (dN*a) % q
#Die Variablen sind jetzt wie folgt initialisiert:
#ht = hash(text[0:N])
#hs = hash(s)
#dN = (d**N) % q

#Hauptschleife
k = 0
while k < M-N:
if hs == ht and s==text[k:k+N]:
return k # serch string an Position k gefunden
if k+N < M:
ht = (d*ht - dN * ord(text[k]) + dN*q + ord(text[k+N]) ) % q
k +=1
return -1 # search string nicht gefunden

Hashing und assoziative Arrays

2008-06-10T21:42:31Z

Thorben: /* Doppeltes Hashing */

Mitschrift gibts [http://hci.iwr.uni-heidelberg.de/alda/images/AlDa.pdf hier] als PDF und [http://hci.iwr.uni-heidelberg.de/alda/images/Alda_source.pdf hier] gibts die TeX-Sourcen, leider als PDF weil man wohl keine .TeXs hochladen darf. Originale gibts auf Anfrage bei kirchner at cl dot uni minus heidelberg dot de. Wird das Package "listings" verwendet, das gibts bei [http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/ http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/]

Tipp- und sonstige Fehler dürfen gerne verbessert und erneut hochgeladen werden, oder gebt mir per Email Bescheid, dann pflege ich die Korrektur ein :)

Ich Finde dein Aufschrieb sollte ins Wiki übetragen werden, das bietet auch alles, was
du mit Latex machen kannst. Die Bäume kannst du z.B. mit Latex zeichnen, einen pro Seite und diese dann in eine png Datei umwandeln. Wie sowas geht kann man z.B. in den Quellen von doxygen oder mediawiki selbst nachlesen. Oder man zoomt rein und macht einen Screenshot :-)

== Hashtabelle mit linearer Verkettung ==
Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem
Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

===Implementation in Python===
''HashNode'' ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert
und mit Hilfe von ''next'' eine verkettete Liste realisiert
class HashNode:
def __init__(self,key,data,next):
self.key = key
self.data = data
self.next = next # Verkettung!

Die eigentliche Hashtabelle wird in der Klasse ''HashTable'' implementiert:
class HashTable:
def __init__(self):
self.capacity = ... # Geeignete Werte siehe unten
self.size = 0
self.array = [None]*self.capacity

In Python wird der Zugriffsoperator ''[ ]'' für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:
def __setitem__(self, key, value)

so dass im Programmtext dann folgende Syntax möglich ist: <tt>a[key] = value</tt> (schreibender Zugriff auf <tt>a[key]</tt>).
Analog wird der lesende Zugriff <tt>value = a[key]</tt> wie folgt umgesetzt:
def __getitem__(self, key, value)

Implementierung der <tt>__setitem__</tt>-Funktion in der <tt>HashTable</tt>-Klasse:
def __setitem__(self, key, value):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key:
# Element key ist schon in der Tabelle
#Überschreibe die Daten mit dem neuen Wert
node.data = value
return
# Kollision des Hashwerts, probiere nächsten Key aus
node = node.next
# Kein Element hatte den richtigen Schlüssel.
# ==>Es gibt diesen Schlüssel noch nicht
# Füge also ein neues Element in die Hashtabelle ein

self.array[index] = HashNode(key, value, self.array[index])
# Der alte Anfang der Liste wurde der Nachfolger des neu eingefügten
# ersten Elements

self.size += 1

Und die Implementierung der <tt>__getitem__</tt> Funktionen:
def __getitem__(self, key):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key: # Gefunden!
return node.data
node = node.next
raise KeyError(key)

==== Wahl der Kapazität ====
In der C++ Standardbibliothek (Klasse <tt>std::hash_map</tt>) wird die Hashtabelle häufig mit Hilfe der linearen Verkettung
imlementiert. Dabei wird <tt>capacity</tt> immer als ''Primzahl'' gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:
53, 97, 193, 398, 769, ...

Das hat zur Folge, dass <tt>hash(key) % self.capacity</tt> ''alle'' Bits von h benutzt (Eigenschaft aus der Zahlentheorie). Die Kapizität wird vergrößert, wenn <tt>size == capacity</tt> erreicht wird. Analog zum dynamischen Array werden die Daten dann aus dem alten Array (<tt>self.array</tt>) in ein entsprechend vergrößertes neues Array kopiert.

== Hashtabelle mit offener Adressierung (offenes Hashing) ==
[http://de.wikipedia.org/wiki/Hashtabelle#Hashing_mit_offener_Adressierung Wikipedia (de)]
[http://en.wikipedia.org/wiki/Open_addressing Wikipedia (en)]

Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

=== Idee ===
Wenn <tt>array[index]</tt> durch Kollision bereits vergeben ist, probiere einen
anderen Index aus.

* Das Array enthält pro Element höchstens ein (key,value)-Paar
* Das Array muss stets mindestens ''einen'' freien Platz haben (sonst gäbe es beim Ausprobieren anderer Indizes eine Endlosschleife). Es gilt immer <tt>self.size < self.capacity</tt>. Dies war bei der vorigen Hash-Implementation mit linearer Verkettung nicht notwendig (aber im Sinne schneller zugriffszeiten trotzdem wünschenswert).

=== Vorgehen bei Kollisionen ===

==== Sequentielles Sondieren====
Probiere den nächsten Index: <tt>index = (index+1) % capacity</tt>

* Vorteil: einfach
* Nachteil: Clusterbildung

Clusterbildung heißt, dass sich größere zusammenhängende Bereiche bilden die belegt sind, unterbrochen von Bereichen die komplett frei sind. Beim Versuche des Einfügens eines Elements an einen Platz, der schon belegt ist, muss jetzt das ganze Cluster sequentiell durchlaufen werden, bis ein freier Platz gefunden wird. Damit entspricht die Komplexität der Suche der mittleren Länge der belegten Bereiche, was sich entsprechend in einer langsamen Suche widerspiegelt.

==== Doppeltes Hashing ====
[http://de.wikipedia.org/wiki/Doppel-Hashing Wikipedia (de)] [http://en.wikipedia.org/wiki/Double_hashing Wikipedia (en)]

Bestimme einen neuen Index (bei Kollisionen) durch eine ''2. Hashfunktion''.

Das doppelte Hashing wird typischerweise in der Praxis angewendet und liegt auch der Python Implementierung des Datentyps ''Dictionary'' (Syntax <tt>{'a':1, 'b':2, 'c':3}</tt> zugrunde.

Eine effiziente Implementierung dieses Datentyps ist für die Performance der Skriptsprache Python extrem wichtig, da z.B. beim Aufruf einer Funktion der auszuführunde Code in einem Dictionary unter dem Schlüssel ''Funktionsname'' nachgeschlagen wird oder die Werte lokaler Variablen innerhalb einer Funktion ebenfalls in einem Dictionary zu finden sind.

Für die Implementierung in Python werden wieder die obigen Klassen <tt>HashNode</tt> (das Attribut <tt>next</tt> kann allerdings jetzt entfernt werden) und <tt>HashTable</tt> benötigt, es folgen die angepassten Implementationen von <tt>__setitem</tt> und <tt>__getitem__</tt>:

def __setitem__(self, key, value):
h = hash(key)
index = h % self.capacity
while True:
if self.array[index] is None or self.array[index].key is None:
# das Feld ist frei (1. Abfrage)
# oder das Feld ist als frei markiert (2. Abfrage)
self.array[index] = HashNode(key, value)
self.size +=1
return
if self.array[index].key == key:
# Es gibt diesen Schlüssel schon,
# überschreibe die Daten
self.array[index].data = value
return
# Letzter Fall: Kollision => neuer Index durch 2. Hashfunktion
index = (5*index+1+h) % self.capacity
h = h >> 5

Die vorgestellte Implementierung orientiert sich an Pythons interner Dictionary Implementierung, der zugehörige Quelltext (mit ausführlichem Kommentar) findet sich unter [http://svn.python.org/view/*checkout*/python/trunk/Objects/dictobject.c dictobject.c Python Implementation (SVN)]

===== Komplexität des offenen Hashings =====

* Annahme: uniformes Hashing, das heißt alle Indizes haben gleiche Wahrscheinlichkeit
* Füllstand <math>\alpha = \frac{\text{size}}{\text{capacity}}</math>

* '''Erfolglose Suche''' (d.h. es wird entweder ein neues Element eingefügt oder ein <tt>KeyError</tt> geworfen): Untere Schranke für die Komplexität ist <math>\Omega\left(\frac{1}{1-\alpha}\right)</math> Schritte (= Anzahl der notwendigen index-Berechnungen).
* '''Erfolgreiche Suche''' <math>\Omega\left(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\right)</math> Schritte.

{| border="1" cellspacing="0" cellpadding="5" align="center"
! <math>\alpha</math>
! 0.5
! 0.9
|-
| erfolglos
| 2.0
| 10
|-
| erfolgreich
| 1.4
| 2.6
|}

===== Wahl der Kapazität =====
In Python wird <tt>capacity</tt> Aufgrund der obigen Beobachtung so gewählt, dass <math>\alpha \leq 2/3</math>. Falls <math>\alpha</math> größer werden sollte, verdopple die Kapazität und kopiere das alte array in das neue Array (analog zum dynamischen Array)

In Python werden die Kapazitätsgrößen als Zweierpotenzen gewählt, also 4,8,16,32,...,
so dass <tt>h % self.capacity</tt> nur die unteren Bits von <tt>h</tt> benutzt.

== Anwendung von Hashing ==

* Hashtabelle, assoziatives Aray
* Sortieren in linearer Zeit (Übungsaufgabe 6.2)
* Suchen von Strings in Texten: Rabin-Karp-Algorithmus
* ...

=== Rabin Karp Algorithmus ===
In Textverarbeitungsanwendungen ist eine häufig benutzte Funktion die ''Search & Replace'' Funktionalität. Die Suche sollte in O(len(text)) möglich sein, aber ein naiver Algorithmus braucht O(len(text)*len(searchstring))

==== Naive Implementierung der Suche ====
def search(text, s):
M, N = len(text), len(s)
for k in range(M-N):
if s==text[k:k+N]: # O(N), da N Zeichen verglichen werden müssen
return k
return -1 #nicht gefunden

==== Idee des Rabin Karp Algorithmus ====
Statt Vergleichen <tt>s==text[k:k+N]</tt>, die O(N) benötigen da N Vergleiche der Buchstaben durchgeführt werden müssen, Vergleiche die Hashs von Suchstring und dem zu untersuchenden Textabschnitt: <tt>hash(s) == hash(text[k:k+N])</tt>. Dabei muss natürlich <tt>hash(s)</tt> nur einmal berechnet werden, wohingegen <tt>hash(text[k:k+N])</tt> immer wieder neu berechnet werden muss. Damit der Vergleich O(1) sein kann, ist es deswegen erforderlich, eine solche Hashfunktion zu haben, die nicht alle Zeichen (das wäre O(N) ) einlesen muss, sondern die vorhergehende Hashfunktion mit einbezieht.

Eine solche Hashfunktion heißt ''Running Hash'' und funktioniert analog zum ''Sliding Mean''.

Die Running Hash Funktion berechnet in O(1) den hash von <tt>text[k+1:k+1+N]</tt> ausgehend vom hash für <tt>text[k:k+N]</tt>.

Idee: Interpretiere den Text als Ziffern in einer base d Darstellung:

<math>h_k = \text{text}[k]\cdot d^{N-1} + \text{text}[k]\cdot d^{N-2} + \cdots + \text{text}[k+N-1]</math>

Für die Basis 10 (Dezimalsystem) ergibt sich also

<math>h_k = \text{text}[k]\cdot {10}^{N-1} + \text{text}[k]\cdot {10}^{N-2} + \cdots + \text{text}[k+N-1]</math>

Daraus folgt

<math>h_{k+1} = 10\cdot h_k - \text{text}[k]\cdot {10}^{N} + \text{text}[k+N]</math>

Die Komplexität dieses Updates ist O(1), falls man <math>{10}^{N}</math> vorberechnet hat.

In der Realität wählt man dann d=32 und benutzt noch an einigen Stellen modulo Operationen, um die Zahlen nicht zu groß werden zu lassen.

==== Implementation ====
def searchRabinKarp(text, s):
ht, hs, dN = 0, 0, 1
M, N = len(text), len(s)
d, q = 32, 33554393 # q ist eine große Primzahl, aber so, dass d*q < 2**32 (um Überlauf zu vermeiden)

#Initialisierung
for k in range(N):
ht = (ht*d + ord(text[k])) % q
#ord() gibt die ASCIInummer des übergebenen Zeichens zurück
ds = (hs*d + ord( s[k] )) % q
dN = (dN*a) % q
#Die Variablen sind jetzt wie folgt initialisiert:
#ht = hash(text[0:N])
#hs = hash(s)
#dN = (d**N) % q

#Hauptschleife
k = 0
while k < M-N:
if hs == ht and s==text[k:k+N]:
return k # serch string an Position k gefunden
if k+N < M:
ht = (d*ht - dN * ord(text[k]) + dN*q + ord(text[k+N]) ) % q
k +=1
return -1 # search string nicht gefunden

Hashing und assoziative Arrays

2008-06-10T21:40:38Z

Thorben: /* Hashtabelle mit offener Adressierung (offenes Hashing) */

Mitschrift gibts [http://hci.iwr.uni-heidelberg.de/alda/images/AlDa.pdf hier] als PDF und [http://hci.iwr.uni-heidelberg.de/alda/images/Alda_source.pdf hier] gibts die TeX-Sourcen, leider als PDF weil man wohl keine .TeXs hochladen darf. Originale gibts auf Anfrage bei kirchner at cl dot uni minus heidelberg dot de. Wird das Package "listings" verwendet, das gibts bei [http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/ http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/]

Tipp- und sonstige Fehler dürfen gerne verbessert und erneut hochgeladen werden, oder gebt mir per Email Bescheid, dann pflege ich die Korrektur ein :)

Ich Finde dein Aufschrieb sollte ins Wiki übetragen werden, das bietet auch alles, was
du mit Latex machen kannst. Die Bäume kannst du z.B. mit Latex zeichnen, einen pro Seite und diese dann in eine png Datei umwandeln. Wie sowas geht kann man z.B. in den Quellen von doxygen oder mediawiki selbst nachlesen. Oder man zoomt rein und macht einen Screenshot :-)

== Hashtabelle mit linearer Verkettung ==
Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem
Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

===Implementation in Python===
''HashNode'' ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert
und mit Hilfe von ''next'' eine verkettete Liste realisiert
class HashNode:
def __init__(self,key,data,next):
self.key = key
self.data = data
self.next = next # Verkettung!

Die eigentliche Hashtabelle wird in der Klasse ''HashTable'' implementiert:
class HashTable:
def __init__(self):
self.capacity = ... # Geeignete Werte siehe unten
self.size = 0
self.array = [None]*self.capacity

In Python wird der Zugriffsoperator ''[ ]'' für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:
def __setitem__(self, key, value)

so dass im Programmtext dann folgende Syntax möglich ist: <tt>a[key] = value</tt> (schreibender Zugriff auf <tt>a[key]</tt>).
Analog wird der lesende Zugriff <tt>value = a[key]</tt> wie folgt umgesetzt:
def __getitem__(self, key, value)

Implementierung der <tt>__setitem__</tt>-Funktion in der <tt>HashTable</tt>-Klasse:
def __setitem__(self, key, value):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key:
# Element key ist schon in der Tabelle
#Überschreibe die Daten mit dem neuen Wert
node.data = value
return
# Kollision des Hashwerts, probiere nächsten Key aus
node = node.next
# Kein Element hatte den richtigen Schlüssel.
# ==>Es gibt diesen Schlüssel noch nicht
# Füge also ein neues Element in die Hashtabelle ein

self.array[index] = HashNode(key, value, self.array[index])
# Der alte Anfang der Liste wurde der Nachfolger des neu eingefügten
# ersten Elements

self.size += 1

Und die Implementierung der <tt>__getitem__</tt> Funktionen:
def __getitem__(self, key):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key: # Gefunden!
return node.data
node = node.next
raise KeyError(key)

==== Wahl der Kapazität ====
In der C++ Standardbibliothek (Klasse <tt>std::hash_map</tt>) wird die Hashtabelle häufig mit Hilfe der linearen Verkettung
imlementiert. Dabei wird <tt>capacity</tt> immer als ''Primzahl'' gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:
53, 97, 193, 398, 769, ...

Das hat zur Folge, dass <tt>hash(key) % self.capacity</tt> ''alle'' Bits von h benutzt (Eigenschaft aus der Zahlentheorie). Die Kapizität wird vergrößert, wenn <tt>size == capacity</tt> erreicht wird. Analog zum dynamischen Array werden die Daten dann aus dem alten Array (<tt>self.array</tt>) in ein entsprechend vergrößertes neues Array kopiert.

== Hashtabelle mit offener Adressierung (offenes Hashing) ==
[http://de.wikipedia.org/wiki/Hashtabelle#Hashing_mit_offener_Adressierung Wikipedia (de)]
[http://en.wikipedia.org/wiki/Open_addressing Wikipedia (en)]

Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

=== Idee ===
Wenn <tt>array[index]</tt> durch Kollision bereits vergeben ist, probiere einen
anderen Index aus.

* Das Array enthält pro Element höchstens ein (key,value)-Paar
* Das Array muss stets mindestens ''einen'' freien Platz haben (sonst gäbe es beim Ausprobieren anderer Indizes eine Endlosschleife). Es gilt immer <tt>self.size < self.capacity</tt>. Dies war bei der vorigen Hash-Implementation mit linearer Verkettung nicht notwendig (aber im Sinne schneller zugriffszeiten trotzdem wünschenswert).

=== Vorgehen bei Kollisionen ===

==== Sequentielles Sondieren====
Probiere den nächsten Index: <tt>index = (index+1) % capacity</tt>

* Vorteil: einfach
* Nachteil: Clusterbildung

Clusterbildung heißt, dass sich größere zusammenhängende Bereiche bilden die belegt sind, unterbrochen von Bereichen die komplett frei sind. Beim Versuche des Einfügens eines Elements an einen Platz, der schon belegt ist, muss jetzt das ganze Cluster sequentiell durchlaufen werden, bis ein freier Platz gefunden wird. Damit entspricht die Komplexität der Suche der mittleren Länge der belegten Bereiche, was sich entsprechend in einer langsamen Suche widerspiegelt.

==== Doppeltes Hashing ====
Bestimme einen neuen Index (bei Kollisionen) durch eine ''2. Hashfunktion''.

Das doppelte Hashing wird typischerweise in der Praxis angewendet und liegt auch der Python Implementierung des Datentyps ''Dictionary'' (Syntax <tt>{'a':1, 'b':2, 'c':3}</tt> zugrunde.

Eine effiziente Implementierung dieses Datentyps ist für die Performance der Skriptsprache Python extrem wichtig, da z.B. beim Aufruf einer Funktion der auszuführunde Code in einem Dictionary unter dem Schlüssel ''Funktionsname'' nachgeschlagen wird oder die Werte lokaler Variablen innerhalb einer Funktion ebenfalls in einem Dictionary zu finden sind.

Für die Implementierung in Python werden wieder die obigen Klassen <tt>HashNode</tt> (das Attribut <tt>next</tt> kann allerdings jetzt entfernt werden) und <tt>HashTable</tt> benötigt, es folgen die angepassten Implementationen von <tt>__setitem</tt> und <tt>__getitem__</tt>:

def __setitem__(self, key, value):
h = hash(key)
index = h % self.capacity
while True:
if self.array[index] is None or self.array[index].key is None:
# das Feld ist frei (1. Abfrage)
# oder das Feld ist als frei markiert (2. Abfrage)
self.array[index] = HashNode(key, value)
self.size +=1
return
if self.array[index].key == key:
# Es gibt diesen Schlüssel schon,
# überschreibe die Daten
self.array[index].data = value
return
# Letzter Fall: Kollision => neuer Index durch 2. Hashfunktion
index = (5*index+1+h) % self.capacity
h = h >> 5

Die vorgestellte Implementierung orientiert sich an Pythons interner Dictionary Implementierung, der zugehörige Quelltext (mit ausführlichem Kommentar) findet sich unter [http://svn.python.org/view/*checkout*/python/trunk/Objects/dictobject.c dictobject.c Python Implementation (SVN)]

===== Komplexität des offenen Hashings =====

* Annahme: uniformes Hashing, das heißt alle Indizes haben gleiche Wahrscheinlichkeit
* Füllstand <math>\alpha = \frac{\text{size}}{\text{capacity}}</math>

* '''Erfolglose Suche''' (d.h. es wird entweder ein neues Element eingefügt oder ein <tt>KeyError</tt> geworfen): Untere Schranke für die Komplexität ist <math>\Omega\left(\frac{1}{1-\alpha}\right)</math> Schritte (= Anzahl der notwendigen index-Berechnungen).
* '''Erfolgreiche Suche''' <math>\Omega\left(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\right)</math> Schritte.

{| border="1" cellspacing="0" cellpadding="5" align="center"
! <math>\alpha</math>
! 0.5
! 0.9
|-
| erfolglos
| 2.0
| 10
|-
| erfolgreich
| 1.4
| 2.6
|}

===== Wahl der Kapazität =====
In Python wird <tt>capacity</tt> Aufgrund der obigen Beobachtung so gewählt, dass <math>\alpha \leq 2/3</math>. Falls <math>\alpha</math> größer werden sollte, verdopple die Kapazität und kopiere das alte array in das neue Array (analog zum dynamischen Array)

In Python werden die Kapazitätsgrößen als Zweierpotenzen gewählt, also 4,8,16,32,...,
so dass <tt>h % self.capacity</tt> nur die unteren Bits von <tt>h</tt> benutzt.

== Anwendung von Hashing ==

* Hashtabelle, assoziatives Aray
* Sortieren in linearer Zeit (Übungsaufgabe 6.2)
* Suchen von Strings in Texten: Rabin-Karp-Algorithmus
* ...

=== Rabin Karp Algorithmus ===
In Textverarbeitungsanwendungen ist eine häufig benutzte Funktion die ''Search & Replace'' Funktionalität. Die Suche sollte in O(len(text)) möglich sein, aber ein naiver Algorithmus braucht O(len(text)*len(searchstring))

==== Naive Implementierung der Suche ====
def search(text, s):
M, N = len(text), len(s)
for k in range(M-N):
if s==text[k:k+N]: # O(N), da N Zeichen verglichen werden müssen
return k
return -1 #nicht gefunden

==== Idee des Rabin Karp Algorithmus ====
Statt Vergleichen <tt>s==text[k:k+N]</tt>, die O(N) benötigen da N Vergleiche der Buchstaben durchgeführt werden müssen, Vergleiche die Hashs von Suchstring und dem zu untersuchenden Textabschnitt: <tt>hash(s) == hash(text[k:k+N])</tt>. Dabei muss natürlich <tt>hash(s)</tt> nur einmal berechnet werden, wohingegen <tt>hash(text[k:k+N])</tt> immer wieder neu berechnet werden muss. Damit der Vergleich O(1) sein kann, ist es deswegen erforderlich, eine solche Hashfunktion zu haben, die nicht alle Zeichen (das wäre O(N) ) einlesen muss, sondern die vorhergehende Hashfunktion mit einbezieht.

Eine solche Hashfunktion heißt ''Running Hash'' und funktioniert analog zum ''Sliding Mean''.

Die Running Hash Funktion berechnet in O(1) den hash von <tt>text[k+1:k+1+N]</tt> ausgehend vom hash für <tt>text[k:k+N]</tt>.

Idee: Interpretiere den Text als Ziffern in einer base d Darstellung:

<math>h_k = \text{text}[k]\cdot d^{N-1} + \text{text}[k]\cdot d^{N-2} + \cdots + \text{text}[k+N-1]</math>

Für die Basis 10 (Dezimalsystem) ergibt sich also

<math>h_k = \text{text}[k]\cdot {10}^{N-1} + \text{text}[k]\cdot {10}^{N-2} + \cdots + \text{text}[k+N-1]</math>

Daraus folgt

<math>h_{k+1} = 10\cdot h_k - \text{text}[k]\cdot {10}^{N} + \text{text}[k+N]</math>

Die Komplexität dieses Updates ist O(1), falls man <math>{10}^{N}</math> vorberechnet hat.

In der Realität wählt man dann d=32 und benutzt noch an einigen Stellen modulo Operationen, um die Zahlen nicht zu groß werden zu lassen.

==== Implementation ====
def searchRabinKarp(text, s):
ht, hs, dN = 0, 0, 1
M, N = len(text), len(s)
d, q = 32, 33554393 # q ist eine große Primzahl, aber so, dass d*q < 2**32 (um Überlauf zu vermeiden)

#Initialisierung
for k in range(N):
ht = (ht*d + ord(text[k])) % q
#ord() gibt die ASCIInummer des übergebenen Zeichens zurück
ds = (hs*d + ord( s[k] )) % q
dN = (dN*a) % q
#Die Variablen sind jetzt wie folgt initialisiert:
#ht = hash(text[0:N])
#hs = hash(s)
#dN = (d**N) % q

#Hauptschleife
k = 0
while k < M-N:
if hs == ht and s==text[k:k+N]:
return k # serch string an Position k gefunden
if k+N < M:
ht = (d*ht - dN * ord(text[k]) + dN*q + ord(text[k+N]) ) % q
k +=1
return -1 # search string nicht gefunden

Hashing und assoziative Arrays

2008-06-10T21:33:45Z

Thorben: /* Implementation in Python */

Mitschrift gibts [http://hci.iwr.uni-heidelberg.de/alda/images/AlDa.pdf hier] als PDF und [http://hci.iwr.uni-heidelberg.de/alda/images/Alda_source.pdf hier] gibts die TeX-Sourcen, leider als PDF weil man wohl keine .TeXs hochladen darf. Originale gibts auf Anfrage bei kirchner at cl dot uni minus heidelberg dot de. Wird das Package "listings" verwendet, das gibts bei [http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/ http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/]

Tipp- und sonstige Fehler dürfen gerne verbessert und erneut hochgeladen werden, oder gebt mir per Email Bescheid, dann pflege ich die Korrektur ein :)

Ich Finde dein Aufschrieb sollte ins Wiki übetragen werden, das bietet auch alles, was
du mit Latex machen kannst. Die Bäume kannst du z.B. mit Latex zeichnen, einen pro Seite und diese dann in eine png Datei umwandeln. Wie sowas geht kann man z.B. in den Quellen von doxygen oder mediawiki selbst nachlesen. Oder man zoomt rein und macht einen Screenshot :-)

== Hashtabelle mit linearer Verkettung ==
Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem
Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

===Implementation in Python===
''HashNode'' ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert
und mit Hilfe von ''next'' eine verkettete Liste realisiert
class HashNode:
def __init__(self,key,data,next):
self.key = key
self.data = data
self.next = next # Verkettung!

Die eigentliche Hashtabelle wird in der Klasse ''HashTable'' implementiert:
class HashTable:
def __init__(self):
self.capacity = ... # Geeignete Werte siehe unten
self.size = 0
self.array = [None]*self.capacity

In Python wird der Zugriffsoperator ''[ ]'' für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:
def __setitem__(self, key, value)

so dass im Programmtext dann folgende Syntax möglich ist: <tt>a[key] = value</tt> (schreibender Zugriff auf <tt>a[key]</tt>).
Analog wird der lesende Zugriff <tt>value = a[key]</tt> wie folgt umgesetzt:
def __getitem__(self, key, value)

Implementierung der <tt>__setitem__</tt>-Funktion in der <tt>HashTable</tt>-Klasse:
def __setitem__(self, key, value):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key:
# Element key ist schon in der Tabelle
#Überschreibe die Daten mit dem neuen Wert
node.data = value
return
# Kollision des Hashwerts, probiere nächsten Key aus
node = node.next
# Kein Element hatte den richtigen Schlüssel.
# ==>Es gibt diesen Schlüssel noch nicht
# Füge also ein neues Element in die Hashtabelle ein

self.array[index] = HashNode(key, value, self.array[index])
# Der alte Anfang der Liste wurde der Nachfolger des neu eingefügten
# ersten Elements

self.size += 1

Und die Implementierung der <tt>__getitem__</tt> Funktionen:
def __getitem__(self, key):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key: # Gefunden!
return node.data
node = node.next
raise KeyError(key)

==== Wahl der Kapazität ====
In der C++ Standardbibliothek (Klasse <tt>std::hash_map</tt>) wird die Hashtabelle häufig mit Hilfe der linearen Verkettung
imlementiert. Dabei wird <tt>capacity</tt> immer als ''Primzahl'' gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:
53, 97, 193, 398, 769, ...

Das hat zur Folge, dass <tt>hash(key) % self.capacity</tt> ''alle'' Bits von h benutzt (Eigenschaft aus der Zahlentheorie). Die Kapizität wird vergrößert, wenn <tt>size == capacity</tt> erreicht wird. Analog zum dynamischen Array werden die Daten dann aus dem alten Array (<tt>self.array</tt>) in ein entsprechend vergrößertes neues Array kopiert.

== Hashtabelle mit offener Adressierung (offenes Hashing) ==
Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

=== Idee ===
Wenn <tt>array[index]</tt> durch Kollision bereits vergeben ist, probiere einen
anderen Index aus.

* Das Array enthält pro Element höchstens ein (key,value)-Paar
* Das Array muss stets mindestens ''einen'' freien Platz haben (sonst gäbe es beim Ausprobieren anderer Indizes eine Endlosschleife). Es gilt immer <tt>self.size < self.capacity</tt>. Dies war bei der vorigen Hash-Implementation mit linearer Verkettung nicht notwendig (aber im Sinne schneller zugriffszeiten trotzdem wünschenswert).

=== Vorgehen bei Kollisionen ===

==== Sequentielles Sondieren====
Probiere den nächsten Index: <tt>index = (index+1) % capacity</tt>

* Vorteil: einfach
* Nachteil: Clusterbildung

Clusterbildung heißt, dass sich größere zusammenhängende Bereiche bilden die belegt sind, unterbrochen von Bereichen die komplett frei sind. Beim Versuche des Einfügens eines Elements an einen Platz, der schon belegt ist, muss jetzt das ganze Cluster sequentiell durchlaufen werden, bis ein freier Platz gefunden wird. Damit entspricht die Komplexität der Suche der mittleren Länge der belegten Bereiche, was sich entsprechend in einer langsamen Suche widerspiegelt.

==== Doppeltes Hashing ====
Bestimme einen neuen Index (bei Kollisionen) durch eine ''2. Hashfunktion''.

Das doppelte Hashing wird typischerweise in der Praxis angewendet und liegt auch der Python Implementierung des Datentyps ''Dictionary'' (Syntax <tt>{'a':1, 'b':2, 'c':3}</tt> zugrunde.

Eine effiziente Implementierung dieses Datentyps ist für die Performance der Skriptsprache Python extrem wichtig, da z.B. beim Aufruf einer Funktion der auszuführunde Code in einem Dictionary unter dem Schlüssel ''Funktionsname'' nachgeschlagen wird oder die Werte lokaler Variablen innerhalb einer Funktion ebenfalls in einem Dictionary zu finden sind.

Für die Implementierung in Python werden wieder die obigen Klassen <tt>HashNode</tt> (das Attribut <tt>next</tt> kann allerdings jetzt entfernt werden) und <tt>HashTable</tt> benötigt, es folgen die angepassten Implementationen von <tt>__setitem</tt> und <tt>__getitem__</tt>:

def __setitem__(self, key, value):
h = hash(key)
index = h % self.capacity
while True:
if self.array[index] is None or self.array[index].key is None:
# das Feld ist frei (1. Abfrage)
# oder das Feld ist als frei markiert (2. Abfrage)
self.array[index] = HashNode(key, value)
self.size +=1
return
if self.array[index].key == key:
# Es gibt diesen Schlüssel schon,
# überschreibe die Daten
self.array[index].data = value
return
# Letzter Fall: Kollision => neuer Index durch 2. Hashfunktion
index = (5*index+1+h) % self.capacity
h = h >> 5

Die vorgestellte Implementierung orientiert sich an Pythons interner Dictionary Implementierung, der zugehörige Quelltext (mit ausführlichem Kommentar) findet sich unter [http://svn.python.org/view/*checkout*/python/trunk/Objects/dictobject.c dictobject.c Python Implementation (SVN)]

===== Komplexität des offenen Hashings =====

* Annahme: uniformes Hashing, das heißt alle Indizes haben gleiche Wahrscheinlichkeit
* Füllstand <math>\alpha = \frac{\text{size}}{\text{capacity}}</math>

* '''Erfolglose Suche''' (d.h. es wird entweder ein neues Element eingefügt oder ein <tt>KeyError</tt> geworfen): Untere Schranke für die Komplexität ist <math>\Omega\left(\frac{1}{1-\alpha}\right)</math> Schritte (= Anzahl der notwendigen index-Berechnungen).
* '''Erfolgreiche Suche''' <math>\Omega\left(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\right)</math> Schritte.

{| border="1" cellspacing="0" cellpadding="5" align="center"
! <math>\alpha</math>
! 0.5
! 0.9
|-
| erfolglos
| 2.0
| 10
|-
| erfolgreich
| 1.4
| 2.6
|}

===== Wahl der Kapazität =====
In Python wird <tt>capacity</tt> Aufgrund der obigen Beobachtung so gewählt, dass <math>\alpha \leq 2/3</math>. Falls <math>\alpha</math> größer werden sollte, verdopple die Kapazität und kopiere das alte array in das neue Array (analog zum dynamischen Array)

In Python werden die Kapazitätsgrößen als Zweierpotenzen gewählt, also 4,8,16,32,...,
so dass <tt>h % self.capacity</tt> nur die unteren Bits von <tt>h</tt> benutzt.

== Anwendung von Hashing ==

* Hashtabelle, assoziatives Aray
* Sortieren in linearer Zeit (Übungsaufgabe 6.2)
* Suchen von Strings in Texten: Rabin-Karp-Algorithmus
* ...

=== Rabin Karp Algorithmus ===
In Textverarbeitungsanwendungen ist eine häufig benutzte Funktion die ''Search & Replace'' Funktionalität. Die Suche sollte in O(len(text)) möglich sein, aber ein naiver Algorithmus braucht O(len(text)*len(searchstring))

==== Naive Implementierung der Suche ====
def search(text, s):
M, N = len(text), len(s)
for k in range(M-N):
if s==text[k:k+N]: # O(N), da N Zeichen verglichen werden müssen
return k
return -1 #nicht gefunden

==== Idee des Rabin Karp Algorithmus ====
Statt Vergleichen <tt>s==text[k:k+N]</tt>, die O(N) benötigen da N Vergleiche der Buchstaben durchgeführt werden müssen, Vergleiche die Hashs von Suchstring und dem zu untersuchenden Textabschnitt: <tt>hash(s) == hash(text[k:k+N])</tt>. Dabei muss natürlich <tt>hash(s)</tt> nur einmal berechnet werden, wohingegen <tt>hash(text[k:k+N])</tt> immer wieder neu berechnet werden muss. Damit der Vergleich O(1) sein kann, ist es deswegen erforderlich, eine solche Hashfunktion zu haben, die nicht alle Zeichen (das wäre O(N) ) einlesen muss, sondern die vorhergehende Hashfunktion mit einbezieht.

Eine solche Hashfunktion heißt ''Running Hash'' und funktioniert analog zum ''Sliding Mean''.

Die Running Hash Funktion berechnet in O(1) den hash von <tt>text[k+1:k+1+N]</tt> ausgehend vom hash für <tt>text[k:k+N]</tt>.

Idee: Interpretiere den Text als Ziffern in einer base d Darstellung:

<math>h_k = \text{text}[k]\cdot d^{N-1} + \text{text}[k]\cdot d^{N-2} + \cdots + \text{text}[k+N-1]</math>

Für die Basis 10 (Dezimalsystem) ergibt sich also

<math>h_k = \text{text}[k]\cdot {10}^{N-1} + \text{text}[k]\cdot {10}^{N-2} + \cdots + \text{text}[k+N-1]</math>

Daraus folgt

<math>h_{k+1} = 10\cdot h_k - \text{text}[k]\cdot {10}^{N} + \text{text}[k+N]</math>

Die Komplexität dieses Updates ist O(1), falls man <math>{10}^{N}</math> vorberechnet hat.

In der Realität wählt man dann d=32 und benutzt noch an einigen Stellen modulo Operationen, um die Zahlen nicht zu groß werden zu lassen.

==== Implementation ====
def searchRabinKarp(text, s):
ht, hs, dN = 0, 0, 1
M, N = len(text), len(s)
d, q = 32, 33554393 # q ist eine große Primzahl, aber so, dass d*q < 2**32 (um Überlauf zu vermeiden)

#Initialisierung
for k in range(N):
ht = (ht*d + ord(text[k])) % q
#ord() gibt die ASCIInummer des übergebenen Zeichens zurück
ds = (hs*d + ord( s[k] )) % q
dN = (dN*a) % q
#Die Variablen sind jetzt wie folgt initialisiert:
#ht = hash(text[0:N])
#hs = hash(s)
#dN = (d**N) % q

#Hauptschleife
k = 0
while k < M-N:
if hs == ht and s==text[k:k+N]:
return k # serch string an Position k gefunden
if k+N < M:
ht = (d*ht - dN * ord(text[k]) + dN*q + ord(text[k+N]) ) % q
k +=1
return -1 # search string nicht gefunden

Talk:Hashing und assoziative Arrays

2008-06-04T17:29:33Z

Thorben:

Warum als PDF? Das ist doch völlig am Sinn des Wikis vorbei...

Finde ich auch, wenn du es schon als tex gemacht hast ist es doch super einfach
es in die Wiki zu übertragen, die unterstützt ja über < math > und < /math > auch
viele Latexbefehle...

Iteration versus Rekursion

2008-06-04T17:28:27Z

Thorben: Removing all content from page

Hashing und assoziative Arrays

2008-06-04T17:27:55Z

Thorben:

Mitschrift gibts [http://hci.iwr.uni-heidelberg.de/alda/images/AlDa.pdf hier] als PDF und [http://hci.iwr.uni-heidelberg.de/alda/images/Alda_source.pdf hier] gibts die TeX-Sourcen, leider als PDF weil man wohl keine .TeXs hochladen darf. Originale gibts auf Anfrage bei kirchner at cl dot uni minus heidelberg dot de. Wird das Package "listings" verwendet, das gibts bei [http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/ http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/]

Tipp- und sonstige Fehler dürfen gerne verbessert und erneut hochgeladen werden, oder gebt mir per Email Bescheid, dann pflege ich die Korrektur ein :)

== Hashtabelle mit linearer Verkettung ==
Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem
Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

===Implementation in Python===
''HashNode'' ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert
und mit hilfe von ''next'' eine verkettete Liste darstellt
class HashNode:
def __init__(self,key,data,next):
self.key = key
self.data = data
self.next = next #Verkettung!

Die eigentliche Hashtabelle wir in der Klasse ''HashTable'' implementier:
class HashTable:
def __init__(self):
self.capacity = ... #Geigneter Wert
self.size = 0
self.array = [None]*self.capacity

In Python wird der Zugriffsoperator ''[ ]'' für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:
def __setitem__(self, key, value)

So dass im Programmtext dann folgender Syntax möglich ist: <tt>a[key] = value</tt>

Genauso wir die Zuweisung <tt>value=a[key]</tt> wie folgt umgesetzt
def __getitem__(self, key, value)

Implementierung der <tt>__setitem__</tt> Funktionen in der <tt>HashTable</tt> Klasse:
def __setitme__(self, key, value):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key:
#Element key ist schon in der Tabelle
#Überschreibe die Daten mit dem neuen Wert
node.data = value
return
#Kollision des Hashwerts, probiere nächsten Key aus
node = node.next
#Kein Element hatte den richtigen Schlüssel.
#==>Es gibt diesen Schlüssel noch nicht
#Füge also ein neues Element in die Hashtabelle ein

self.array[index] = HashNode(key, value, self.array[index])
#Der alte Anfang der List wurde der Nachfolger vom neue eingefügten
#ersten Element

size+=1

Und die Implementierung der <tt>__getitem__</tt> Funktionen:
def __getItem__(self, key):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key #Gefunden!
return Node.data
node = node.next
raise KeyError(key)

==== Wahl der Kapazität ====
In der C++ Standardbibliothek wird typischerweise ein Hash mit Hilfe der linearen Kette
imlementiert. Dabei wird <tt>capcity</tt> immer als ''Primzahl'' gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:
53, 97, 193, 398, 769, ...

Das hat zur Folge, dass <tt>h % self.capacity</tt> ''alle'' Bits von h benutzt (Eigenschaft aus der Zahlentheorie)

== Hashtabelle mit offener Adressierung (offenes Hashing) ==
Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

=== Idee ===
Wenn <tt>array[index]</tt> durch Kollision bereits vergeben ist, probiere einen
anderen Index aus.

* Das Array enthält pro Element höchstens ein (key,value)-Paar
* Das Array muss stets mindestens ''einen'' freien Platz haben (sonst gäbe es eine Endlosschleife). Es gilt immer <tt>self.size < self.capacity</tt>. Dies galt für die vorige Hash Implementation nicht.

=== Vorgehen bei Kollisionen ===

==== Sequentielles Suchen ====
Probiere den nächsten Index: <tt>index = index+1 % capacity</tt>

* Vorteil: einfach
* Nachteil: Clusterbildung

Clusterbildung heißt, dass sich größere zusammenhängende Bereiche bilden die belegt sind, unterbrochen von Bereichen die komplett frei sind. Beim Versuche des Einfügens eines Elements an einen Platz, der schon belegt ist, muss jetzt das ganze Cluster sequentiell durchlaufen werden, bis ein freier Platz gefunden wird. Damit entspricht die Komplexität der Suche der mittleren Länge der belegten Bereiche, was sich entsprechend in einer langsamen Suche widerspiegelt.

==== Doppeltes Hashing ====
Bestimme einen neuen Index (bei Kollisionen) durch eine ''2. Hashfunktion''.

Das doppelte Hashing wird typischerweise in der Praxis angewendet und liegt auch der Python Implementierung des Datentyps ''Dictionary'' (Syntax <tt>{'a':1, 'b':2, 'c':3}</tt> zugrunde.

Eine effiziente Implementierung dieses Datentyps ist für die Performance der Skriptsprache Python extrem wichtig, da z.B. beim Aufruf einer Funktion der auszuführunde Code in einem Dictionary unter dem Schlüssel ''Funktionsname'' nachgeschlagen wird oder die Werte lokaler Variablen innerhalb einer Funktion ebenfalls in einem Dictionary zu finden sind.

Für die Implementierung in Python werden wieder die obigen Klassen <tt>HashNode</tt> und <tt>HashTable</tt> benötigt, es folgen die angepassten Implementationen von <tt>__setitem</tt> und <tt>__getitem__</tt>:

def __setitem__(self, key, value):
h = hash(key)
index = h % self.capacity
while True:
if self.array[index] is None or self.array[index].key is None
#das Feld ist frei (1. Abfrage)
#oder das feld ist als frei markiert (2. Abfrage)
self.array[index] = HashNode(key, value)
self.size +=1
return
if self.array[index].key == key:
#Es gibt diesen Schlüssel schon,
#überschreibe die Daten
self.array[index].data = value
#Letzter Fall: Kollision
index = (5*index+1+h) % self.capacity
h = h >> 5

Die vorgestellte Implementierung orientiert sich an Pythons interner Dictionary Implementierung, der zugehörige Quelltext mit ausführlichem Kommentar) findet sich unter [http://svn.python.org/view/*checkout*/python/trunk/Objects/dictobject.c dictobject.c Python Implementation (SVN)]

===== Komplexität des offenen Hashings =====

* Annahme: uniformes Hashing, das heißt alle Indizes haben gleiche Wahrscheinlichkeit
* Füllstand <math>\alpha = \frac{\text{size}}{\text{capacity}}</math>

* '''Erfolglose Suche''' (d.h. es wird entweder ein neues Element eingefügt oder ein <tt>keyError</tt> geworfen): Untere Schranke für die Komplexität ist <math>\Omega\left(\frac{1}{1-\alpha}\right)</math> Schritte bzw. Anzahl von neuen index Berechnungen.
* '''Erfolgreiche Suche''' <math>\Omega\left(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\right)</math>

{| border="1" cellspacing="0" cellpadding="5" align="center"
! <math>\alpha</math>
! 0.5
! 0.9
|-
| erfolglos
| 2.0
| 10
|-
| erfolgreich
| 1.4
| 2.6
|}

===== Wahl der Kapazität =====
In Python wird <tt>capacity</tt> Aufgrund der obigen Beobachtung so gewählt, dass <math>\alpha \leq 2/3</math>. Falls <math>\alpha</math> größer werden sollte, verdopple die Kapazität und kopiere das alte array in das neue Array (analog zum dynamischen Array)

In Python werden die Kapazitätsgrößen als Zweierpotenzen gewählt, also 4,8,16,32,...,
so dass <tt>h % self.capacity</tt> nur die unteren Bits von <tt>h</tt> benutzt.

== Anwendung von Hashing ==

* Hashtabelle, assoziatives Aray
* Sortieren in linearer Zeit (Übungsaufgabe 6.2)
* Suchen von Strings in Texten
* ...

=== Rabin Karp Algorithmus ===
In Textverarbeitungsanwendungen ist eine häufig benutzte Funktion die ''Search & Replace'' Funktionalität. Die Suche sollte in O(len(text)) möglich sein, aber ein naiver Algorithmus braucht O(len(text)*len(searchstring))

==== Naive Implementierung der Suche ====
def search(text, s):
M, N = len(text), len(s)
for k in range(M-N):
if s==text[k:k+N]
return k
return -1 #nicht gefunden

==== Idee des Rabin Karp Algorithmus ====
Statt Vergleichen <tt>s==text[k:k+N], die O(N) benötigen da N Vergleiche der Buchstaben durchgeführt werden müssen, Vergleiche die Hashs von Suchstring und dem zu untersuchenden Textabschnitt: <tt>hash(s) == hash(text[k:k+N])</tt>. Dabei muss natürlich <tt>hash(s)</tt> nur einmal berechnet werden, wohingegen <tt>hash(text[k:k+N])</tt> immer wieder neu berechnet werden muss. Damit der Vergleich O(1) sein kann, ist es deswegen erforderlich, eine solche Hashfunktion zu haben, die nicht alle Zeichen (das wäre O(N) ) einlesen muss, sondern die vorhergehende Hashfunktion mit einbezieht.

Eine solche Hashfunktion heißt ''Running Hash'' und funktioniert analog zum ''Sliding Mean''.

Die Running Hash Funktion berechnet in O(1) den hash von <tt>text[k+1:k+1+N]</tt> ausgehend vom hash für <tt>text[k:k+N]</tt>.

Idee: Interpretiere den Text als Ziffern in einer base d Darstellung:

<math>h_k = \text{text}[k]\cdot d^{N-1} + \text{text}[k]\cdot d^{N-2} + \cdots + \text{text}[k+N-1]</math>

Für die Basis 10 (Dezimalsystem) ergibt sich also

<math>h_k = \text{text}[k]\cdot {10}^{N-1} + \text{text}[k]\cdot {10}^{N-2} + \cdots + \text{text}[k+N-1]</math>
Daraus folgt
<math>h_{k+1} = 10\cdot h_k - \text{text}[k]\cdot {10}^{N} + \text{text}[k+N]</math>
Und die Komplexität ist O(1).

In der Realität wählt man dann d=32 und benutzt noch an einigen Stellen modulo Operationen, um die Zahlen nicht zu groß werden zu lassen.

==== Implementation ====
def searchRabinKarp(text, s):
ht, hs, dN = 0, 0, 1
M, N = len(text), len(s)
d, q = 32, <sehr große Primzahl>

#Initialisierung
for k in range(N):
ht = ht*d + ord(text[k]) % q
#ord() gibt die ASCIInummer des übergebenen Zeichens zurück
ds = hs*d + ord( s[k] )
dN = (dN*a) % q
#Die Variable sind jetzt wie folgt initialisiert:
#ht = hash(text[0:N])
#hs = hash(s)
#dN = (d**N) % q

#Hauptschleife
k = 0
while k < M-N:
if hs == ht and s==text[k:k+N]:
return k
ht = (d*ht - dN * ord(text[k]) + dN*q + ord(text[k+M]) ) % q
k +=1
return -1

Iteration versus Rekursion

2008-06-04T17:10:18Z

Thorben:

== Hashtabelle mit linearer Verkettung ==
Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem
Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

===Implementation in Python===
''HashNode'' ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert
und mit hilfe von ''next'' eine verkettete Liste darstellt
class HashNode:
def __init__(self,key,data,next):
self.key = key
self.data = data
self.next = next #Verkettung!

Die eigentliche Hashtabelle wir in der Klasse ''HashTable'' implementier:
class HashTable:
def __init__(self):
self.capacity = ... #Geigneter Wert
self.size = 0
self.array = [None]*self.capacity

In Python wird der Zugriffsoperator ''[ ]'' für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:
def __setitem__(self, key, value)

So dass im Programmtext dann folgender Syntax möglich ist: <tt>a[key] = value</tt>

Genauso wir die Zuweisung <tt>value=a[key]</tt> wie folgt umgesetzt
def __getitem__(self, key, value)

Implementierung der <tt>__setitem__</tt> Funktionen in der <tt>HashTable</tt> Klasse:
def __setitme__(self, key, value):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key:
#Element key ist schon in der Tabelle
#Überschreibe die Daten mit dem neuen Wert
node.data = value
return
#Kollision des Hashwerts, probiere nächsten Key aus
node = node.next
#Kein Element hatte den richtigen Schlüssel.
#==>Es gibt diesen Schlüssel noch nicht
#Füge also ein neues Element in die Hashtabelle ein

self.array[index] = HashNode(key, value, self.array[index])
#Der alte Anfang der List wurde der Nachfolger vom neue eingefügten
#ersten Element

size+=1

Und die Implementierung der <tt>__getitem__</tt> Funktionen:
def __getItem__(self, key):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key #Gefunden!
return Node.data
node = node.next
raise KeyError(key)

==== Wahl der Kapazität ====
In der C++ Standardbibliothek wird typischerweise ein Hash mit Hilfe der linearen Kette
imlementiert. Dabei wird <tt>capcity</tt> immer als ''Primzahl'' gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:
53, 97, 193, 398, 769, ...

Das hat zur Folge, dass <tt>h % self.capacity</tt> ''alle'' Bits von h benutzt (Eigenschaft aus der Zahlentheorie)

== Hashtabelle mit offener Adressierung (offenes Hashing) ==
Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

=== Idee ===
Wenn <tt>array[index]</tt> durch Kollision bereits vergeben ist, probiere einen
anderen Index aus.

* Das Array enthält pro Element höchstens ein (key,value)-Paar
* Das Array muss stets mindestens ''einen'' freien Platz haben (sonst gäbe es eine Endlosschleife). Es gilt immer <tt>self.size < self.capacity</tt>. Dies galt für die vorige Hash Implementation nicht.

=== Vorgehen bei Kollisionen ===

==== Sequentielles Suchen ====
Probiere den nächsten Index: <tt>index = index+1 % capacity</tt>

* Vorteil: einfach
* Nachteil: Clusterbildung

Clusterbildung heißt, dass sich größere zusammenhängende Bereiche bilden die belegt sind, unterbrochen von Bereichen die komplett frei sind. Beim Versuche des Einfügens eines Elements an einen Platz, der schon belegt ist, muss jetzt das ganze Cluster sequentiell durchlaufen werden, bis ein freier Platz gefunden wird. Damit entspricht die Komplexität der Suche der mittleren Länge der belegten Bereiche, was sich entsprechend in einer langsamen Suche widerspiegelt.

==== Doppeltes Hashing ====
Bestimme einen neuen Index (bei Kollisionen) durch eine ''2. Hashfunktion''.

Das doppelte Hashing wird typischerweise in der Praxis angewendet und liegt auch der Python Implementierung des Datentyps ''Dictionary'' (Syntax <tt>{'a':1, 'b':2, 'c':3}</tt> zugrunde.

Eine effiziente Implementierung dieses Datentyps ist für die Performance der Skriptsprache Python extrem wichtig, da z.B. beim Aufruf einer Funktion der auszuführunde Code in einem Dictionary unter dem Schlüssel ''Funktionsname'' nachgeschlagen wird oder die Werte lokaler Variablen innerhalb einer Funktion ebenfalls in einem Dictionary zu finden sind.

Für die Implementierung in Python werden wieder die obigen Klassen <tt>HashNode</tt> und <tt>HashTable</tt> benötigt, es folgen die angepassten Implementationen von <tt>__setitem</tt> und <tt>__getitem__</tt>:

def __setitem__(self, key, value):
h = hash(key)
index = h % self.capacity
while True:
if self.array[index] is None or self.array[index].key is None
#das Feld ist frei (1. Abfrage)
#oder das feld ist als frei markiert (2. Abfrage)
self.array[index] = HashNode(key, value)
self.size +=1
return
if self.array[index].key == key:
#Es gibt diesen Schlüssel schon,
#überschreibe die Daten
self.array[index].data = value
#Letzter Fall: Kollision
index = (5*index+1+h) % self.capacity
h = h >> 5

Die vorgestellte Implementierung orientiert sich an Pythons interner Dictionary Implementierung, der zugehörige Quelltext mit ausführlichem Kommentar) findet sich unter [http://svn.python.org/view/*checkout*/python/trunk/Objects/dictobject.c dictobject.c Python Implementation (SVN)]

===== Komplexität des offenen Hashings =====

* Annahme: uniformes Hashing, das heißt alle Indizes haben gleiche Wahrscheinlichkeit
* Füllstand <math>\alpha = \frac{\text{size}}{\text{capacity}}</math>

* '''Erfolglose Suche''' (d.h. es wird entweder ein neues Element eingefügt oder ein <tt>keyError</tt> geworfen): Untere Schranke für die Komplexität ist <math>\Omega\left(\frac{1}{1-\alpha}\right)</math> Schritte bzw. Anzahl von neuen index Berechnungen.
* '''Erfolgreiche Suche''' <math>\Omega\left(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\right)</math>

{| border="1" cellspacing="0" cellpadding="5" align="center"
! <math>\alpha</math>
! 0.5
! 0.9
|-
| erfolglos
| 2.0
| 10
|-
| erfolgreich
| 1.4
| 2.6
|}

===== Wahl der Kapazität =====
In Python wird <tt>capacity</tt> Aufgrund der obigen Beobachtung so gewählt, dass <math>\alpha \leq 2/3</math>. Falls <math>\alpha</math> größer werden sollte, verdopple die Kapazität und kopiere das alte array in das neue Array (analog zum dynamischen Array)

In Python werden die Kapazitätsgrößen als Zweierpotenzen gewählt, also 4,8,16,32,...,
so dass <tt>h % self.capacity</tt> nur die unteren Bits von <tt>h</tt> benutzt.

== Anwendung von Hashing ==

* Hashtabelle, assoziatives Aray
* Sortieren in linearer Zeit (Übungsaufgabe 6.2)
* Suchen von Strings in Texten
* ...

=== Rabin Karp Algorithmus ===
In Textverarbeitungsanwendungen ist eine häufig benutzte Funktion die ''Search & Replace'' Funktionalität. Die Suche sollte in O(len(text)) möglich sein, aber ein naiver Algorithmus braucht O(len(text)*len(searchstring))

==== Naive Implementierung der Suche ====
def search(text, s):
M, N = len(text), len(s)
for k in range(M-N):
if s==text[k:k+N]
return k
return -1 #nicht gefunden

==== Idee des Rabin Karp Algorithmus ====
Statt Vergleichen <tt>s==text[k:k+N], die O(N) benötigen da N Vergleiche der Buchstaben durchgeführt werden müssen, Vergleiche die Hashs von Suchstring und dem zu untersuchenden Textabschnitt: <tt>hash(s) == hash(text[k:k+N])</tt>. Dabei muss natürlich <tt>hash(s)</tt> nur einmal berechnet werden, wohingegen <tt>hash(text[k:k+N])</tt> immer wieder neu berechnet werden muss. Damit der Vergleich O(1) sein kann, ist es deswegen erforderlich, eine solche Hashfunktion zu haben, die nicht alle Zeichen (das wäre O(N) ) einlesen muss, sondern die vorhergehende Hashfunktion mit einbezieht.

Eine solche Hashfunktion heißt ''Running Hash'' und funktioniert analog zum ''Sliding Mean''.

Die Running Hash Funktion berechnet in O(1) den hash von <tt>text[k+1:k+1+N]</tt> ausgehend vom hash für <tt>text[k:k+N]</tt>.

Idee: Interpretiere den Text als Ziffern in einer base d Darstellung:

<math>h_k = \text{text}[k]\cdot d^{N-1} + \text{text}[k]\cdot d^{N-2} + \cdots + \text{text}[k+N-1]</math>

Für die Basis 10 (Dezimalsystem) ergibt sich also

<math>h_k = \text{text}[k]\cdot {10}^{N-1} + \text{text}[k]\cdot {10}^{N-2} + \cdots + \text{text}[k+N-1]</math>
Daraus folgt
<math>h_{k+1} = 10\cdot h_k - \text{text}[k]\cdot {10}^{N} + \text{text}[k+N]</math>
Und die Komplexität ist O(1).

In der Realität wählt man dann d=32 und benutzt noch an einigen Stellen modulo Operationen, um die Zahlen nicht zu groß werden zu lassen.

==== Implementation ====
def searchRabinKarp(text, s):
ht, hs, dN = 0, 0, 1
M, N = len(text), len(s)
d, q = 32, <sehr große Primzahl>

#Initialisierung
for k in range(N):
ht = ht*d + ord(text[k]) % q
#ord() gibt die ASCIInummer des übergebenen Zeichens zurück
ds = hs*d + ord( s[k] )
dN = (dN*a) % q
#Die Variable sind jetzt wie folgt initialisiert:
#ht = hash(text[0:N])
#hs = hash(s)
#dN = (d**N) % q

#Hauptschleife
k = 0
while k < M-N:
if hs == ht and s==text[k:k+N]:
return k
ht = (d*ht - dN * ord(text[k]) + dN*q + ord(text[k+M]) ) % q
k +=1
return -1

Iteration versus Rekursion

2008-06-04T17:08:36Z

Thorben: /* Implementation */

== Hashtabelle mit linearer Verkettung ==
Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem
Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

===Implementation in Python===
''HashNode'' ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert
und mit hilfe von ''next'' eine verkettete Liste darstellt
class HashNode:
def __init__(self,key,data,next):
self.key = key
self.data = data
self.next = next #Verkettung!

Die eigentliche Hashtabelle wir in der Klasse ''HashTable'' implementier:
class HashTable:
def __init__(self):
self.capacity = ... #Geigneter Wert
self.size = 0
self.array = [None]*self.capacity

In Python wird der Zugriffsoperator ''[ ]'' für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:
def __setitem__(self, key, value)

So dass im Programmtext dann folgender Syntax möglich ist: <tt>a[key] = value</tt>

Genauso wir die Zuweisung <tt>value=a[key]</tt> wie folgt umgesetzt
def __getitem__(self, key, value)

Implementierung der <tt>__setitem__</tt> Funktionen in der <tt>HashTable</tt> Klasse:
def __setitme__(self, key, value):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key:
#Element key ist schon in der Tabelle
#Überschreibe die Daten mit dem neuen Wert
node.data = value
return
#Kollision des Hashwerts, probiere nächsten Key aus
node = node.next
#Kein Element hatte den richtigen Schlüssel.
#==>Es gibt diesen Schlüssel noch nicht
#Füge also ein neues Element in die Hashtabelle ein

self.array[index] = HashNode(key, value, self.array[index])
#Der alte Anfang der List wurde der Nachfolger vom neue eingefügten
#ersten Element

size+=1

Und die Implementierung der <tt>__getitem__</tt> Funktionen:
def __getItem__(self, key):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key #Gefunden!
return Node.data
node = node.next
raise KeyError(key)

==== Wahl der Kapazität ====
In der C++ Standardbibliothek wird typischerweise ein Hash mit Hilfe der linearen Kette
imlementiert. Dabei wird <tt>capcity</tt> immer als ''Primzahl'' gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:
53, 97, 193, 398, 769, ...

Das hat zur Folge, dass <tt>h % self.capacity</tt> ''alle'' Bits von h benutzt (Eigenschaft aus der Zahlentheorie)

== Hashtabelle mit offener Adressierung (offenes Hashing) ==
Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

=== Idee ===
Wenn <tt>array[index]</tt> durch Kollision bereits vergeben ist, probiere einen
anderen Index aus.

* Das Array enthält pro Element höchstens ein (key,value)-Paar
* Das Array muss stets mindestens ''einen'' freien Platz haben (sonst gäbe es eine Endlosschleife). Es gilt immer <tt>self.size < self.capacity</tt>. Dies galt für die vorige Hash Implementation nicht.

=== Vorgehen bei Kollisionen ===

==== Sequentielles Suchen ====
Probiere den nächsten Index: <tt>index = index+1 % capacity</tt>

* Vorteil: einfach
* Nachteil: Clusterbildung

Clusterbildung heißt, dass sich größere zusammenhängende Bereiche bilden die belegt sind, unterbrochen von Bereichen die komplett frei sind. Beim Versuche des Einfügens eines Elements an einen Platz, der schon belegt ist, muss jetzt das ganze Cluster sequentiell durchlaufen werden, bis ein freier Platz gefunden wird. Damit entspricht die Komplexität der Suche der mittleren Länge der belegten Bereiche, was sich entsprechend in einer langsamen Suche widerspiegelt.

==== Doppeltes Hashing ====
Bestimme einen neuen Index (bei Kollisionen) durch eine ''2. Hashfunktion''.

Das doppelte Hashing wird typischerweise in der Praxis angewendet und liegt auch der Python Implementierung des Datentyps ''Dictionary'' (Syntax <tt>{'a':1, 'b':2, 'c':3}</tt> zugrunde.

Eine effiziente Implementierung dieses Datentyps ist für die Performance der Skriptsprache Python extrem wichtig, da z.B. beim Aufruf einer Funktion der auszuführunde Code in einem Dictionary unter dem Schlüssel ''Funktionsname'' nachgeschlagen wird oder die Werte lokaler Variablen innerhalb einer Funktion ebenfalls in einem Dictionary zu finden sind.

Für die Implementierung in Python werden wieder die obigen Klassen <tt>HashNode</tt> und <tt>HashTable</tt> benötigt, es folgen die angepassten Implementationen von <tt>__setitem</tt> und <tt>__getitem__</tt>:

def __setitem__(self, key, value):
h = hash(key)
index = h % self.capacity
while True:
if self.array[index] is None or self.array[index].key is None
#das Feld ist frei (1. Abfrage)
#oder das feld ist als frei markiert (2. Abfrage)
self.array[index] = HashNode(key, value)
self.size +=1
return
if self.array[index].key == key:
#Es gibt diesen Schlüssel schon,
#überschreibe die Daten
self.array[index].data = value
#Letzter Fall: Kollision
index = (5*index+1+h) % self.capacity
h = h >> 5

Die vorgestellte Implementierung orientiert sich an Pythons interner Dictionary Implementierung, der zugehörige Quelltext mit ausführlichem Kommentar) findet sich unter [http://svn.python.org/view/*checkout*/python/trunk/Objects/dictobject.c dictobject.c Python Implementation (SVN)]

===== Komplexität des offenen Hashings =====

* Annahme: uniformes Hashing, das heißt alle Indizes haben gleiche Wahrscheinlichkeit
* Füllstand <math>\alpha = \frac{\text{size}}{\text{capacity}}</math>

* '''Erfolglose Suche''' (d.h. es wird entweder ein neues Element eingefügt oder ein <tt>keyError</tt> geworfen): Untere Schranke für die Komplexität ist <math>\Omega\left(\frac{1}{1-\alpha}\right)</math> Schritte bzw. Anzahl von neuen index Berechnungen.
* '''Erfolgreiche Suche''' <math>\Omega\left(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\right)</math>

{| border="1" cellspacing="0" cellpadding="5" align="center"
! <math>\alpha</math>
! 0.5
! 0.9
|-
| erfolglos
| 2.0
| 10
|-
| erfolgreich
| 1.4
| 2.6
|}

===== Wahl der Kapazität =====
In Python wird <tt>capacity</tt> Aufgrund der obigen Beobachtung so gewählt, dass <math>\alpha \leq 2/3</math>. Falls <math>\alpha</math> größer werden sollte, verdopple die Kapazität und kopiere das alte array in das neue Array (analog zum dynamischen Array)

In Python werden die Kapazitätsgrößen als Zweierpotenzen gewählt, also 4,8,16,32,...,
so dass <tt>h % self.capacity</tt> nur die unteren Bits von <tt>h</tt> benutzt.

== Anwendung von Hashing ==

* Hashtabelle, assoziatives Aray
* Sortieren in linearer Zeit (Übungsaufgabe 6.2)
* Suchen von Strings in Texten
* ...

=== Rabin Karp Algorithmus ===
In Textverarbeitungsanwendungen ist eine häufig benutzte Funktion die ''Search & Replace'' Funktionalität. Die Suche sollte in O(len(text)) möglich sein, aber ein naiver Algorithmus braucht O(len(text)*len(searchstring))

==== Naive Implementierung der Suche ====
def search(text, s):
M, N = len(text), len(s)
for k in range(M-N):
if s==text[k:k+N]
return k
return -1 #nicht gefunden

==== Idee des Rabin Karp Algorithmus ====
Statt Vergleichen <tt>s==text[k:k+N], die O(N) benötigen da N Vergleiche der Buchstaben durchgeführt werden müssen, Vergleiche die Hashs von Suchstring und dem zu untersuchenden Textabschnitt: <tt>hash(s) == hash(text[k:k+N])</tt>. Dabei muss natürlich <tt>hash(s)</tt> nur einmal berechnet werden, wohingegen <tt>hash(text[k:k+N])</tt> immer wieder neu berechnet werden muss. Damit der Vergleich O(1) sein kann, ist es deswegen erforderlich, eine solche Hashfunktion zu haben, die nicht alle Zeichen (das wäre O(N) ) einlesen muss, sondern die vorhergehende Hashfunktion mit einbezieht.

Eine solche Hashfunktion heißt ''Running Hash'' und funktioniert analog zum ''Sliding Mean''.

Die Running Hash Funktion berechnet in O(1) den hash von <tt>text[k+1:k+1+N]</tt> ausgehend vom hash für <tt>text[k:k+N]</tt>.

Idee: Interpretiere den Text als Ziffern in einer base d Darstellung:

<math>h_k = \text{text}[k]\cdot d^{N-1} + \text{text}[k]\cdot d^{N-2} + \cdots + \text{text}[k+N-1]</math>

Für die Basis 10 (Dezimalsystem) ergibt sich also

<math>h_k = \text{text}[k]\cdot {10}^{N-1} + \text{text}[k]\cdot {10}^{N-2} + \cdots + \text{text}[k+N-1]</math>
Daraus folgt
<math>h_{k+1} = 10\cdot h_k - \text{text}[k]\cdot {10}^{N} + \text{text}[k+N]</math>
Und die Komplexität ist O(1).

In der Realität wählt man dann d=32 und benutzt noch an einigen Stellen modulo Operationen, um die Zahlen nicht zu groß werden zu lassen.

==== Implementation ====
def searchRabinKarp(text, s):
ht, hs, dN = 0, 0, 1
M, N = len(text), len(s)
d, q = 32, <sehr große Primzahl>

#Initialisierung
for k in range(N):
ht = ht*d + ord(text[k]) % q
#ord() gibt die ASCIInummer des übergebenen Zeichens zurück
ds = hs*d + ord( s[k] )
dN = (dN*a) % q
#Die Variable sind jetzt wie folgt initialisiert:
#ht = hash(text[0:N])
#hs = hash(s)
#dN = (d**N) % q

k = 0
while k < M-N:
if hs == ht and s==text[k:k+N]:
return k
ht = (d*ht - dN * ord(text[k]) + dN*q + ord(text[k+M]) ) % q
k +=1
return -1

#Hauptschleife

Iteration versus Rekursion

2008-06-04T17:07:26Z

Thorben: /* Idee des Rabin Karp Algorithmus */

== Hashtabelle mit linearer Verkettung ==
Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem
Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

===Implementation in Python===
''HashNode'' ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert
und mit hilfe von ''next'' eine verkettete Liste darstellt
class HashNode:
def __init__(self,key,data,next):
self.key = key
self.data = data
self.next = next #Verkettung!

Die eigentliche Hashtabelle wir in der Klasse ''HashTable'' implementier:
class HashTable:
def __init__(self):
self.capacity = ... #Geigneter Wert
self.size = 0
self.array = [None]*self.capacity

In Python wird der Zugriffsoperator ''[ ]'' für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:
def __setitem__(self, key, value)

So dass im Programmtext dann folgender Syntax möglich ist: <tt>a[key] = value</tt>

Genauso wir die Zuweisung <tt>value=a[key]</tt> wie folgt umgesetzt
def __getitem__(self, key, value)

Implementierung der <tt>__setitem__</tt> Funktionen in der <tt>HashTable</tt> Klasse:
def __setitme__(self, key, value):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key:
#Element key ist schon in der Tabelle
#Überschreibe die Daten mit dem neuen Wert
node.data = value
return
#Kollision des Hashwerts, probiere nächsten Key aus
node = node.next
#Kein Element hatte den richtigen Schlüssel.
#==>Es gibt diesen Schlüssel noch nicht
#Füge also ein neues Element in die Hashtabelle ein

self.array[index] = HashNode(key, value, self.array[index])
#Der alte Anfang der List wurde der Nachfolger vom neue eingefügten
#ersten Element

size+=1

Und die Implementierung der <tt>__getitem__</tt> Funktionen:
def __getItem__(self, key):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key #Gefunden!
return Node.data
node = node.next
raise KeyError(key)

==== Wahl der Kapazität ====
In der C++ Standardbibliothek wird typischerweise ein Hash mit Hilfe der linearen Kette
imlementiert. Dabei wird <tt>capcity</tt> immer als ''Primzahl'' gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:
53, 97, 193, 398, 769, ...

Das hat zur Folge, dass <tt>h % self.capacity</tt> ''alle'' Bits von h benutzt (Eigenschaft aus der Zahlentheorie)

== Hashtabelle mit offener Adressierung (offenes Hashing) ==
Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

=== Idee ===
Wenn <tt>array[index]</tt> durch Kollision bereits vergeben ist, probiere einen
anderen Index aus.

* Das Array enthält pro Element höchstens ein (key,value)-Paar
* Das Array muss stets mindestens ''einen'' freien Platz haben (sonst gäbe es eine Endlosschleife). Es gilt immer <tt>self.size < self.capacity</tt>. Dies galt für die vorige Hash Implementation nicht.

=== Vorgehen bei Kollisionen ===

==== Sequentielles Suchen ====
Probiere den nächsten Index: <tt>index = index+1 % capacity</tt>

* Vorteil: einfach
* Nachteil: Clusterbildung

Clusterbildung heißt, dass sich größere zusammenhängende Bereiche bilden die belegt sind, unterbrochen von Bereichen die komplett frei sind. Beim Versuche des Einfügens eines Elements an einen Platz, der schon belegt ist, muss jetzt das ganze Cluster sequentiell durchlaufen werden, bis ein freier Platz gefunden wird. Damit entspricht die Komplexität der Suche der mittleren Länge der belegten Bereiche, was sich entsprechend in einer langsamen Suche widerspiegelt.

==== Doppeltes Hashing ====
Bestimme einen neuen Index (bei Kollisionen) durch eine ''2. Hashfunktion''.

Das doppelte Hashing wird typischerweise in der Praxis angewendet und liegt auch der Python Implementierung des Datentyps ''Dictionary'' (Syntax <tt>{'a':1, 'b':2, 'c':3}</tt> zugrunde.

Eine effiziente Implementierung dieses Datentyps ist für die Performance der Skriptsprache Python extrem wichtig, da z.B. beim Aufruf einer Funktion der auszuführunde Code in einem Dictionary unter dem Schlüssel ''Funktionsname'' nachgeschlagen wird oder die Werte lokaler Variablen innerhalb einer Funktion ebenfalls in einem Dictionary zu finden sind.

Für die Implementierung in Python werden wieder die obigen Klassen <tt>HashNode</tt> und <tt>HashTable</tt> benötigt, es folgen die angepassten Implementationen von <tt>__setitem</tt> und <tt>__getitem__</tt>:

def __setitem__(self, key, value):
h = hash(key)
index = h % self.capacity
while True:
if self.array[index] is None or self.array[index].key is None
#das Feld ist frei (1. Abfrage)
#oder das feld ist als frei markiert (2. Abfrage)
self.array[index] = HashNode(key, value)
self.size +=1
return
if self.array[index].key == key:
#Es gibt diesen Schlüssel schon,
#überschreibe die Daten
self.array[index].data = value
#Letzter Fall: Kollision
index = (5*index+1+h) % self.capacity
h = h >> 5

Die vorgestellte Implementierung orientiert sich an Pythons interner Dictionary Implementierung, der zugehörige Quelltext mit ausführlichem Kommentar) findet sich unter [http://svn.python.org/view/*checkout*/python/trunk/Objects/dictobject.c dictobject.c Python Implementation (SVN)]

===== Komplexität des offenen Hashings =====

* Annahme: uniformes Hashing, das heißt alle Indizes haben gleiche Wahrscheinlichkeit
* Füllstand <math>\alpha = \frac{\text{size}}{\text{capacity}}</math>

* '''Erfolglose Suche''' (d.h. es wird entweder ein neues Element eingefügt oder ein <tt>keyError</tt> geworfen): Untere Schranke für die Komplexität ist <math>\Omega\left(\frac{1}{1-\alpha}\right)</math> Schritte bzw. Anzahl von neuen index Berechnungen.
* '''Erfolgreiche Suche''' <math>\Omega\left(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\right)</math>

{| border="1" cellspacing="0" cellpadding="5" align="center"
! <math>\alpha</math>
! 0.5
! 0.9
|-
| erfolglos
| 2.0
| 10
|-
| erfolgreich
| 1.4
| 2.6
|}

===== Wahl der Kapazität =====
In Python wird <tt>capacity</tt> Aufgrund der obigen Beobachtung so gewählt, dass <math>\alpha \leq 2/3</math>. Falls <math>\alpha</math> größer werden sollte, verdopple die Kapazität und kopiere das alte array in das neue Array (analog zum dynamischen Array)

In Python werden die Kapazitätsgrößen als Zweierpotenzen gewählt, also 4,8,16,32,...,
so dass <tt>h % self.capacity</tt> nur die unteren Bits von <tt>h</tt> benutzt.

== Anwendung von Hashing ==

* Hashtabelle, assoziatives Aray
* Sortieren in linearer Zeit (Übungsaufgabe 6.2)
* Suchen von Strings in Texten
* ...

=== Rabin Karp Algorithmus ===
In Textverarbeitungsanwendungen ist eine häufig benutzte Funktion die ''Search & Replace'' Funktionalität. Die Suche sollte in O(len(text)) möglich sein, aber ein naiver Algorithmus braucht O(len(text)*len(searchstring))

==== Naive Implementierung der Suche ====
def search(text, s):
M, N = len(text), len(s)
for k in range(M-N):
if s==text[k:k+N]
return k
return -1 #nicht gefunden

==== Idee des Rabin Karp Algorithmus ====
Statt Vergleichen <tt>s==text[k:k+N], die O(N) benötigen da N Vergleiche der Buchstaben durchgeführt werden müssen, Vergleiche die Hashs von Suchstring und dem zu untersuchenden Textabschnitt: <tt>hash(s) == hash(text[k:k+N])</tt>. Dabei muss natürlich <tt>hash(s)</tt> nur einmal berechnet werden, wohingegen <tt>hash(text[k:k+N])</tt> immer wieder neu berechnet werden muss. Damit der Vergleich O(1) sein kann, ist es deswegen erforderlich, eine solche Hashfunktion zu haben, die nicht alle Zeichen (das wäre O(N) ) einlesen muss, sondern die vorhergehende Hashfunktion mit einbezieht.

Eine solche Hashfunktion heißt ''Running Hash'' und funktioniert analog zum ''Sliding Mean''.

Die Running Hash Funktion berechnet in O(1) den hash von <tt>text[k+1:k+1+N]</tt> ausgehend vom hash für <tt>text[k:k+N]</tt>.

Idee: Interpretiere den Text als Ziffern in einer base d Darstellung:

<math>h_k = \text{text}[k]\cdot d^{N-1} + \text{text}[k]\cdot d^{N-2} + \cdots + \text{text}[k+N-1]</math>

Für die Basis 10 (Dezimalsystem) ergibt sich also

<math>h_k = \text{text}[k]\cdot {10}^{N-1} + \text{text}[k]\cdot {10}^{N-2} + \cdots + \text{text}[k+N-1]</math>
Daraus folgt
<math>h_{k+1} = 10\cdot h_k - \text{text}[k]\cdot {10}^{N} + \text{text}[k+N]</math>
Und die Komplexität ist O(1).

In der Realität wählt man dann d=32 und benutzt noch an einigen Stellen modulo Operationen, um die Zahlen nicht zu groß werden zu lassen.

==== Implementation ====
def searchRabinKarp(text, s):
ht, hs, dN = 0, 0, 1
M, N = len(text), len(s)
d, q = 32, <sehr große Primzahl>

#Initialisierung
for k in range(N):
ht = ht*d + ord(text[k]) % q
#ord() gibt die ASCIInummer des übergebenen Zeichens zurück
ds = hs*d + ord( s[k] )
dN = (dN*a) % q
#Die Variable sind jetzt wie folgt initialisiert:
#ht = hash(text[0:N])
#hs = hash(s)
#dN = (d**N) % q

k = 0
while k < M-N:
if hs == ht and s==text[k:k+N]:
return k
ht = (d*ht - dN * ord(text[k]) + dN*q + ord(text[k+M]) ) % q
k +=1
return -1

#Hauptschleife

Iteration versus Rekursion

2008-06-04T17:07:06Z

Thorben: /* Rabin Karp Algorithmus */

== Hashtabelle mit linearer Verkettung ==
Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem
Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

===Implementation in Python===
''HashNode'' ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert
und mit hilfe von ''next'' eine verkettete Liste darstellt
class HashNode:
def __init__(self,key,data,next):
self.key = key
self.data = data
self.next = next #Verkettung!

Die eigentliche Hashtabelle wir in der Klasse ''HashTable'' implementier:
class HashTable:
def __init__(self):
self.capacity = ... #Geigneter Wert
self.size = 0
self.array = [None]*self.capacity

In Python wird der Zugriffsoperator ''[ ]'' für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:
def __setitem__(self, key, value)

So dass im Programmtext dann folgender Syntax möglich ist: <tt>a[key] = value</tt>

Genauso wir die Zuweisung <tt>value=a[key]</tt> wie folgt umgesetzt
def __getitem__(self, key, value)

Implementierung der <tt>__setitem__</tt> Funktionen in der <tt>HashTable</tt> Klasse:
def __setitme__(self, key, value):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key:
#Element key ist schon in der Tabelle
#Überschreibe die Daten mit dem neuen Wert
node.data = value
return
#Kollision des Hashwerts, probiere nächsten Key aus
node = node.next
#Kein Element hatte den richtigen Schlüssel.
#==>Es gibt diesen Schlüssel noch nicht
#Füge also ein neues Element in die Hashtabelle ein

self.array[index] = HashNode(key, value, self.array[index])
#Der alte Anfang der List wurde der Nachfolger vom neue eingefügten
#ersten Element

size+=1

Und die Implementierung der <tt>__getitem__</tt> Funktionen:
def __getItem__(self, key):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key #Gefunden!
return Node.data
node = node.next
raise KeyError(key)

==== Wahl der Kapazität ====
In der C++ Standardbibliothek wird typischerweise ein Hash mit Hilfe der linearen Kette
imlementiert. Dabei wird <tt>capcity</tt> immer als ''Primzahl'' gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:
53, 97, 193, 398, 769, ...

Das hat zur Folge, dass <tt>h % self.capacity</tt> ''alle'' Bits von h benutzt (Eigenschaft aus der Zahlentheorie)

== Hashtabelle mit offener Adressierung (offenes Hashing) ==
Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

=== Idee ===
Wenn <tt>array[index]</tt> durch Kollision bereits vergeben ist, probiere einen
anderen Index aus.

* Das Array enthält pro Element höchstens ein (key,value)-Paar
* Das Array muss stets mindestens ''einen'' freien Platz haben (sonst gäbe es eine Endlosschleife). Es gilt immer <tt>self.size < self.capacity</tt>. Dies galt für die vorige Hash Implementation nicht.

=== Vorgehen bei Kollisionen ===

==== Sequentielles Suchen ====
Probiere den nächsten Index: <tt>index = index+1 % capacity</tt>

* Vorteil: einfach
* Nachteil: Clusterbildung

Clusterbildung heißt, dass sich größere zusammenhängende Bereiche bilden die belegt sind, unterbrochen von Bereichen die komplett frei sind. Beim Versuche des Einfügens eines Elements an einen Platz, der schon belegt ist, muss jetzt das ganze Cluster sequentiell durchlaufen werden, bis ein freier Platz gefunden wird. Damit entspricht die Komplexität der Suche der mittleren Länge der belegten Bereiche, was sich entsprechend in einer langsamen Suche widerspiegelt.

==== Doppeltes Hashing ====
Bestimme einen neuen Index (bei Kollisionen) durch eine ''2. Hashfunktion''.

Das doppelte Hashing wird typischerweise in der Praxis angewendet und liegt auch der Python Implementierung des Datentyps ''Dictionary'' (Syntax <tt>{'a':1, 'b':2, 'c':3}</tt> zugrunde.

Eine effiziente Implementierung dieses Datentyps ist für die Performance der Skriptsprache Python extrem wichtig, da z.B. beim Aufruf einer Funktion der auszuführunde Code in einem Dictionary unter dem Schlüssel ''Funktionsname'' nachgeschlagen wird oder die Werte lokaler Variablen innerhalb einer Funktion ebenfalls in einem Dictionary zu finden sind.

Für die Implementierung in Python werden wieder die obigen Klassen <tt>HashNode</tt> und <tt>HashTable</tt> benötigt, es folgen die angepassten Implementationen von <tt>__setitem</tt> und <tt>__getitem__</tt>:

def __setitem__(self, key, value):
h = hash(key)
index = h % self.capacity
while True:
if self.array[index] is None or self.array[index].key is None
#das Feld ist frei (1. Abfrage)
#oder das feld ist als frei markiert (2. Abfrage)
self.array[index] = HashNode(key, value)
self.size +=1
return
if self.array[index].key == key:
#Es gibt diesen Schlüssel schon,
#überschreibe die Daten
self.array[index].data = value
#Letzter Fall: Kollision
index = (5*index+1+h) % self.capacity
h = h >> 5

Die vorgestellte Implementierung orientiert sich an Pythons interner Dictionary Implementierung, der zugehörige Quelltext mit ausführlichem Kommentar) findet sich unter [http://svn.python.org/view/*checkout*/python/trunk/Objects/dictobject.c dictobject.c Python Implementation (SVN)]

===== Komplexität des offenen Hashings =====

* Annahme: uniformes Hashing, das heißt alle Indizes haben gleiche Wahrscheinlichkeit
* Füllstand <math>\alpha = \frac{\text{size}}{\text{capacity}}</math>

* '''Erfolglose Suche''' (d.h. es wird entweder ein neues Element eingefügt oder ein <tt>keyError</tt> geworfen): Untere Schranke für die Komplexität ist <math>\Omega\left(\frac{1}{1-\alpha}\right)</math> Schritte bzw. Anzahl von neuen index Berechnungen.
* '''Erfolgreiche Suche''' <math>\Omega\left(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\right)</math>

{| border="1" cellspacing="0" cellpadding="5" align="center"
! <math>\alpha</math>
! 0.5
! 0.9
|-
| erfolglos
| 2.0
| 10
|-
| erfolgreich
| 1.4
| 2.6
|}

===== Wahl der Kapazität =====
In Python wird <tt>capacity</tt> Aufgrund der obigen Beobachtung so gewählt, dass <math>\alpha \leq 2/3</math>. Falls <math>\alpha</math> größer werden sollte, verdopple die Kapazität und kopiere das alte array in das neue Array (analog zum dynamischen Array)

In Python werden die Kapazitätsgrößen als Zweierpotenzen gewählt, also 4,8,16,32,...,
so dass <tt>h % self.capacity</tt> nur die unteren Bits von <tt>h</tt> benutzt.

== Anwendung von Hashing ==

* Hashtabelle, assoziatives Aray
* Sortieren in linearer Zeit (Übungsaufgabe 6.2)
* Suchen von Strings in Texten
* ...

=== Rabin Karp Algorithmus ===
In Textverarbeitungsanwendungen ist eine häufig benutzte Funktion die ''Search & Replace'' Funktionalität. Die Suche sollte in O(len(text)) möglich sein, aber ein naiver Algorithmus braucht O(len(text)*len(searchstring))

==== Naive Implementierung der Suche ====
def search(text, s):
M, N = len(text), len(s)
for k in range(M-N):
if s==text[k:k+N]
return k
return -1 #nicht gefunden

==== Idee des Rabin Karp Algorithmus ====
Statt Vergleichen <tt>s==text[k:k+N], die O(N) benötigen da N Vergleiche der Buchstaben durchgeführt werden müssen, Vergleiche die Hashs von Suchstring und dem zu untersuchenden Textabschnitt: <tt>hash(s) == hash(text[k:k+N])</tt>. Dabei muss natürlich <tt>hash(s)</tt> nur einmal berechnet werden, wohingegen <tt>hash(text[k:k+N])</tt> immer wieder neu berechnet werden muss. Damit der Vergleich O(1) sein kann, ist es deswegen erforderlich, eine solche Hashfunktion zu haben, die nicht alle Zeichen (das wäre O(N) ) einlesen muss, sondern die vorhergehende Hashfunktion mit einbezieht.

Eine solche Hashfunktion heißt ''Running Hash'' und funktioniert analog zum ''Sliding Mean''.

Die Running Hash Funktion berechnet in O(1) den hash von <tt>text[k+1:k+1+N]</tt> ausgehend vom hash für <tt>text[k:k+N]</tt>.

Idee: Interpretiere den Text als Ziffern in einer base d Darstellung:

<math>h_k = \text{text}[k]\cdot d^{N-1} + \text{text}[k]\cdot d^{N-2} + \cdots + \text{text}[k+N-1]</math>

Für die Basis 10 (Dezimalsystem) ergibt sich also

<math>h_k = \text{text}[k]\cdot {10}^{N-1} + \text{text}[k]\cdot {10}^{N-2} + \cdots + \text{text}[k+N-1]</math>
Daraus folgt
<math>h_{k+1} = 10\cdot h_k - \text{text}[k]\cdot {10}^{N} + \text{text}[k+N]</math>
Und die Komplexität ist O(1).

In der Realität wählt man dann d=32 und benutzt noch an einigen Stellen modulo Operationen, um die Zahlen nicht zu groß werden zu lassen.

==== Implementation ====+
def searchRabinKarp(text, s):
ht, hs, dN = 0, 0, 1
M, N = len(text), len(s)
d, q = 32, <sehr große Primzahl>

#Initialisierung
for k in range(N):
ht = ht*d + ord(text[k]) % q
#ord() gibt die ASCIInummer des übergebenen Zeichens zurück
ds = hs*d + ord( s[k] )
dN = (dN*a) % q
#Die Variable sind jetzt wie folgt initialisiert:
#ht = hash(text[0:N])
#hs = hash(s)
#dN = (d**N) % q

k = 0
while k < M-N:
if hs == ht and s==text[k:k+N]:
return k
ht = (d*ht - dN * ord(text[k]) + dN*q + ord(text[k+M]) ) % q
k +=1
return -1

#Hauptschleife

Iteration versus Rekursion

2008-06-04T16:51:24Z

Thorben:

Iteration versus Rekursion

2008-06-04T16:39:23Z

Thorben: /* Wahl der Kapazität */

Iteration versus Rekursion

2008-06-04T16:38:54Z

Thorben: /* Wahl der Kapazität */

== Hashtabelle mit linearer Verkettung ==
Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem
Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

===Implementation in Python===
''HashNode'' ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert
und mit hilfe von ''next'' eine verkettete Liste darstellt
class HashNode:
def __init__(self,key,data,next):
self.key = key
self.data = data
self.next = next #Verkettung!

Die eigentliche Hashtabelle wir in der Klasse ''HashTable'' implementier:
class HashTable:
def __init__(self):
self.capacity = ... #Geigneter Wert
self.size = 0
self.array = [None]*self.capacity

In Python wird der Zugriffsoperator ''[ ]'' für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:
def __setitem__(self, key, value)

So dass im Programmtext dann folgender Syntax möglich ist: <tt>a[key] = value</tt>

Genauso wir die Zuweisung <tt>value=a[key]</tt> wie folgt umgesetzt
def __getitem__(self, key, value)

Implementierung der <tt>__setitem__</tt> Funktionen in der <tt>HashTable</tt> Klasse:
def __setitme__(self, key, value):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key:
#Element key ist schon in der Tabelle
#Überschreibe die Daten mit dem neuen Wert
node.data = value
return
#Kollision des Hashwerts, probiere nächsten Key aus
node = node.next
#Kein Element hatte den richtigen Schlüssel.
#==>Es gibt diesen Schlüssel noch nicht
#Füge also ein neues Element in die Hashtabelle ein

self.array[index] = HashNode(key, value, self.array[index])
#Der alte Anfang der List wurde der Nachfolger vom neue eingefügten
#ersten Element

size+=1

Und die Implementierung der <tt>__getitem__</tt> Funktionen:
def __getItem__(self, key):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key #Gefunden!
return Node.data
node = node.next
raise KeyError(key)

==== Wahl der Kapazität ====
In der C++ Standardbibliothek wird typischerweise ein Hash mit Hilfe der linearen Kette
imlementiert. Dabei wird <tt>capcity</tt> immer als ''Primzahl'' gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:
53, 97, 193, 398, 769, ...

Das hat zur Folge, dass <tt>h % self.capacity</tt> ''alle'' Bits von h benutzt (Eigenschaft aus der Zahlentheorie)

== Hashtabelle mit offener Adressierung (offenes Hashing) ==
Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

=== Idee ===
Wenn <tt>array[index]</tt> durch Kollision bereits vergeben ist, probiere einen
anderen Index aus.

* Das Array enthält pro Element höchstens ein (key,value)-Paar
* Das Array muss stets mindestens ''einen'' freien Platz haben (sonst gäbe es eine Endlosschleife). Es gilt immer <tt>self.size < self.capacity</tt>. Dies galt für die vorige Hash Implementation nicht.

=== Vorgehen bei Kollisionen ===

==== Sequentielles Suchen ====
Probiere den nächsten Index: <tt>index = index+1 % capacity</tt>

* Vorteil: einfach
* Nachteil: Clusterbildung

Clusterbildung heißt, dass sich größere zusammenhängende Bereiche bilden die belegt sind, unterbrochen von Bereichen die komplett frei sind. Beim Versuche des Einfügens eines Elements an einen Platz, der schon belegt ist, muss jetzt das ganze Cluster sequentiell durchlaufen werden, bis ein freier Platz gefunden wird. Damit entspricht die Komplexität der Suche der mittleren Länge der belegten Bereiche, was sich entsprechend in einer langsamen Suche widerspiegelt.

==== Doppeltes Hashing ====
Bestimme einen neuen Index (bei Kollisionen) durch eine ''2. Hashfunktion''.

Das doppelte Hashing wird typischerweise in der Praxis angewendet und liegt auch der Python Implementierung des Datentyps ''Dictionary'' (Syntax <tt>{'a':1, 'b':2, 'c':3}</tt> zugrunde.

Eine effiziente Implementierung dieses Datentyps ist für die Performance der Skriptsprache Python extrem wichtig, da z.B. beim Aufruf einer Funktion der auszuführunde Code in einem Dictionary unter dem Schlüssel ''Funktionsname'' nachgeschlagen wird oder die Werte lokaler Variablen innerhalb einer Funktion ebenfalls in einem Dictionary zu finden sind.

Für die Implementierung in Python werden wieder die obigen Klassen <tt>HashNode</tt> und <tt>HashTable</tt> benötigt, es folgen die angepassten Implementationen von <tt>__setitem</tt> und <tt>__getitem__</tt>:

def __setitem__(self, key, value):
h = hash(key)
index = h % self.capacity
while True:
if self.array[index] is None or self.array[index].key is None
#das Feld ist frei (1. Abfrage)
#oder das feld ist als frei markiert (2. Abfrage)
self.array[index] = HashNode(key, value)
self.size +=1
return
if self.array[index].key == key:
#Es gibt diesen Schlüssel schon,
#überschreibe die Daten
self.array[index].data = value
#Letzter Fall: Kollision
index = (5*index+1+h) % self.capacity
h = h >> 5

Die vorgestellte Implementierung orientiert sich an Pythons interner Dictionary Implementierung, der zugehörige Quelltext mit ausführlichem Kommentar) findet sich unter [http://svn.python.org/view/*checkout*/python/trunk/Objects/dictobject.c dictobject.c Python Implementation (SVN)]

===== Komplexität des offenen Hashings =====

* Annahme: uniformes Hashing, das heißt alle Indizes haben gleiche Wahrscheinlichkeit
* Füllstand <math>\alpha = \frac{\text{size}}{\text{capacity}}</math>

* '''Erfolglose Suche''' (d.h. es wird entweder ein neues Element eingefügt oder ein <tt>keyError</tt> geworfen): Untere Schranke für die Komplexität ist <math>\Omega\left(\frac{1}{1-\alpha}\right)</math> Schritte bzw. Anzahl von neuen index Berechnungen.
* '''Erfolgreiche Suche''' <math>\Omega\left(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\right)</math>

{| border="1" cellspacing="0" cellpadding="5" align="center"
! <math>\alpha</math>
! 0.5
! 0.9
|-
| erfolglos
| 2.0
| 10
|-
| erfolgreich
| 1.4
| 2.6
|}

===== Wahl der Kapazität =====
In Python wird <tt>capacity</tt> Aufgrund der obigen Beobachtung so gewählt, dass <math>\alpha \lq 2/3</math>. Falls <math>\alpha</math> größer werden sollte, verdopple die Kapazität und kopiere das alte array in das neue Array (analog zum dynamischen Array)

In Python werden die Kapazitätsgrößen als Zweierpotenzen gewählt, also 4,8,16,32,...,
so dass <tt>h % self.capacity</tt> nur die unteren Bits von <tt>h</tt> benutzt.

Iteration versus Rekursion

2008-06-04T16:38:11Z

Thorben: /* Hashtabelle mit linearer Verkettung */

== Hashtabelle mit linearer Verkettung ==
Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem
Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

===Implementation in Python===
''HashNode'' ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert
und mit hilfe von ''next'' eine verkettete Liste darstellt
class HashNode:
def __init__(self,key,data,next):
self.key = key
self.data = data
self.next = next #Verkettung!

Die eigentliche Hashtabelle wir in der Klasse ''HashTable'' implementier:
class HashTable:
def __init__(self):
self.capacity = ... #Geigneter Wert
self.size = 0
self.array = [None]*self.capacity

In Python wird der Zugriffsoperator ''[ ]'' für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:
def __setitem__(self, key, value)

So dass im Programmtext dann folgender Syntax möglich ist: <tt>a[key] = value</tt>

Genauso wir die Zuweisung <tt>value=a[key]</tt> wie folgt umgesetzt
def __getitem__(self, key, value)

Implementierung der <tt>__setitem__</tt> Funktionen in der <tt>HashTable</tt> Klasse:
def __setitme__(self, key, value):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key:
#Element key ist schon in der Tabelle
#Überschreibe die Daten mit dem neuen Wert
node.data = value
return
#Kollision des Hashwerts, probiere nächsten Key aus
node = node.next
#Kein Element hatte den richtigen Schlüssel.
#==>Es gibt diesen Schlüssel noch nicht
#Füge also ein neues Element in die Hashtabelle ein

self.array[index] = HashNode(key, value, self.array[index])
#Der alte Anfang der List wurde der Nachfolger vom neue eingefügten
#ersten Element

size+=1

Und die Implementierung der <tt>__getitem__</tt> Funktionen:
def __getItem__(self, key):
index = hash(key) % self.capacity
node = self.array[index]
while node is not None:
if node.key == key #Gefunden!
return Node.data
node = node.next
raise KeyError(key)

==== Wahl der Kapazität ====
In der C++ Standardbibliothek wird typischerweise ein Hash mit Hilfe der linearen Kette
imlementiert. Dabei wird <tt>capcity</tt> immer als ''Primzahl'' gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:
53, 97, 193, 398, 769, ...

Das hat zur Folge, dass <tt>h % self.capacity</tt> ''alle'' Bits von h benutzt (Eigenschaft aus der Zahlentheorie)

== Hashtabelle mit offener Adressierung (offenes Hashing) ==
Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

=== Idee ===
Wenn <tt>array[index]</tt> durch Kollision bereits vergeben ist, probiere einen
anderen Index aus.

* Das Array enthält pro Element höchstens ein (key,value)-Paar
* Das Array muss stets mindestens ''einen'' freien Platz haben (sonst gäbe es eine Endlosschleife). Es gilt immer <tt>self.size < self.capacity</tt>. Dies galt für die vorige Hash Implementation nicht.

=== Vorgehen bei Kollisionen ===

==== Sequentielles Suchen ====
Probiere den nächsten Index: <tt>index = index+1 % capacity</tt>

* Vorteil: einfach
* Nachteil: Clusterbildung

Clusterbildung heißt, dass sich größere zusammenhängende Bereiche bilden die belegt sind, unterbrochen von Bereichen die komplett frei sind. Beim Versuche des Einfügens eines Elements an einen Platz, der schon belegt ist, muss jetzt das ganze Cluster sequentiell durchlaufen werden, bis ein freier Platz gefunden wird. Damit entspricht die Komplexität der Suche der mittleren Länge der belegten Bereiche, was sich entsprechend in einer langsamen Suche widerspiegelt.

==== Doppeltes Hashing ====
Bestimme einen neuen Index (bei Kollisionen) durch eine ''2. Hashfunktion''.

Das doppelte Hashing wird typischerweise in der Praxis angewendet und liegt auch der Python Implementierung des Datentyps ''Dictionary'' (Syntax <tt>{'a':1, 'b':2, 'c':3}</tt> zugrunde.

Eine effiziente Implementierung dieses Datentyps ist für die Performance der Skriptsprache Python extrem wichtig, da z.B. beim Aufruf einer Funktion der auszuführunde Code in einem Dictionary unter dem Schlüssel ''Funktionsname'' nachgeschlagen wird oder die Werte lokaler Variablen innerhalb einer Funktion ebenfalls in einem Dictionary zu finden sind.

Für die Implementierung in Python werden wieder die obigen Klassen <tt>HashNode</tt> und <tt>HashTable</tt> benötigt, es folgen die angepassten Implementationen von <tt>__setitem</tt> und <tt>__getitem__</tt>:

def __setitem__(self, key, value):
h = hash(key)
index = h % self.capacity
while True:
if self.array[index] is None or self.array[index].key is None
#das Feld ist frei (1. Abfrage)
#oder das feld ist als frei markiert (2. Abfrage)
self.array[index] = HashNode(key, value)
self.size +=1
return
if self.array[index].key == key:
#Es gibt diesen Schlüssel schon,
#überschreibe die Daten
self.array[index].data = value
#Letzter Fall: Kollision
index = (5*index+1+h) % self.capacity
h = h >> 5

Die vorgestellte Implementierung orientiert sich an Pythons interner Dictionary Implementierung, der zugehörige Quelltext mit ausführlichem Kommentar) findet sich unter [http://svn.python.org/view/*checkout*/python/trunk/Objects/dictobject.c dictobject.c Python Implementation (SVN)]

===== Komplexität des offenen Hashings =====

* Annahme: uniformes Hashing, das heißt alle Indizes haben gleiche Wahrscheinlichkeit
* Füllstand <math>\alpha = \frac{\text{size}}{\text{capacity}}</math>

* '''Erfolglose Suche''' (d.h. es wird entweder ein neues Element eingefügt oder ein <tt>keyError</tt> geworfen): Untere Schranke für die Komplexität ist <math>\Omega\left(\frac{1}{1-\alpha}\right)</math> Schritte bzw. Anzahl von neuen index Berechnungen.
* '''Erfolgreiche Suche''' <math>\Omega\left(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\right)</math>

{| border="1" cellspacing="0" cellpadding="5" align="center"
! <math>\alpha</math>
! 0.5
! 0.9
|-
| erfolglos
| 2.0
| 10
|-
| erfolgreich
| 1.4
| 2.6
|}

===== Wahl der Kapazität =====
In Python wird <tt>capacity</tt> Aufgrund der obigen Beobachtung so gewählt, dass <math>\alpha \lt 2/3</math>. Falls <math>\alpha</math> größer werden sollte, verdopple die Kapazität und kopiere das alte array in das neue Array (analog zum dynamischen Array)

In Python werden die Kapazitätsgrößen als Zweierpotenzen gewählt, also 4,8,16,32,...,
so dass <tt>h % self.capacity</tt> nur die unteren Bits von <tt>h</tt> benutzt.

Iteration versus Rekursion

2008-06-04T16:34:51Z

Thorben: /* Doppeltes Hashing */

Iteration versus Rekursion

2008-06-04T16:31:01Z

Thorben: /* Komplexität des offenen Hashings */

Iteration versus Rekursion

2008-06-04T16:27:24Z

Thorben: /* Doppeltes Hashing */

Iteration versus Rekursion

2008-06-04T16:21:05Z

Thorben: /* Doppeltes Hashing */

Iteration versus Rekursion

2008-06-04T16:15:32Z

Thorben: /* Hashtabelle mit offener Adressierung (offenes Hashing) */

Iteration versus Rekursion

2008-06-04T16:11:12Z

Thorben: /* Hashtabelle mit offener Adressierung (offenes Hashing) */

Iteration versus Rekursion

2008-06-04T16:01:20Z

Thorben:

Iteration versus Rekursion

2008-06-04T15:56:06Z

Thorben: /* Hashtabelle mit linearer Verkettung */

Iteration versus Rekursion

2008-06-04T15:54:36Z

Thorben: