Java Eindeutige ID für einen String

[darton]

Hallo!
Ich bin im Moment dabei Excel-Dateien mit Java auszulesen. Eine Zeile in einer Excel-Datei besteht dabei aus etwa 10 Zellen, die ich als Strings in einem Objekt ablege. Es kann allerdings passieren, dass in den Excel-Dateien mehrere Datensätze mit denselben Werten auftreten. Anstatt immer alle 10 Werte auf Gleichheit zu überprüfen, möchte ich einfach jedem Objekt einen eindeutigen Schlüssel mitgeben, sodass man nur diesen Schlüssel vergleichen müsste. Dazu konkateniere ich einfach alle 10 Werte zu einem neuen String und aus diesem String soll dann eine ID erzeugt werden. Nur wie kriege ich das hin, dass unterschiedliche Strings auch unterschiedliche IDs bekommen. Ich habe jetzt erstmal an den Hashwert gedacht, nur frage ich mich, ob der Hashwert wirklich eindeutig ist. Der Mathematiker würde jetzt fragen, ob die Hashfunktion bijektiv ist. Vielleicht könnt ihr mir bei der Frage ja behilflich sein oder Alternativen vorschlagen.

 

[..Gast]

Du vergleichst erst den Hashwert, ist dieser gleich dann vergleichst du alles. Ist dieser ungleich dann machst du weiter. Hashwerte sind von Natur nicht und niemals eindeutig.

 

[platin91]

Hashwerte sind definitiv NICHT eindeutig.
Wenn du jeden String nur einmal brauchst leg doch ein HashSet<String> an, da
sind naturgemäß Duplikate entfernt.

 

[Shagg]

Bei Hashfunktionen nennt man sowas kollsionssicherheit. natürlich sind sie dies nicht zu 100%, dass ergibt sich schon alleine daraus, das du von einem "unendlichen" raum (hier deine strings) in einen hashwert fester länge abbildest. für deine zwecke sollte ein hashwert aber denke ich funktionieren. es ist ja eben eines der sicherheitskriterien einer hashfunktion, das es schwer sein soll zwei eingaben (hier wieder deine strings) zu finden die den gleichen hashwert liefern (kollsion).

 

[-Razzer-]

Wie genau sind den die Daten abgespeichert?

12 | 34 | 56 | 78 als String "12345678"
1 | 234 | 5 | 678 als String "12345678"

Hashwert wäre der gleiche nur die Zeilen sind es nicht.
Du kannst dir auch eine eigene Methode ausdenken und hashCode() überschreiben.

 

[Zhak]

Die hashCode-Methode ist keine Hashfunktion. Die Berechnung dahinter erzeugt für jeden String einen eindeutigen Wert. Sie ist dazu da einen Integerwert zu erzeugen der dann anschließend von einer Hash-Funktion verarbeitet werden kann. Aber da es unendlich viele Strings gibt kann der erzeugte Integerwert überlaufen wodurch dann wieder Kollisionen(also zwei unterschiedliche Strings erzeugen den gleichen hashCode) enstehen.

 

[misu]

Also,
Hashfunktionen sind natürlich nicht bijektiv, und zwar weil zwar jedem Urbild (z.B. jedem (fast) beliebig langen String) ein Wert einer fixen Größe (z.B. 64bit) zu geordnet werden. Da beide Mengen endlich, die Urbildmenge jedoch größer, existiert keine inverse Abbildung => nicht bijektiv.

ABER: In der Praxis ist das eigentlich völlig unerheblich. Wenn du nicht extrem viele Hashs hast, wird eine Kollision quasi nie auftreten.

In der Regel ist ein Hash zwar nicht eindeutig, verhält sich aber praktischerweise so.

Gruß,
misu

edit: Es gibt natürlich auch sowas wie bijektive Hashfunktionen, z.B. die identische Abbildung. Hab ich allerdings noch nie in der Praxis gesehen.

 

[darton]

An eine HashSet habe ich noch gar nicht gedacht. Da könnte ich ja dann meine ganzen Objekte unterbringen.
Also ein Datensatz besteht bei mir aus mehreren Strings und ein paar Zahlen. Durch die Konkatenation passiert es auf jeden Fall NICHT, dass dadurch gleiche Strings auftreten.
In die HashSet müssten dann so ca. 1000 Daten rein. Bei einer solchen Anzahl werden beim Hashwert wohl keine Kollisionen auftreten, oder?
Ich hatte mir durch den Hashcode eigentlich auch noch gedacht, dass man die Collection (sortiert nach Hashwert) dann binär durchsuchen könnte. Oder verläuft das Suchen in einer HashSet nach doppelten Einträgen intern sowieso binär?

 

[platin91]

Wenn du bei den Objekten nicht übermäßig viel Pech hast gibt das bei der Menge wohl nur ein paar oder keine Kollisionen.
HashSet wird per Hash durchsucht, wenn du wenig Kollisionen hast kommt das Ergebnis mehr oder weniger sofort.

 

[..Gast]

für deine zwecke sollte ein hashwert aber denke ich funktionieren. es ist ja eben eines der sicherheitskriterien einer hashfunktion, das es schwer sein soll zwei eingaben (hier wieder deine strings) zu finden die den gleichen hashwert liefern (kollsion).

Sag niemals nie! Mit der herangehensweise "Wird schon keine Kollisionen geben!" hat man sich nicht selten einen Programmbug aus reiner nachlässigkeit (also faulheit) eingebaut den man in großen Programmen so schnell nicht mehr finden kann. Warum nicht gleich ordentlich machen?

