[DSAL] Übungsblatt 6 - Doppeltes Hashing

[Commo]

Hi,

kann zufällig jemand die Ergebnisse für das doppelte Hashing vergleichen? Ich hab da was angestrichen bekommen, aber habe erstens fürs Hashing nen Skript benutzt und zweitens per Hand immernoch dasselbe raus. Weiß jetzt nicht, ob mein Tutor falsch korrigiert hat oder ich einen grundlegenden Fehler mache:

h1(x): 7,14,18,14,6,15,6,0,6,12,16,3,0,1,12,15,1,17,8
h2(x): 11,7,10,7,8,10,10,14,9,3,9,5,10,1,16,6,1,8,8
Doppelt: 7,14,18,2,6,15,16,0,5,12,4,3,10,1,9,8,11,17,13

Angestrichen wurde erstmalig die 16 beim doppelten.

Habe mir an der Stelle halt gedacht: h(82,0) = h1(82) = 6 ist schon vergeben. h(82,1) = h1(82) + h2(82) = 6+10 = 16 ist frei.

[Merlin Junior]

Moin Commo

die Quersumme von 52 (4. Wert) ist 7 und nicht 8, aber das hast du anscheiend im Hashing doch richtig gemacht^^

Ansonsten hab ich gerade unabhängig genau dein ergebnis rausbekommen und in meiner damaligen Lösung ist die 82 an stelle 16 als richtig korregiert

mfg
Merlin Junior

[Commo]

Hi,

danke fürs nachrechnen. Bei den Quersummen habe ich mich in der Spalte vertan, hab es jetzt korrigiert. Gut, dann weiß ich ja jetzt Bescheid.

[aRo]

hallo!

Ist es richtig, wenn ich sage, dass alle "Wörterbuchoperationen" wie Search, Insert, Delete beim Hashing grundsätzlich im Erwartungsfall in O(1) erledigt werden können?

Ich glaube beim offenen Hashing ist das bei allen drei O(1+a) wobei a der Belegungsfaktor ist.
Und beim geschlossenen Hashing? Wie ist das da genau? Meine auch irgendwo auf einer Folie gelesen zu haben "delete sei nicht praktikabel"? Was soll das denn heißen...?

[NeX]

Wie ist das da genau? Meine auch irgendwo auf einer Folie gelesen zu haben "delete sei nicht praktikabel"? Was soll das denn heißen...?

bei geschlossem Hashing gehst du ja wie folgt vor bei einer Kollision.

Du sondierst. z.B. mit linearem, quadratischem oder doppeltem Hashing

Wenn du dir also z.b. folgendes Situation vorstellst.

geschlossenes Hashing mit quadratischem Sondieren: m=6

Hashfunktion: Quersumme mod m


Einfügen von 12

Einfügen von 21

Einfügen von 30 (3+4=7 = 1)


erstes Problem) die Suche

Würdest du jetzt nach der 30 suchen wollen würdest du zuerst an Tabellenstelle 3 nachsehen und die 12 finden
Jetzt suchst du nach der 30 mit quadratischem Sondieren und findest zuerst die 21 und dann die 30 !

löschst du nun die 21.....



kommst du zum zweitem Problem)

Du suchst wieder die 30 und kommst zuerst zur 12 ....gehst weiter und der Tabellenplatz ist leer....somit denkst du das du aufhören kannst mit suchen .......

genau das ist das Problem ...man müsste nun die 21 nur als "gelöscht" markieren damit man dann da nicht aufhört zu suchen.....
anderum ergibt sich natürlich die Frage wann man aufhört mit suchen falls die Zahl gar nicht drin ist....

es ist also nicht praktikabel

[aRo]

hi und danke für deine Mühe!

Hm, gut, wenn die das mit nicht praktikabel meinen.

Im Prinzip müsste ich die Sequenz durchsuchen, bis ich einen freien Slot in der Sequenz finde (wo nix drin ist und der auch nicht makiert ist). Dann kann ich mir sicher sein, dass die Suche erfolglos war.

Aber in welche O-Klasse ist das nun einzuordnen?

[NeX]

Aber in welche O-Klasse ist das nun einzuordnen?

ich würde meinen in O(m) (wobei m Tabellengröße) da du im schlechtesten fall die komplette hashtabelle durchgehen musst

[aRo]

klingt logisch.
Dann wäre der Worst Case O(m), und der erwartete Fall ist aber weiterhin O(1) oder?

[Robert]

Also wir sind bei geschlossenem Hashing.. da würde ich sagen, dass es dann von dem Belegungsfaktor abhängt.
Es hängt von dem Erwartungswert für eine Kollision ab, also vom Belegungsfaktor a und der Tabellengröße m und davon, wie viele Sondierungsschritte ausgeführt werden müssen.

Eine obere Schranke für den Aufwand um ein Element zu suchen, ist der selbe, um ein weiteres Element einzufügen.
Denn die negative Anfrage bricht beim ersten freien Slot ab (wo das neue Element eingefügt werden würde), während eine positive immer früher abbricht.

Die mittleren Kosten für das Einfügen des (n+1)sten Elements bei einer Tabellengröße m ist etwa

Siehe: Folien 941-946

Bei Belegungsfaktor a = n/m:



Für die Suche bildet man dann den Mittelwert über alle möglichen Einfüge-Reihenfolgen, weil die Suche davon abhängig ist, wie viele Kollisionen aufgetreten sind und an wie vielter Stelle das Element in der Sondierungskette liegt. S. Folie 951



Der erwartete Fall ist also nicht O(1) sondern abhängig vom Belegungsfaktor.

Ob es im Worst-Case wirklich nur O(m) ist, mag ich auch bezweifeln.
Denn es ist abhängig von der Sondierungsmethode.
Es kann ja durchaus sein, dass das i beim Sondieren größer als m wird.
Es ist ja nicht sicher, dass in einer Sondierungssequenz jeder Tabellenplatz nur genau einmal betrachtet wird. Schaut man sich z.B. die Übung A6.1.1b) an und schaut mal wie aufwändig es ist, die 8 tatsächlich einzufügen, so wird man sehen, dass die Berechnung dafür ganz schön aufwendig, wenn nicht unmöglich ist (mein PC schaffts nicht )

Für offenes Hashing ist der Worst Case O(m), falls alle Elemente in einem Eintrag landen, hat die Liste natürlich eine Länge von m und diese muss man maximal bis zum Ende durchsuchen.

[Commo]

Zur zusätzlichen Information: Wir haben auch gesagt, dass die Sondierungssequenzen üblicherweise länger sind als Listen beim offenen Hashing. Es kommt halt nur darauf an, ob du den Speicherplatz hast, denn beim offenen Hashing wächst die Tabelle dadurch dynamisch an.