Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
ich weiss wie man eine Hashmap nutzt !!!!!!!!!!!!
Aber folgender Code verwirrt mich trotzdem:
Code:
/*
* *
* This example shows how not to use a Hashmap
*/
import java.util.HashMap;
public class HashConfuser
{
private HashMap hm = new HashMap();
public HashConfuser()
{
}
public void run()
{
boolean error = false;
int iterator = 0;
// Run only till error occurres
while (!error)
{
++iterator;
hm = new HashMap();
System.err.println("-->Iteration: " + iterator);
// Run max 6000 times
for (int a = 0; (a < 6000)&&!error; a++)
{
// Create object with unique id
MyObject temp1 = new MyObject(a + "A" + System.nanoTime());
// generate key for map by hashing the object
Object key = String.valueOf(temp1.hashCode());
// Check wether object is already in hashmap
if (hm.containsKey(key))
{
// Can this really happen ?
// Yes, but why and why always at the same step ?
System.err.println("------Error occured after " + hm.size() + " objects in iteration " + iterator
+ " ------:--");
System.err.println("Duplicate found: *\t " + hm.get(key) + "\n\t\t *\t " + temp1);
error = true;
}
else
{
// else store it there !
hm.put(key, temp1);
}
}
}
}
public static void main(String[] args)
{
// MAIN
new HashConfuser().run();
}
class MyObject
{
private String key = "";
public MyObject(String key)
{
this.key = key;
}
public String toString()
{
return key;
}
}
}
Weiss jemand konkret warum der Fehlerfall auftaucht.
Technische/Logische Begründung !
Es kann sein das der gleiche Hashcode von nem anderen Objekt der gleiche ist wie der vom anderen ^^
Das ist das Problem...
Eineindeutig: Sie bedeutet, dass jedes Element der Zielmenge höchstens einmal als Funktionswert angenommen wird. Es werden also keine zwei verschiedenen Elemente der Definitionsmenge auf dasselbe Element der Zielmenge abgebildet. Eine injektive Funktion ist daher (als Relation gesehen) linkseindeutig.
Fu Mathebegriffe!
Auf deutsch, es muss net eindeutig sein... Wayne interssieren mathmatische Begriffe :bae:
Und offenbar liefert die hashCode Methode keinen besonders guten Hash so das hier schnell eine Kollision auftritt.
Aus der Dokumentation zu java.lang.Object:
It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hashtables.
Nein, nein und nochmals nein!!! :x :x :x
Wenn der Hashcode nicht eindeutig wäre, könnte es passieren,
daß der hashcode von "Ich bin ein String" einmal 42 und ein anderes
mal 24 sein kann. Und genau das ist eben nicht der Fall.
Wir alle meinen zwar dasselbe, benutzen aber unterschiedliche Wörter
(oder heißt es in diesem Fall Worte ???:L )
Nicht umsonst sagt Google
google hat gesagt.:
Ergebnisse 1 - 100 von ungefähr 54.100 Seiten auf Deutsch für eineindeutig . (0,41 Sekunden)
Du hast doch verstanden was ich gemeint habe und die Konsequenz für das obige Programm erkannt, oder nicht?
Natürlich war damit nicht gemeint, dass die gleichen Daten mit gleichem Hash Algorithmus gehasht unterschiedliche Ergebnisshashes bringen können. Es war gemeint das unterschiedliche Daten gehasht gleiche Hashwerte ergeben können.
Jo, leoroy, hör auf uns mit deinen mathematischn Wörtern zu ärgern...
Ich dachte net mal dass das ein Wort ist...
Jeder versteht was wir meinen, das ein hashwert nicht eindeutig sein muss, dh, es kann von anderen Objekten das gleiche sein. Ist aber pro Objekt (wenn sich dieses net ändert) immer der gleiche!
@Leroy: Zustimmung :toll:
Wenn man verstehen will, wie ein Hash-Algorithmus funktioniert, sollte man so grundlegende Begriffe wie Eineindeutigkeit eigentlich kennen ... :meld:
Hallo zusammen,
das hört sich ja ganz plausibel an,
aber warum habe ich immer den fehler
nach der gleichen anzahl von durchläufen.
Unterschiedlich konstante Zahl auf verschiedenen PCs ?
Hallo zusammen,
das hört sich ja ganz plausibel an,
aber warum habe ich immer den fehler
nach der gleichen anzahl von durchläufen.
Unterschiedlich konstante Zahl auf verschiedenen PCs ?
Weil, wie wir hier ja schon festgestellt haben, die gleichen Daten mit dem gleichen Algorithmus gehasht immer den gleichen Hashwert ergeben. Und offenbar sind in der Schleife 2 Objekte dabei die den gleichen Hashwert ergeben, und das die dann immer an der gleichen Stelle auftrefen ist dann ja logisch.
Hallo zusammen,
das hört sich ja ganz plausibel an,
aber warum habe ich immer den fehler
nach der gleichen anzahl von durchläufen.
Unterschiedlich konstante Zahl auf verschiedenen PCs ?
Weil, wie wir hier ja schon festgestellt haben, die gleichen Daten mit dem gleichen Algorithmus gehasht immer den gleichen Hashwert ergeben. Und offenbar sind in der Schleife 2 Objekte dabei die den gleichen Hashwert ergeben, und das die dann immer an der gleichen Stelle auftrefen ist dann ja logisch.
Für so etwas gibt es ja auch Kollisionshandling, wo normaler Weise festgelegt wird, was im Kollisionsfall passieren soll.
Nochmal zur Eineindeutigkeit (oder auch Injektivität&Surjektivität bzw Bijektivität *komplette Verwirrung stift* ):
wenn ich eine Menge aus m Objekten auf eine Hashtabelle mit max n verschiedenen Hash-Werten abbilde, kann keine injektive Zuordnung mehr stattfinden (es gibt also mehrere Objekte, die den gleichen Hashwert bekommen), sobald m>n ist, was spätestens beim Hashing von Dateiinhalten passieren dürfte.
Sicherlich kann eine optimale Hashfunktion die Kollisionsfälle minimieren; aber solange man Kollisionen nicht zu 100% durch den Kontext ausschliessen kann, bedarf diese Zuordnung einer Kollisionsbehandlung.
Nochmal zur Eineindeutigkeit (oder auch Injektivität ):
wenn ich eine Menge aus m Objekten auf eine Hashtabelle mit max n verschiedenen Hash-Werten abbilde, kann keine injektive Zuordnung mehr stattfinden...
Hallo zusammen,
das hört sich ja ganz plausibel an,
aber warum habe ich immer den fehler
nach der gleichen anzahl von durchläufen.
Unterschiedlich konstante Zahl auf verschiedenen PCs ?
Weil, wie wir hier ja schon festgestellt haben, die gleichen Daten mit dem gleichen Algorithmus gehasht immer den gleichen Hashwert ergeben. Und offenbar sind in der Schleife 2 Objekte dabei die den gleichen Hashwert ergeben, und das die dann immer an der gleichen Stelle auftrefen ist dann ja logisch.
Nunja, aber wie man sieht werden die Objekte und deren Inhalt zur Laufzeit (und eigentlich eindeutig) erzeugt in folgenden Code sogar mit Zufallszahlen.
So dass diese gleichen (hash-gleichen) Objekte eher zufällig und nicht konstant erzeugt werden sollten.
Und nu ?
Code:
/*
* *
* This example shows how not to use a Hashmap
*/
import java.util.HashMap;
import java.util.Random;
public class HashConfuser
{
private HashMap hm = new HashMap();
public HashConfuser()
{
}
public void run()
{
Random ran=new Random();
boolean error = false;
int iterator = 0;
// Run only till error occurres
while (!error)
{
++iterator;
hm = new HashMap();
System.err.println("-->Iteration: " + iterator);
// Run max 6000 times
for (int a = 0; (a < 6000)&&!error; a++)
{
// Create object with unique id
MyObject temp1 = new MyObject(ran.nextInt(10000)+a + "A" + System.nanoTime());
// generate key for map by hashing the object
Object key = String.valueOf(temp1.hashCode());
// Check wether object is already in hashmap
if (hm.containsKey(key))
{
// Can this really happen ?
// Yes, but why and why always at the same step ?
System.err.println("------Error occured after " + hm.size() + " objects in iteration " + iterator
+ " ------:--");
System.err.println("Duplicate found: *\t " + hm.get(key) + "\n\t\t *\t " + temp1);
error = true;
}
else
{
// else store it there !
hm.put(key, temp1);
}
}
}
}
public static void main(String[] args)
{
// MAIN
new HashConfuser().run();
}
class MyObject
{
private String key = "";
public MyObject(String key)
{
this.key = key;
}
public String toString()
{
return key;
}
}
}
Wie wäre es, in MyObject einfach die Methode 'hashCode()' zu überschreiben? Die von Object geerbte ist nicht wirklich gut ...
Edit:
zum Beispiel so:
Code:
final int basis = 37;
final int multi = 17;
public int hashCode ()
{
int result = basis;
result = multi * result + this.intAttribut1;
result = multi * result + this.intAttribut2;
result = multi * result + this.intAttribut3;
// ... weitere int-Attribute
result = multi * result + this.stringAttribut1.hashCode();
result = multi * result + this.stringAttribut2.hashCode();
result = multi * result + this.stringAttribut3.hashCode();
// ... weitere String-Attribute
// ... sonstige Attribute entsprechend konstruieren
return result;
}
So sollte eine Hashfunktion aussehen (in Anlehnung an: Joshua Bloch, Effektiv Java programmieren).
/*
* *
* This example shows how not to use a Hashmap
*/
import java.util.HashMap;
import java.util.Random;
public class HashConfuser
{
private HashMap hm = new HashMap();
public HashConfuser()
{
}
public void run()
{
Random ran=new Random();
boolean error = false;
int iterator = 0;
// Run only till error occurres
while (!error)
{
++iterator;
hm = new HashMap();
System.err.println("-->Iteration: " + iterator);
// Run max 6000 times
for (int a = 0; (a < 6000)&&!error; a++)
{
// Create object with unique id
MyObject temp1 = new MyObject(ran.nextInt(100)+a+ System.nanoTime());
// generate key for map by hashing the object
Object key = String.valueOf(temp1.hashCode());
// Check wether object is already in hashmap
if (hm.containsKey(key))
{
// Can this really happen ?
// Yes, but why and why always at the same step ?
System.err.println("------Error occured after " + hm.size() + " objects in iteration " + iterator
+ " ------:--");
System.err.println("Duplicate found: *\t " + hm.get(key) + "\n\t\t *\t " + temp1);
error = true;
}
else
{
// else store it there !
hm.put(key, temp1);
}
}
}
}
public static void main(String[] args)
{
// MAIN
new HashConfuser().run();
}
class MyObject
{
private long key = -1;
public MyObject(long key)
{
this.key = key;
}
public int hashCode()
{
//unique systemadress
return System.identityHashCode(this);
}
public String toString()
{
return ""+key;
}
}
}