Die hashCode-Methode ist keine Hashfunktion. Die Berechnung dahinter erzeugt für jeden String einen eindeutigen Wert. [..] Aber da es unendlich viele Strings gibt kann der erzeugte Integerwert überlaufen wodurch dann wieder Kollisionen(also zwei unterschiedliche Strings erzeugen den gleichen hashCode) enstehen.

... der erste Satz entstellt den letzten, oder andersrum. .hashCode() erzeugt auf primitivster Art und Weise einen HashWert -> s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] <- und reicht bei weiten nicht an die Verteilung eines guten Hash-Algos ran, mal ganz davon abgesehen das der HashWert nur 32-Bit hat. Aber wie gesagt, dafür ist er schnell erzeugt und reicht für einen einfachen vergleich.

ABER: In der Praxis ist das eigentlich völlig unerheblich. Wenn du nicht extrem viele Hashs hast, wird eine Kollision quasi nie auftreten.

In der Regel ist ein Hash zwar nicht eindeutig, verhält sich aber praktischerweise so.

Sag niemals nie! Mit der herangehensweise "Wird schon keine Kollisionen geben!" hat man sich nicht selten einen Programmbug aus reiner nachlässigkeit (also faulheit) eingebaut den man in großen Programmen so schnell nicht mehr finden kann. Warum nicht gleich ordentlich machen?

Wenn du bei den Objekten nicht übermäßig viel Pech hast gibt das bei der Menge wohl nur ein paar oder keine Kollisionen.

Korrekt! Aber ein Progamm das auf reiner Glückssache funktioniert oder eben nicht, das will man ja auch nicht haben.



Nimm ein HashSet, so wie hier schon vorgeschlagen. Die Arbeitsweise dieser HashSet sieht so aus, das du mit boolean vorhanden = HashSet.add("MeinText") einen Wert geliefert bekommst ob "MeinText" schon vorhanden ist. Dabei nutzt HashSet zum einen String.hashCode() um sich einen HashWert von "MeinText" zu erzeugen. Mit diesen HashWert sucht er intern ob es schon andere Strings gibt, die den gleichen HashWert erzeugt haben. Wenn ein String gefunden wurde, der den gleichen HashWert erzeugt dann wird mit String.equals() ZUVERLÄSSIG verglichen, ob es wirklich der gleiche Text ist oder nur der gleiche HashWert ist. Wird ein HashWert gar nicht gefunden, dann gibt es diesen String noch nicht.

... also, mach es ordentlich, verwende HashSet und ignorieren niemals den Fakt, das ein HashWert keine Eindeutigkeit besitzt ... auch nicht für eine kleine Anzahl von Strings!

 

[te one]

Wie genau sind den die Daten abgespeichert?

12 | 34 | 56 | 78 als String "12345678"
1 | 234 | 5 | 678 als String "12345678"

Hashwert wäre der gleiche nur die Zeilen sind es nicht.
Du kannst dir auch eine eigene Methode ausdenken und hashCode() überschreiben.

Was hälst du davon dieses Verfahren zum Hash-berechnen zu verwenden?
Ist eine kurze und schnelle Aufgabe:
Hänge alle Zahlen aneinander
Oder du könntest sogar noch ein Trennzeichen einfügen, damit das nicht wie oben beschrieben endet.

Allerdings wie oben schon erwähnt musst du dann wirklich noch prüfen ob es tatsächlich das gleiche ist. Weil so ein Hash nicht eindeutig ist.

Solltest du noch ein Trennzeichen einfügen oder so ganze wie oben einsetzten Frage ich mich allerdings ob das so viel Sinn macht...
Denn dein Code wäre ja in etwa so:

for each zeile
-if (!wert1 in spalte1)
->return true
->else: if (!wert2 in spalte2)
--------->return true
--------->else: if (!wert3 in spalte3)
...und so weiter...

Sollte die erste Spalte gleich anders als die anderen sein, dann ist dieses Verfahren sicherlich schneller.
Hast du viele Datensätze die vorne gleich sind und hinten unterschiedlich könntest du auch von hinten beginnen.

Ist halt die Frage wie schnell normalerweiße ein String=String vergleich im Gegensatz zu int=int ist. Und wenn int<>int am Anfang oft zutrifft kann das schon insgesamt einen satten Geschwindigkeitsvorteil bringen.

Müsstest mal die Zeit messen die man braucht:
-Wenn man zB in ein Array je Element eine ganze Zeile einliest und sogar ein bestimmtes Zeichen zur Trennung der Spalten verwendet
-zwei ints vergleicht

edit:
Noch eine super Idee:
Schreibe alle Zahlen hintereinander in einen String. Dann ordne das ganze in nem Baum (weiß nicht ob du dir dadrunter was vorstellen kannst -> http://www.at-mix.de/images/glossar/avl-baum.gif ).
Damit kannst du mit ganz wenig Aufwand dann prüfen ob es einen solche String schon gibt (wesentlich effektiver als zB ein komplettes Array zu durchlaufen).
Oder ein Baum in dem nur die Werte der ersten Spalte stehen und man wenn man ein passendes Element im Baum gefunden hat dort eine Verbindung zu einem anderen Baum hat...
Das ist aber nur ne Methode wenn du richtig richtig richtig viele Zeilen hast Oder langeweile...

 

[Elfire]

Weshalb einfach wenns auch kompliziert geht?
Einfach die Methoden hashCode() und equals() auf dem Objekt implementieren, das die Strings enthält.
Danach die Objekte in ein Set ablegen.
Falls du Eclipse benutzt, kannst du einfach Rechtsklick->Source->Generate hashCode() and Equals() auswählen, dann werden diese beiden Methoden generiert.
Andere IDEs werden diese Funktion sicher auch anbieten, aber da kenne ich mich zu wenig aus.

Dies ist wohl die einfachste und sicherste Variante damit du keine doppelten Einträge erhälst.