[Java] Hashingfunktion

W

weau

0
Hallo Habo,

angenommen wir haben diese sehr stark vereinfachte Klasse Rational.
Code: 
public class Rational{
private int zaehler;
private int nenner;

//Konstruktor
public Rational(int zaehler, int nenner){
this.zaehler = zaehler;
this.nenner = nenner;
}

usw...

}

Ich möchte jetzt eine Hashfunktion für Brüche schreiben.
Dabei ist folgende Struktur vorgegeben :
Code: 
public int hash(){


}

Eine Hashfunktion soll aus einer Eingabe (Parameter oder Klassenvariablen) immer einen Wert in einem bestimmten Wertebreich erzeugen und wenn ich das für Objekte mache, dann müssen die Objekte ja den gleichen Wert von der Hashfunktion bekommen, wenn diese equal sind?

Dann gibt es im Prinzip doch jetzt tausend Möglichkeiten, wie ich eine Hashfunktion schreiben könnte?
Code: 
public int hash(){
return (64 * this.zaehler) % 1024;
}

Code: 
public int hash(){
return (64 * this.nenner) % 1024;
}

usw...

Ist das korrekt oder muss ich mich immer auf nenner und zaehler beziehen?

LG , weau
 
Wenn du dich nur auf den Zähler beziehst und zwei Rationals haben denselben Zähler, haben sie ja auch denselben Hash oder? Darf das sein?

