doppeltes Hashing

[Landreas]

Ich habe folgendes Problem wir müssen eine kollisionsfunktion via doppeltem hashing machen, d.h. wir haben 2 Hashingfunktionen:
h1 = lineares Aufsummieren jedes Zeichens eines Strings
h2 = Aufsummieren jedes Zeichens eines Strings mit Gewichtung (also 1. Zeichen 1, 2. Zeichen 2, usw...)

dann ergibt sich ja als kollisionsfunktion (wert(h1)+wert(h2))%tabellenlänge. Wenn aber das daraus resultierende Bucket bereits besetzt ist, wird die Funktion wieder aufgerunfen, gibt wieder den gleichen wert zurück und das ganze wird zu einer endlosschleife...

ohne das wir einfach +1 irgendwo einsetzen müssen wir das nun lösen. Jemand von euch eine Idee, ich verzweifle dran.

LG, Andreas

 

[Babba_BLuBB]

Du koenntest es so machen, dass sie die Gewichtungsfaktoren von h2 bei jedem Aufruf ändern...

 

[Bleiglanz]

was wollt ihr eigentlich machen wenn der Bucket voll ist???

dann müsst ihr doch einen neuen anlegen...

der wert der hashfunktion kann sich ja wohl kaum ändern??

 

[ronny]

Hi Landreas,

hmmm, is schon ne weile her mit dem hashing, aber mal gucken...

also, die hashfunktion hast du ja bereits...
es gibt ja einmal das "einfache" Hashing und das verkettete Hashing.

Beim "einfachen" Hashing kommst du um den Kollisionszähler direkt nicht drumrum.

Du könntest allerdings auf des verkettete Hashing ausweichen und in deinem "Bucket"
eine Liste reintun, die die Elemente an dieser x mod y Position hält. d. h. wenn du mit deiner Hashfunktion
an Pos. X ankommst, dann schnappst du dir die Liste daraus und plazierst das
neue Objekt an der quasi "letzen" Stelle der Liste.... oder, wenn schon vorhanden
ist, eben nicht. Natürlich kommst du um ein "Durchlaufen" von Listen nicht drumherum..

Auf gut Deutsch hast du ne Liste mit länge m (bei dir "tabellenlänge") und in dieser
liste sind an den Positionen x mod m wieder Listen enthalten, die dann die "eigentlichen"
unterschiedlichen Objekte mit dem selben Ergebnis von x mod m enthalten....

das mit dem "wir dürfen kein i++ verwenden" verstehe ich da nicht so ganz... ???:L

vielleicht ist das ja mit dem verketteten Hashing ein Ansatz für dich.... :wink:

 

[Babba_BLuBB]

@ Bleiglanz:
Es darf ja kein neues Bucket angelegt werden!
Die Anzahl der Buckets muss von Anfang an festgelegt sein.

So weit ich weis muss man durch schrittweise modifikation der Hashfunktion ein leeres Bucket finden...

@Landreas:
Hat euer Lehrer/Prof. gesagt, ob ihr offenes oder geschlossenes Hashing verwenden sollt?
Wenn ihr offenes Hashing verwenden dürft ist die Lösung mit der Liste natürlich am Besten!
Aber dann bräuchtest du h2 nicht...

 

[ronny]

ne, die hashfunktion darf man nicht verändern....
du kannst beim "einfachen" hashing nur über den kollisionszähler
das nächste freie bucket finden...

hast du allerdings verkettetes hashing, hast du in deinem bucket
"listenköpfe" drin, die auf Listen zeigen, die die Objekte enthalten..

so umgehst du das mitschleppen des kollisionszählers..

 

[Babba_BLuBB]

ne, die hashfunktion darf man nicht verändern....

Meinte mit "modifizierten" dass man den Kollisionszaehler mit in die Hashfunktion einbaut...
Aber +1 darf ja nicht benutzt werden....

 

[messi]

Du könntest der Hash-Funktion einen "seed" übergeben. Und zwar den Bucket, der bei einem seed = 0 herauskommt. Der seed wird dann addiert und es kommt ein neuer Bucket heraus. Wenn der besetzt ist, wiederholst du das für einen dritten, usw. Könnte aber auch zu einer Endlosschleife führen.

public static int hash(String s, int seed) {
    int hash = 0;
    // hash = wert(h1) + wer(h2)
    hash += seed;
    return hash;
}

Keine Ahung, ob das gut ist.

 

[KISS]

also ich erinner mich mal ein bischen aus meinem studium

1. hashfunktionen sollten ueber primzahlen laufen, um moeglichst breite streuung zu erziehlen.

2. double hashing ist 2 wege hashing, also ist die addition 2er hashfunktionen eigentlich nicht sinvoll

3. buckets sind (da hashfunktionen nun mal nicht bijektiv sind) listen in denen auf gleichheit geprueft wird, beim double hashing ist dies meist wieder eine hashlist, in der die buckets dann wierder listen sind

4. natuerlich können hashlisten erweitert werden, allerdings sind die meisten dynamischen hashlisten eher statisch mit rehasing

5. um dein problem zu loesen, siehe 3

6 erst denken, dann schreiben

So weit ich weis muss man durch schrittweise modifikation der Hashfunktion ein leeres Bucket finden...

und wie zur hoelle wilst du so irgend etwas wiederfinden

 

[Babba_BLuBB]

... Und zwar den Bucket, der bei einem seed = 0 herauskommt. ...

Das ist gar nicht mal schlecht... So wird die +1 vermieden und trotzdem der Wert der Hashfunktion modifiziert... :toll:

 

[Babba_BLuBB]

und wie zur hoelle wilst du so irgend etwas wiederfinden

Hab doch oben geschrieben, dass ich den Kollisionszaehler einbauen wuerde.

Wenn i der Kollisionzaehler ist dann wuerde ich h2 wie folgt aufbauen:
h2 = [Buchstabe1 * (Gewicht+i) + Buchstabe2 * (Gewicht+i) + .......] mod Bucketanzahl

Diese "Modifikation" ist nachvollziehbar und kann beim Suchen in der Hashtabelle genau so wieder aufgebaut werden...

 

[KISS]

du hast das prinzip des bildens von hashes zur schnellen suche voll verstanden, hut ab.

 

[Babba_BLuBB]

du hast das prinzip des bildens von hashes zur schnellen suche voll verstanden, hut ab.

Wie jetzt? Ironisch oder ernsthaft?

 

[ronny]

ich kann nur nochmals empfehlen, auf verkettetes hashing auszuweichen...
da haste listen in ner liste,
kriegst sofort die pos in deinem array oda liste über die hashfunktion und kannst dann
die liste durchgehen, ob objekt vorhanden oda nicht, einfügen, etc.
kein rummodifizieren der hashfunktion, wieder decodieren und was weiß ich noch alles...
und kein +1.... (zumindest nicht direkt sichtbar... ) :wink:

 

[Landreas]

ja ne leider verkettetes hashing haben wir schon in einer anderen funktion, ich denke ich werde die Methode mit dem seed ausprobieren. Und vielen Dank für eure zahlreichen Vorschläge.