Fachrat Informatik - Forum

hallo,

ich habe das so verstanden:

die zweite funktion bestimmt die schrittweite. double hashing ist also nur eine variante des linaren hashings, bei dem du bei einer kollision nicht einen schritt weiter gehst, sondern soviel schritte, wie dir die zweite funktion angibt. wenn es also eine kollision gibt.

bsp: du willst ein element an platz 8 einordnen, dieses ist aber schon belegt, dann berechnest du den wert der zweiten fuktion dieser sei jetz mal 3. und dann gehtst du von platz 8 aus 3 schritte weiter.
wenn es dort wieder zu einer kollision kommt denn wieder 3 schritte weiter, bis du auf einen freien platz stößt.

bei mir sieht 1a dann so aus:
0...........................................................13
14 7 - 28 15 36 - 21 8 5 22 11 - 27

hoffe das stimmt so

cowhen

Quoted

von obiwan: einfach bei position 0 weitermachen? wohl ja...

genau.




nun hab ich auchnoch eine frage: wie berechne ich denn die mittleren zugriffszahlen? das durchschaue ich irgendwie noch nicht


thx

cowhen

Für die erfolgreiche Suche habe ich herausgefunden, dass man die Anzahl der Vergleiche durch die Anzahl der Elemente dividieren muss. Also, wenn man eine Tabelle erstellt, dann daneben am besten noch einen Strich für den Tabellenzugriff machen, dann alle Striche aufaddieren und hier durch 11 teilen. Dann habe ich bei Aufgabe 1a 21 Tabellenzugriffe(vergleiche), durch 11 dividieren, erhält man 1,90909.... für die erfolgreiche Suche.
Wie man aber die nicht erfolgreiche Suche berechnet, weiß ich auch nicht.
mfg
MAX

error

...und schaue, aber kann nichts finden!!! Wir haben hier nicht mit Wahrscheinlichkeiten zu tun! Ich finde im Skript keine geeignete Formel dazu.
Aber durch Ausprobieren kam ich auf folgendes:
Nicht erfolgreiche Suche:=(h1(M-1)+M*h2(M-1)+Anzahl der Elemente)/Anzahl der Elemente
Ich kam dabei auf 3,454545....
Kann das jemand bestätigen/widerlegen???
mfg
MAX

die genaue zahl lässt sich nur berechnen, indem man jede mögliche nicht erfolgreiche suche ausprobiert, also im wesentlichen ab jedem (besetzten) tabellenplatz jede mögliche zweite hashfunktion (also schrittweiten von 2 bis 13) durchprobiert, bis man periodisch wieder am ausgangsplatz ankommt. das ganze mitgezählt und alles aufsummiert ergibt den entsprechenden aufwand. lässt sich wahrscheinlich am ehesten durch ein kleines programm durchspielen, bevor man das zu fuß probiert...

also ich habe jetz für die erfolgreiche suche folgendes rausbekommen:
a) 1,90
b)1,63
c)1,45

hat das irgendwer auch so?

mfg

cowhen

@cowhen

also 1,9 bei aufgabe 1a habe ich auch. bei teil b weiss ich nicht genau wie ich das berechnen soll. hatte da zwischenzeitlich mal 1,41 heraus. wie hast du das denn gemacht?


gruss Jens

@cowhen
Habe auch so
@Zypressen Hügel
Ich verstehe nicht ganz, was du meinst. Kannst du etwas ausführlicher erklären?
mfg
MAX

Erfolgreiche Suche ist ja noch okay, aber erfolglose? Hat da schon jemand ein Ergebnis? Oder ein Programm?

Die Idee hinter der Berechnung des mittleren Aufwandes für die erfolglose Suche ist folgende:

Die Anzahl der Tabellenzugriffe, die man benötigt, um festzustellen, daß ein bestimmtes Element, von dem der Wert der primären und sekundären Hashfunktion bekannt ist, nicht in der Tabelle enthalten ist, sollte einfach zu ermitteln sein (Tabelle solange durchgehen bis man entweder einen leeren Tabellenplatz findet oder am Ausgangspunkt der Suche angekommen ist).