Ich muss allerdings gestehen, dass ich selbst noch NIE diese hash( Methode überschrieben habe.

cu
serow
 
Original von Serow
Wenn du dich nur auf den Zähler beziehst und zwei Rationals haben denselben Zähler, haben sie ja auch denselben Hash oder? Darf das sein?
Zum Vergrößern anklicken....

Bei unterschiedlichem Nenner dürften Sie eigentlich nicht die gleiche Hashzahl bekommen, d.h. ich müsste den Nenner noch einbauen.

Code: 
public int hash(){
return (64 * this.nenner + 64 * this.nenner) % 1024;
}

Könnte das passen?
 
Ich denke du musst beides einbeziehen...

Mit
Code: 
public int hash(){
        return (64 * this.nenner + 64 * this.nenner) % 1024;
}
hat 2/3 und 5/3 denselben hash, mit
Code: 
public int hash(){
        return (64 * this.zaehler + 64 * this.zaehler) % 1024;
}
hat 2/3 und 2/4 denselben hash.

Beides darf nicht sein.

cu
serow
 
Sorry, hatte mich oben verschrieben :
Code: 
public int hash(){
return (64 * this.nenner + 64 * this.zaehler) % 1024;
}
Müsste passen?
 
Man sollte vllt noch darauf achten, die Hash funktion möglisht performant zu halten.
Code: 
HASHING IN JAVA
Ziel effiziente Speicherung von Objekten
L Verteilen der m potenziellen Objekte auf n Container/Buckets
L Container ist Behälter für Einträge in einer Hashtabelle
L Zuordnung Objekt ? Container
L Meist m > n, die tatsächliche Anzahl an Objekten m? ist aber klein
L m' ~ n
L Z. B. 12-stellige Versicherungsnummern, aber nicht 1012 Versicherungsnehmer
L Hashcode für die Zuordnung einer Nummer (= Schlüssel) zu jedem Objekt
L Aufteilung der Nummern auf die Container durch Hashfunktion
L Mehrere Objekte je Nummer
L Mehrere Nummern je Container/Bucket
L Liste von Objekten in jedem Container
L Hashing-Idee
L Zu einer Klasse kann es sehr viele Objekte geben
L Aber nur wenige kommen wirklich vor
L Hashcode sollte vorkommende Objekte gleichmäßig auf Nummern aufteilen

Methode hashCode() in Object
L Hashwert für jedes Objekt
L Implementierung in Object: Speicheradresse
L Vertrag in Object
Konsistenz Gleicher Wert bei mehreren Aufrufen
equals Gleiche Objekte haben den gleichen Hashcode
Streuung Nicht gefordert: Unterschiedliche Werte für unterschiedliche
Objekte
L Aber empfohlen (Performance)
L In Java-Bibliotheken
L hashCode bestimmt den Container
L equals wird zum Vergleich innerhalb eines Containers benutzt
L Wer equals überschreibt, muss auch hashCode überschreiben
L Ansonsten unerwartetes Verhalten
Map<PhoneNumber, String> m = new HashMap<PhoneNumberm String>();
m.put(new PhoneNumber(001, 305, 12345), "Wilma");
boolean b = (new PhoneNumber(001, 305, 12345))
.equals(new PhoneNumber(001, 305, 12345)); // true
String wilma = m.get(new PhoneNumber(001, 305, 12345)); // null
Wenn du willst schick ich dir die PDF per PN (Skript aus der Uni)
 
Code: 
public int hash(){
return (64 * this.nenner + 64 * this.zaehler) % 1024;
}
Zum Vergrößern anklicken....
Damit erhältst du trotzdem den selben Hash falls zaehler1 + nenner1 = zaehler2 + nenner2:

Bsp.: 2/3 und 3/2:

(3*64 + 2*64) % 1024 = (2*64 + 3*64) % 1024

Außerdem hast du mit diesem Verfahren auch nur 1024 mögliche Hashwerte, was mir doch recht wenig erscheint.
 
MrSpider, es soll eine relativ einfache Hashfunktion sein (performance ist jetzt mal zweitranig).

du meinst folgendes?

Code: 
public int hash(){
return (64 * this.nenner - 64 * this.zaehler) % 1024;
}
 
Diese Varianten sind alle etwas zu simpel um einigermaßen kollisionsfrei zu sein. Bei deinem letzten Beispiel, wäre z.B. 1/4 und 2/5 wieder eine Kollision. Du könntest dir z.B. mal die Implementation von hash() für ints ansehen um ein Gefühl zu bekommen, wie eine Hashfunktion aussehen sollte.
 
Original von MrSpider
Eigentlich meinte ich wirklich nur Zähler - Nenner. Da einige Kollisionen akzeptabel sind und auch immer vorkommen werden.
Zum Vergrößern anklicken....

Wenn alle Brüche n/m jeweils mit (n+x)/(m+x) für jedes x aus N kollidieren, dann ist das für mich definitiv nicht akzeptabel und es sind mehr als "einige". Wozu sollte man diesen Hash in der Realität denn noch nutzen können, wenn die Kollisionswahrscheinlichkeit so hoch ist?
 
Ich möchte die Hashfunktion im Prinzip gar nicht nutzen. Eine ähnliche Aufgabe wurde in einer Klausur abgefragt und ich hab hier nach Lösungsansätzen gesucht.

Da war mein Beispiel in Post #1 angegeben und man sollte eine kleine Hashfunktion schreiben.
Code: 
public int hash(){
return this.nenner -  this.zaehler
}

wäre dann sicherlich eine Klausurlösung? In der Praxis würde man wahrscheinlich besseres benutzen oder hashCode() nicht überschreiben oder?
 
also wenn Performance keine Rolle spielt, wäre mein erster Gedanke: cheaten ;) d.h auf die bereits implementierte "gute" Hashfunktion zurückgreifen:
Code: 
return (Integer.toString(nenner)+"/"+Integer.toString(zaehler)).hashCode();
 
@CDW
Ja aber:
1. Die Integer HashFunktion gibt wahrscheinlich nur die zahl selbst zurück
2. Die HashFunktion (zumindest die von Objekt) gibt nen int zurück

@weau
HashFunktion sollte man immer überschreiben, wenn man die Klasse in einem Container nutzt (insbesondere Hash* Container), weil diese Funktion intern von den Containern zur effizienz *Verbesserung* (also wenn keine Hash Funktion gehts genauso) genutzt wird
 
Mit einem xor(zähler, nenner) verteilst du wenigstens deinen gesamten Datenbereich gleichmäßig. Mit einer Hash-Funktion, die int * int -> int abbildet, kriegt man sowieso massig Kollisionen. Da braucht man garnicht rumfummeln, die kriegt man nicht weg - wichtiger ist es, sie brauchbar zu verteilen.
Ohne weitere Informationen (tatsächlich verwendeter Datenraum kleiner als int) oder Wünsche (Brüchte bestimmter Form sollen keine Kollision ergeben) stellt sich auch imho garnicht die Frage nach einer weiteren Optimierung.
/edit: Also: public int hash(){ return (zaehler ^ nenner); }
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben