Funktionsweise einer Hashfunktion

[Fenixx]

Guten Abend,

ich habe eine Verständnisfrage zur Funktionsweise einer Hashfunktion.

Angenommen es muss eine eigene Hashtafel implementiert werden, die folgendes leisten muss:
-void put(int value) nimmt value in der Hashtafel auf,
-boolean contains (int value) prüft, ob value in der Hashtafel abgelegt ist,
-void remove (int value) löscht value aus der Hashtafel, falls value dort vorhanden ist,
-boolean isEmpty() prüft, ob die Hashtafel leer ist,
-int load() liefert die Anzahl der belegten Einträge im Feld der Hash-Tafel,
-int size() liefert die Größe des Feldes der Hashtafel,
-void rehash() verdoppelt das Feld der Hashtafel auf 2*size(). rehash() wird ausgeführt, wenn die Anzahl der belegten Elemente in einer Hashtafel mehr als 75% der verfügbaren Elemente des Feldes beträgt.
-Liste allKeys() liefert eine ungeordnete Liste aller in der Hashtafel abgelegten Werte.

Die Hashfunktion h(x) sei gegeben durch:
h(x)=x mod size()
Dabei soll eine Lineare Liste verwendet werden, falls der berechnete Key einer Hashfunktion doppelt vorkommt.

Wird der Key durch die Hashfunktion berechnet?

Das Array von Linearen Listen ist mit der Größe 7 initialisiert.

Nun meine Frage: Ich habe möchte nun 6 und 13 einfügen. Durch die Hashfunktion werden 6 und 13 in die gleiche Klasse eingeteilt, nämlich 6.
In der linearen Liste an der Position [5] gibt es nun 2 Elemente: 6 und 13.
Nun habe ich ja bei einer HashTable immer Key/Value-Paare. Da 6 und 13 aber den gleichen Key haben (6). Dann ist doch die Eindeutigkeit nicht mehr gegeben, oder sehe ich da etwas falsch (was sehr wahrscheinlich sein müsste).

 

[tfa]

Eindeutigkeit muss auf jeden Fall gegeben sein. Kollisionen müssen behandelt werden. Such mal nach "geschlossenem Hashing" und "offenem Hashing".

 

[Fenixx]

Die Aufgabe ist von einem Übungsblatt.
Um solch eine Kollision zu vermeiden könnte man ja folgende Hashfunktion nehmen:

h_i(x): (h(x)+i) mod size()

So wird bei belegtem Platz der nächste genommen, ist dieser belegt, desssen nächste usw.

Das Konzept ist mir bewusst. Aber ist die Lineare Liste an der Stelle i im Array nicht dafür da, um solche Kollisionen zu vermeiden? Schließlich habe ich ja dann bei gleichem Schlüssel mehrere Elemente in meiner Liste
Oder wofür ist sie sonst da?
Das leuchtet mir noch nicht so ganz ein.

 

[SlaterB]

zum Vermeiden ist die Hashfunktion, die Liste ist zum Umgehen mit den unvermeidlichen Kollisionen,
eben dadurch, die mehreren Elemente (+Keys) pro Hashwert abzulegen

 

[Fenixx]

Wie definierst du vermeidlich und unvermeidlich?
h(x)=x mod size()
Es ist mir nicht bewusst, was hier vermieden werden soll.
Ist nicht der Hashwert in diesem Fall nicht auch gleichzeitig der Key?

 

[SlaterB]

der Key ist x,
wenn alle x auf h(x) 1 abgebildet werden, dann vermeidet die Hashfunktion gar nicht,
mit x mod size() verhindert die Hashfunktion einiges,
nicht aber den von dir angesprochen Konflikt bei x = 6 und 13 (komische Beispiel, aber ist ja egal)

solche Konflikte lassen sich nicht ganz vermeiden, daher gibt es eine Liste,
in welcher die Paare 6+zugehöriges Objekt sowie 13+zugehöriges Objekt gespeichert sind,

sucht man nun nach Key 6, liefert die Hashfunktion die Liste mit beiden Ablagen, deren Keys muss man noch manuell genauer vergleichen,
ist 13 == oder equal 6? nö nicht so,
ist 6 == oder equal 6? yippie, Key + zugehöriges Objekt zum Suchkey 6 gefunden

selbst wenn die Liste nur ein Element enthalten sollte muss es nicht unbedingt das richtige sein,
gleicher Hashwert bedeutet nicht gleicher Key, sondern nur eine Grobaussortierung aller anderen,
man muss immer mit equals noch den Key genau abgleichen

 

[Fenixx]

Wenn ich es richtig versteh:

Die Keys sind 6 und 13. Die Position der Abspeicherung erfolgt durch die Berechnung des Hashcodes durch die Hashfunktion. 6 und 13 haben dann denselben Hashcode?

Aber was sind dann die Values in dem oberen Beispiel?
-void put(int value) nimmt value in der Hashtafel auf (Ich kenne es zugegebenermaßen nur mit put(Key, Value)).

Was sind dann die Values? Doch auch 6 und 13.

Könntest du vielleicht nochmal sauber definieren was was ist? ;-). Ich bin da etwas verwirrt^^.
Vielleicht so: Key/Value/Hashcode

Dann wirds sofort ganz eindeutig.
Vielen Dank

Edit: Sry ich hab dein Edit erst nach dem Post gesehen.

 

[SlaterB]

in einer normalen HashMap lautet die Methode
put(key,value)
insofern kann ich nicht sagen, was bei put(value) passieren soll,

ich vermute, dass es gar keine Values gibt, sondern nur Keys, denn es gibt die Methode
> Liste allKeys() liefert eine ungeordnete Liste aller in der Hashtafel abgelegten Werte.
die Keys mit Werten = Values gleichsetzt

das ganze wäre also in Java-Mitteln ausgedrückt eher ein HashSet statt einer Map

 

[Fenixx]

Alles klar;-).
Eine Frage noch. Du meintest ja folgendes:

sucht man nun nach Key 6, liefert die Hashfunktion die Liste mit beiden Ablagen, deren Keys muss man noch manuell genauer vergleichen,
ist 13 == oder equal 6? nö nicht so,
ist 6 == oder equal 6? yippie, Key + zugehöriges Objekt zum Suchkey 6 gefunden

Das heißt doch, dass die Liste die eigentlichen Key/Value-Paare beinhaltet oder?

 

[SlaterB]

wie gesagt

daher gibt es eine Liste,
in welcher die PAARE 6+zugehöriges Objekt sowie 13+zugehöriges Objekt gespeichert sind,

nach dem Interface des ersten Postings, welches ich damals noch nicht so wirklich bedacht habe,
scheint es aber eher so als wenn nur der Key selber, also die 6 und die 13 gespeichert wird,

ist ja relativ gleich, zentral ist sowieso die Suche nach dem Key selber, ob der exakt so vorhanden ist,

ob man dann den Key zurückgibt oder löscht, nur einen boolean zurückgibt ob vorhanden (contains) oder ein zusätzlich gespeichertes Objekt, wie in einer Map üblich, sind fast schon Randdetails