Nun interessiert uns aber der *durchschnittliche* Aufwand, den man benötigt, um festzustellen, daß ein Element nicht in der Tabelle enthalten ist. Dazu müßte man prinzipiell *alle* (sind leider unendlich viele) nicht enthaltenen Elemente durchprobieren und für jedes den o. g. Aufwand ermitteln. Die Gesamtsumme der Tabellenzugriffe teilt man dann durch die Anzahl der geprüften Elemente und hat damit den gesuchten Mittelwert.

Da man aber nicht unendlich viele Elemente durchprobieren kann, nutzt man aus, daß bei diesen unendlich vielen Elementen jede Kombination von Starttabellenplatz und Schrittweite (also Ergebnis der primären und sekundären Hashfunktion) gleichwahrscheinlich ist (ergibt sich aus den Anforderungen, die wir an die Hashfunktionen gestellt haben). Also kann man einfach den Aufwand für alle möglichen Kombinationen von Starttabellenplatz und Schrittweite berechnen (sind in diesem Fall 14 * 13 Möglichkeiten) und die Gesamtsumme durch die Anzahl der Summanden teilen -- auf diese Weise erhält man dann den gesuchten Mittelwert. Da man bei 14 * 13 = 182 Möglichkeiten per Hand natürlich recht langer beschäftigt wäre, bietet sich hier natürlich ein selbstgeschriebenes Programm an (ist nicht kompliziert, drei verschachtelte Schleifen und ein bißchen Zählerei sollten genügen).

Ich komme auf folgende Zahlen:
a) 3,85
b) 3,50
c) 3,81

(Achtung: Ich habe die Zahlen leicht verändert (Abweichung +- 0,02), um nicht die Ergebnisse vorher zu verraten. Das Programm müßt ihr also schon selber schreiben )

@Joachim

hast du jetzt für die nicht_erfolgreiche suche drei verschiedene ergebnisse ??

habe nämlich nachgerechnet und habe verschiedene ergebnisse - es soll aber immer das gleiche rauskommen

Quoted

Original von spehler62
es soll aber immer das gleiche rauskommen

Wer sagt das?

Über sieben-ecken gehört
hat sich jemand von Niklas erklären lassen und der meinte überall kommt dasselbe raus

Quoted

Original von spehler62
Über sieben-ecken gehört
hat sich jemand von Niklas erklären lassen und der meinte überall kommt dasselbe raus

Kann ich nicht bestätigen. Ich habe eben mein Programm nochmal genau überprüft und auch eine alternative Implementierung verwendet, komme jedoch auf die selben Ergebnisse wie vorher.

Im allgemeinen ist der mittlere Aufwand bei der nicht erfolgreichen Suche jedenfalls nicht bei allen Anordnungen der Elemente derselbe (wenn man von konstanter Tabellengröße und konstanter Elementzahl ausgeht). Ich habe nämlich zwei einfache Fälle gefunden (Tabellengröße sechs), die ich per Hand auszählen konnte und die einen unterschiedlichen mittleren Aufwand haben.

okay,danke für deine mühe.
Hätte ja auch sein können, dass du einen kleinen fehler in deinem programm hattest. Mal schauen was die musterlösung sagt.

Quoted

Original von spehler62
Über sieben-ecken gehört
hat sich jemand von Niklas erklären lassen und der meinte überall kommt dasselbe raus

So so, über sieben Ecken... Gemahnt an "Stille Post"
Wenn ich das gesagt wirklich habe, kann ich mich jetzt nicht mehr daran erinnern. Ist auch falsch: Bei der gegebenen Tabelle kommen definitiv verschiedene Werte heraus. Vielleicht kam das Mißverständnis zustande, weil es im letzten Jahr anders war.

@np
naja, ich geb' ja zu die sieben Ecken sind eher eine Gerade
Zu ihm meintes du, dass bei allen drei Tabellen dasselbe Ergebnis für die nicht_erfolgreiche_Suche rauskommen soll und ich glaube nicht, dass er dich so sehr mißverstanden hat.