Collections Suche Collection, um Strings mit Indizees versehen

W

White_Fox

Top Contributor
Guten Abend allerseits.

Das Problem: Ich habe in einem großen Klassenhaufen viele Strings. Sehr viele Strings davon sind Duplikate. Jetzt ist mein Plan, die Strings in den betreffenden Klassen durch einfache Integer zu ersetzen. Wenn ich den String brauche, will ich in einer Collection nachsehen und anhand des Integerwertes den String wieder zuordnen können.

Hintergrund: ich will den Klassenhaufen serialisieren, und momentan wird jeder String dann mehrfach serialisiert. Das will ich abkürzen.

Wenn ich mit dem Integer nach dem String suchen will, würde sich ja normalerweise eine HashMap anbieten. Ich will aber auch den umgekehrten Weg gehen können: Den zugeordneten Integerwert will ich mit dem String genauso wiederfinden.

Kennt jemand eine Collection, die diese Zuordnung in beide Richtugen leistet?
 
Du könntest natürlich zwei Maps nutzen. Dann hättest du halt so beide Richtungen abgedeckt.
 
Hast du da wirklich ein Problem? Für mich sieht das ein bisschen nach "Pseudo-Optimierung" aus. Ich würde da ganz genau Benchmarken ob das was bringt
 
Nein, ein direktes Problem hab ich (noch?) nicht.

Es handelt sich bei den Objekten um Objektbeschreibungen und enthalten u.a. Klassennamen (für jede Vererbungsebene), Feldnamen, usw.
Und ich werde typischerweise weitaus mehr Objekte als Klassen haben, und jede Klassenbeschreibung wäre mehrfach redundant enthalten. Die Klassen- und Feldnamen machen den mit Abstand größten Teil der Daten aus, das gefällt mir einfach nicht. Das ist, so wie es jetzt ist, Schrott per Design.
Es würde funktionieren, sicher...aber ich will auch, das es gut funktioniert, das ist m.E. so noch nicht der Fall.

Ich habe einen Performancetest geschrieben, mit dem ich u.a. ermittle wieviele Daten ich erzeuge. Bei einem Durchlauf benötige ich aktuell 23.403.357 Bytes an Speicher. Ich werde berichten, wieviel Speicher er nach der Optimierung noch frißt.

Übrigens glaube ich eine Lösung für mein Problem zu haben...kennt jemand BiMap (Google Guava)?

Edit:
Ich stelle gerade fest, daß mir ein einzelner Key nicht ausreicht. Zwei Keys wären besser...
 
Zuletzt bearbeitet:
Das hört sich ja etwas in Richtung Normalisierung an, daher kann sowas durchaus Sinn machen - das war zumindest mein erster Eindruck beim Lesen.

Da wäre aber ggf. auch eine Idee, das auch entsprechend zu moddelieren. Also dann gibt es halt eine Klasse Xyz mit id und wert oder so und dann werden Referenzen statt der Strings gespeichert (und nicht nur die id, weniger Abfragen in der Verwaltung).

Als im einem anderen Thread Strin.intern() missbraucht wurde, hatte ich auch mal geschaut, was für sinnvolle Anwendungen es gibt und da bin ich über einen Fall gestolpert: da wurden nur String.intern() Werte in einigen Feldern gespeichert, weil so einiges an Speicher gespart wurde (laut der Person, die das gemacht hat). Mir fällt es schwer das zu glauben, aber wenn es sehr extrem war mit wenigen unterschiedlichen Strings, dann kann das eine Lösung sein.
Wichtig: Die Anzahl der unterschiedlichen Strings muss begrenzt sein, denn die bleiben durchgehend im Speicher.
Aber dann wäre das eine Möglichkeit sicher zu stellen, dass die Strings, die gleich sind, auch wirklich auf den gleichen String verweisen.
Da hat man aber dann erst einmal keine Serialisierung sonder nur die Darstellung im Speicher optimiert.

Aber nach der letzten Information würde ich mir das alles überlegen. Aktuell benötigst du 24MB Speicher. Wo siehst du Bedarf an Optimierungen?

BiMap dürfte intern auch nichts anderes machen als ich mit zwei HashMaps angedacht habe. Aber halt gekapselt in einer Klasse was ja eh erfolgen sollte. Dahersehe ich den Bedarf für so eine Abhängigkeit nicht wirklich (meine pers. Sicht - ich führe Abhängigkeiten nur ein, wenn dies entsprechend großen Mehrwert hat).

Das einfach mal als mein Senf zu dem Thema in der Hoffnung, dass es hilfreich ist.
 
Ich verstehe ehrlich gesagt sowieso noch nicht ganz, was du mit den ganzen Java internas rumjonglierst, dass du Klassen und Feldnamen halten musst. Ich vermute da gäbe es einfachere Lösungen, aber ich habe mich auch noch nicht gross mit deiner.Software auseinander
gesetzt. Ist also einfach mal eine Behauptung/Vermutung in den Raum.

Zur Optimierung würde ich sowieso erstmal nichts machen, bis du tatsächlich auf Probleme stösst. Die JVM kann da viel mehr Optimieren als man denkt.
 
JustNobody hat gesagt.:
Das einfach mal als mein Senf zu dem Thema in der Hoffnung, dass es hilfreich ist.
Zum Vergrößern anklicken....
Immer gerne...ich stelle das ja gern zur Diskussion. Wie ich immer sage, ich hab doch vom Programmieren eigentlich keine Ahnung. 😉

JustNobody hat gesagt.:
Aber nach der letzten Information würde ich mir das alles überlegen. Aktuell benötigst du 24MB Speicher. Wo siehst du Bedarf an Optimierungen?
Zum Vergrößern anklicken....
Rein von den Zahlen her klingen 24MB erstmal nach nix. Mein klappriger Läppi hat 12GB RAM verbaut, die 24MB merk ich da nicht.
Aber: Ich schätze mal daß 15MB davon Overhead sind. Mindestens, wahrscheinlich ist es noch viel mehr. Ich bin mit dem Design einfach nicht zufrieden.
Wie gesagt, es wird wahrscheinlich funktionieren. Aber ich habe da so wie es aktuell ist einfach noch zu wenig Freude dran.
Ich bin ja normalerweise wahrhaft kein Freund von Optimierungen in Hochsprachen. Aber das mag ich so noch nicht lassen.

@thecain
Es geht um das hier:
Den Sourcecode findest du ein paar Posts weiter oben auf derselben Seite.

Die 24MB beziehen sich übrigens nicht auf die RAM-Belegung, sondern auf das was ich nachher beim Serialisieren erhalte. Das will ich kleiner haben, und das optimiert die JVM auch nicht weg.


Ich stelle gerade fest: Ich brauche eine HashMap mit zwei Keys und einem Value, sowas wie HashMap<K1, K2, V>. Ich denke es wird wohl doch am Einfachsten, eine Wrapperklasse für zwei HashMaps zu schreiben.
 
So würde ich das bauen:
Java: 
package de.limdul.javaforum;

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

/** Klasse um Strings eindeutig einem Int zuzuordnen.
 * Klasse ist Thread-Safe und als Singleton implementiert.
 */
public class StringIntMapper {
	
	public static StringIntMapper INSTANCE = new StringIntMapper();
	
	private final Map<String, Integer> stringToInt = new ConcurrentHashMap<>();
	private final Map<Integer, String> intToString = new ConcurrentHashMap<>();
	
	private int counter = 0;

	private StringIntMapper() {
		// Singleton
	}
	
	/** Liefert für den String entweder den vorhanden Int-Wert oder ermittelt einen neuen.
	 */
	public int getIntValue(String input) {
		Integer value = getIntValueIntern(input);
		if (value!=null) {
			return value;
		} else {
			return computeNewIntValue(input);
		}
	}
	
	/** Liefert zu dem Schlüssel den String.
	 */
	public String getString(int key) {
		return intToString.get(key);
	}
	
	private synchronized int computeNewIntValue(String input) {
		Integer value = getIntValueIntern(input);
		if (value!=null) {
			return value;
		}
		counter++;
		stringToInt.put(input, counter);
		intToString.put(counter, input);
		return counter;
	}
	
	private Integer getIntValueIntern(String input) {
		return stringToInt.get(input);
	}
}

Insbesondere, da du ja nach Multithreading in einem Thread gefragt hast, hab ich sie mal versucht Thread-Safe zu bauen.
Getestet ist sie aber nicht 🙂
 
Generell klingt das alles immer mehr nach Datenbank. Hast Du Dir evtl. einmal überlegt, dir einfach eine relationale Datenbank anzusehen?

Dann wird dir sehr viel Arbeit abgenommen und Dein Code kann sich sehr stark reduzieren. Du hast dann in erster Linie nur noch Entity Klassen, die dann unter dem Strich in der Datenbank zu Tabelle werden (Das kann automatisch passieren so man entsprechende Frameworks wie Hibernate nutzt. Dann setzt Du in erster Linie Annotations in den Entity Klassen.

Der große Vorteil ist, dass Du da weniger an Checks zu schreiben hast und so. Integrität der Daten und sowas wird dann alles geprüft.

Aber ganz klar: Wenn die Serialisierung so eine Anforderung ist, dann ist das natürlich nichts. Ich will hier auch die Anforderungen nicht in Zweifel ziehen oder so sondern nur einen weiteren Denkanstoß geben, wohin die Reise sich auch entwickeln könnte.
 
Vielleicht habe ich es grundlegend falsch verstanden, aber wäre das nicht möglich?

Java: 
Vector<String> map = new Vector<>();

map.add("String 1");
map.add("String 2");

System.out.println(String.format("index of 'String 1': '%d'", map.indexOf("String 1")));
System.out.println(String.format("value of index '0': '%s'", map.get(0)));

System.out.println(String.format("index of 'String 2': '%d'", map.indexOf("String 2")));
System.out.println(String.format("value of index '1': '%s'", map.get(0)));
 
JustNobody hat gesagt.:
Generell klingt das alles immer mehr nach Datenbank. Hast Du Dir evtl. einmal überlegt, dir einfach eine relationale Datenbank anzusehen?
Zum Vergrößern anklicken....
Nein, an eine Datenbank hab ich tatsächlich noch nicht gedacht. Das wäre vielleicht ein einfacher Weg, allerdings klingt mir das nach sehr großem Geschütz für sehr kleines Getier. Die Lebensdauer dieser Zuordnung, die ich haben will, ist relativ kurz. Dafür eine Datenbank aufzuziehen...hm.

Aber ich denke, ich kann meine Anforderungen jetzt konkreter spezifizieren als gestern Abend.
Was ich brauche ist etwas Map<K1, K2, V>-artiges, wobei Key1 und Key2 ODER-verknüpft sein sollen. D.h. ich will z.B. zwei Methoden: V getForKey1(K1 key) und V getForKey2(K2 key) und jedes Mal das Valueobjekt erhalten. Genauso für Remove, usw.

Ich habe jetzt einige Implementierungen von Maps und Tables gefunden, aber diese benötigen zwingend beide Keys oder liefern eine ganze Spalte zurück. Ich habe mal etwas mit Konstruktionen mit mehreren Maps herumgespielt, aber irgendwo fehlte immer etwas. Entweder habe ich keine Möglichkeit gefunden das komplete Tupell zu löschen, oder ähnliches.

Ich habe allerdings ein paar oberflächliche Informationen gefunden, wie Maps arbeiten - gar nich so einfach. Z.B. habe ich keine Ahnung, was ein Rot-Schwarz-Baum ist. Wie gesagt - ich bin kein Informatiker.

Ich glaube aber, das Prinzip etwas verstanden zu haben. Man sortiert die Objekte nach ihrem Hash, und anhand des Hashes sortiert man in "Haufen" vor. Z.B. kann man in fünf Objekthaufen einteilen, je nachdem was Hash modulo fünf ergibt ein anderer Haufen.

Oder, ein ähnliches Prinzip (oder gar dasselbe?): Alle Objekte werden nach ihrem Hash sortiert. Soll ein Objekt gesucht werden, schaue ich, welchen Hash das mittelste Objekt hat und vergleiche diesen mit dem Hash des zu suchenden Objekts. Ist der Hash kleiner, suche ich in der unteren Hälfte auf die gleiche Weise weiter, ist er größer in der oberen Hälfte, usw.

Wie richtig liege ich damit?
 
Einfach mit beiden Keys einmal in die Map hinzufügen oder 2 Maps pflegen...

Eine Map hat eine Komplexität im get von O(1). Da wird nichts "gesucht". In einem Haufen, wie du ihn nennst, ist bei einem optimalen Hashing genau 1 Wert, auf den direkt zugegriffen werden kann.
 
thecain hat gesagt.:
Einfach mit beiden Keys einmal in die Map hinzufügen oder 2 Maps pflegen...
Zum Vergrößern anklicken....
Ja, wenn das so einfach wäre...kleines Beispiel:

Java: 
HashMap<KeyClass1, ValueClass> key1map;
HashMap<KeyClass2, ValueClass> key2map;


ValueClass remove(KeyClass1 key){
    //Wie möchte man das zugehörige Tupel in key2map entfernen?
    return key1map.remove(key);
}
 
Das Problem lässt sich lösen, indem Du im Value noch die Keys hast. Dies ist oft der Fall (Dann hat eine Entity eine Id und dann von mir aus einen Namen. Also kannst Du beim Löschen den Wert heraus suchen und dann über die Keys entfernen.

Wenn Du das nicht hast, dann kannst Du dir das natürlich jederzeit selbst basteln. So eine Verwaltung würde ich in der Regel in einer Klasse sauber kapseln. Dann wäre der gespeicherte Wert halt eine innere Klasse, die Key1, Key2 und Value speichert. Nach außen tritt diese Klasse nicht in Erscheinung.

So Key1 und Key2 unterschiedliche Typen haben, läuft es auf zwei Maps hinaus würde ich sagen.

Dann hätte man eine Klasse, die man universell halten kann, indem man Generics nutzt. Dann hat man K1, K2 und V als Generische Typen.
Intern dann zwei HashMaps mit K1, Value und K2,Value und die interne Value Klasse, die K1, K2 und V als generische Typen übernimmt und dann halt K1 key1, K2 key2 und V value als Instanzvariablen hat. HashCode und Equals kann man außen vor lassen, da diese nicht als Key genutzt wird. (Wobei z.B. mit Lombok das auch kein Thema wäre. @Data,@NoArgsConstructor und @AllArgsConstructor wäre so mein Ansatz.)
Methoden wären dann halt add(K1, K2, V) welches dann eine Value Instanz erzeugt mit den Parametern und das dann in die beiden Maps packt.
remove und so müsste dann halt das Value element suchen und dann aus beiden Maps löschen.

Was mir beim schnellen herunter schreiben gerade nicht gefällt ist: K1 und K2 müssen ja nicht zwingend unterschiedlich sein. Daher haut das Überladen vermutlich nicht hin. Zwei Methoden remove(K1) / remove(K2) wären schön. Aber so wird es ggf. auf removeKey1(K1) und removeKey2(K2) werden müssen.... Aber so einen Fall hatte ich bisher nicht, daher habe ich da keine praktischen Erfahrungen.
 
Ah...du meinst so in etwa?

Java: 
public class DoubledHashMap<K1, K2, V>{
    private class Tupel<K1, K2, V>{
        K1 k1;
        K2 k2;
        V v;
    }
      
    private HashMap<K1, Tupel> key1Map;
    private HashMap<K2, Tupel> key2Map;
}

Ja, doch, das könnte funktionieren. Danke.

Nachtrag:
Das funktioniert ja ganz famos. 🙂

Java: 
public class SynchronizedDoubleKeyHashmap<K1, K2, V> {
    private class Tupel{
        K1 k1;
        K2 k2;
        V v;
       
        public Tupel(K1 k1, K2 k2, V v) {
            this.k1 = k1;
            this.k2 = k2;
            this.v = v;
        }
    }
   
    private HashMap<K1, Tupel> key1Map;
    private HashMap<K2, Tupel> key2Map;

    public SynchronizedDoubleKeyHashmap() {
        key1Map = new HashMap<>();
        key2Map = new HashMap<>();
    }
   
    synchronized void put(K1 k1, K2 k2, V v){
        Tupel tupel = new Tupel(k1, k2, v);
        key1Map.put(k1, tupel);
        key2Map.put(k2, tupel);
    }
   
    synchronized V getForK1(K1 key){
        return key1Map.get(key).v;
    }
   
    synchronized V getForK2(K2 key){
        return key2Map.get(key).v;
    }
   
    synchronized V removeWithK1(K1 key){
        Tupel tupel = key1Map.remove(key);
        key2Map.remove(tupel.k2);
        return tupel.v;
    }
   
    synchronized V removeWithK2(K2 key){
        Tupel tupel = key2Map.remove(key);
        key1Map.remove(tupel.k1);
        return tupel.v;
    }
   
    synchronized boolean isEmpty(){
        return key1Map.isEmpty() & key2Map.isEmpty();
    }
}
 
Zuletzt bearbeitet:
JustNobody hat gesagt.:
Als im einem anderen Thread Strin.intern() missbraucht wurde, hatte ich auch mal geschaut, was für sinnvolle Anwendungen es gibt und da bin ich über einen Fall gestolpert: da wurden nur String.intern() Werte in einigen Feldern gespeichert, weil so einiges an Speicher gespart wurde (laut der Person, die das gemacht hat). Mir fällt es schwer das zu glauben, aber wenn es sehr extrem war mit wenigen unterschiedlichen Strings, dann kann das eine Lösung sein.
Zum Vergrößern anklicken....
Spart in alten JVMs schon etwas Speicher, bei neueren (seit Java 8?) passiert das aber auch einfach automatisch mit String Deduplication.
 
thecain hat gesagt.:
Ist K2 nicht die Value? wenn du Integer auf String und zurück mappst?
Zum Vergrößern anklicken....
Nein...das war im Ausgangspost noch mein Plan, aber Strukturen (ein String ist z.B. der Name welchen Feldes von welcher Klasse?) dann abzubilden wäre mir zuviel Frickelarbeit gewesen. Deswegen kommen da noch zwei oder drei Klassen dazu, sodaß ich auch noch andere Objekte mitverlinken muß.

Der Grund ist einfach, daß ich NACH der Serialisierung durchgeführte Refakturierungen nachziehen können will.
 
Ja, genau so war es gemeint. Statt Tupel ist es aber eigentlich ein Tripel, oder? Aber schon deutlich besserer Name als mein Value.

@mrBrown danke für den Hinweis. Ich war ehrlich gesagt schon etwas über diese Anwendung überrascht.... auf die Idee muss man erst einmal kommen - aber man lernt ja nie aus 🙂
 
Oh ja, man sollte erst recherchieren und dann schreiben. Das würde so Blamagen vermeiden. 🙂

Der Begriff Tupel wird in der Informatik für geordnete Wertesammlungen (eindimensionale Arrays) und – insbesondere in der relationalen Algebra – als Synonym für Datensatz verwendet.
Zum Vergrößern anklicken....


Also von Dir vollkommen richtig benutzt und war mein Fehler, da ich als Tupel nur eine vorhandene Klasse mit genau 2 Elementen vor Augen hatte.
 
Naja...das war Zufall meinerseits, genau wußte ich es ja auch nicht. Tupel habe ich gewählt weil ich mir nicht sicher war, ob es Tripel als Begriff überhaupt gibt. Ich hab da auch ehrlich gesagt nicht sehr viel nachgedacht, bevor du gefragt hast.

Auf jeden Fall danke ich für die Nachfrage und den Denkanstoß.
 
Guten Abend allerseits

Ich werd gerade leicht wahnsinnig...findet jemand den Fehler? Meine Klasse sieht momentan etwa so aus:
Java: 
public class SynchronizedDoubleKeyHashmap<K1, K2, V> {
    private class Tupel{
        K1 k1;
        K2 k2;
        V v;
       
        private Tupel(K1 k1, K2 k2, V v) {
            this.k1 = k1;
            this.k2 = k2;
            this.v = v;
        }
    }
   
    private HashMap<K1, Tupel> key1Map;
    private HashMap<K2, Tupel> key2Map;

    SynchronizedDoubleKeyHashmap() {
        key1Map = new HashMap<>();
        key2Map = new HashMap<>();
    }
   
    private boolean containsKey1(K1 key1){
        return key1Map.containsKey(key1);
    }
   
    private boolean containsKey2(K2 key2){
        return key2Map.containsKey(key2);
    }
   
    private void removeTupel(K1 k1, K2 k2){
        key1Map.remove(k1);
        key2Map.remove(k2);
    }

    synchronized void put(K1 k1, K2 k2, V v){
        if(containsKey1(k1) | containsKey2(k2)){
            removeTupel(k1, k2);
        }
        Tupel tupel = new Tupel(k1, k2, v);
        key1Map.put(k1, tupel);
        key2Map.put(k2, tupel);
    }
   
    synchronized V getForK1(K1 key){
        return key1Map.get(key).v;
    }
   
    synchronized V getForK2(K2 key){
        return key2Map.get(key).v;
    }
   
    synchronized V removeWithK1(K1 key){
        Tupel tupel = key1Map.remove(key);
        key2Map.remove(tupel.k2);
        return tupel.v;
    }

    synchronized V removeWithK2(K2 key){
        Tupel tupel = key2Map.remove(key);
        key1Map.remove(tupel.k1);
        return tupel.v;
    }
   
    synchronized boolean isEmpty(){
        return key1Map.isEmpty() & key2Map.isEmpty();
    }

    @Override
    public boolean equals(Object obj) {
        if(obj instanceof SynchronizedDoubleKeyHashmap){
            SynchronizedDoubleKeyHashmap otherMap = (SynchronizedDoubleKeyHashmap) obj;
           
            return this.key1Map.equals(otherMap.key1Map) &&
                    this.key2Map.equals(otherMap.key2Map);
        }
        return false;
    }
}

Für diese Klasse gibt es nun einen Unittest, und folgender Testcase schlägt ständig fehl - ich verstehe nicht, warum. Sieht jemand das Problem?

Java: 
@Test
    public void testEquals() {
        SynchronizedDoubleKeyHashmap<String, Integer, String> instance, otherMap;
        String key1a, key1b;
        Integer key2a, key2b;
        String valueA, valueB;
        
        System.out.println("equals");
        
        key1a = "Some key";
        key1b = "Some other key";
        key2a = 23;
        key2b = 777;
        valueA = "Some value";
        valueB = "Some other value";
        
        instance = new SynchronizedDoubleKeyHashmap<>();
        instance.put(key1a, key2a, valueA);
        instance.put(key1b, key2b, valueB);
        
        otherMap = new SynchronizedDoubleKeyHashmap<>();
        otherMap.put("Different Key", key2a, valueA);
        otherMap.put(key1b, key2b, valueB);
        assertFalse(instance.equals(otherMap));
        
        otherMap = new SynchronizedDoubleKeyHashmap<>();
        otherMap.put(key1a, 999, valueA);
        otherMap.put(key1b, key2b, valueB);
        assertFalse(instance.equals(otherMap));
        
        otherMap = new SynchronizedDoubleKeyHashmap<>();
        otherMap.put(key1a, key2a, "Different Value");
        otherMap.put(key1b, key2b, valueB);
        assertFalse(instance.equals(otherMap));
        
        otherMap = new SynchronizedDoubleKeyHashmap<>();
        otherMap.put(key1a, key2a, valueA);
        otherMap.put(key1b, key2b, valueB);
        assertTrue(instance.equals(otherMap));        //Fehler, equals() liefert hier false
    }
 
Tupel müsste doch auch ein equals und hashcode implementieren

Und noch 2 Tipps:

Ich würde Test immer 3 stufig aufbauen. arrange - act - assert. Dann ein neuer Test. nicht immer ändern und neu asserten.

Zudem, wenn equals überschrieben wird, immer auch hashcode überschreiben.
 
Dein Tupel hat kein equals.

Da Du beim Insert immer ein neues Tupel erzeugst haben die HashMaps zwar gleiche Keys, aber unterschiedliche Tupel.
 
Du hast übrigens in der Map überall nur die bitweisen Und/Oder Operatoren verwendet - da sollten mit Sicherheit aber die logischen sein (also && anstelle von & verwenden und || anstelle von |)
 
Oh man...ja, Tupel und equals, sicher...

thecain hat gesagt.:
Zudem, wenn equals überschrieben wird, immer auch hashcode überschreiben.
Zum Vergrößern anklicken....
Hm...warum? Ich habe mich schon über die Autofunktion gewundert, die equals() und hashcode() gleichzeitig überschreibt, mich darüber aber eher immer gewundert. Daß sich die JVM um den Hash kümmert war mir bisher immer sehr recht.
Welchen Hintergrund hat das?
 
Es muss gelten: Wenn equals() wahr ist, dann muss der Hashcode gleich sein.
(Wenn equals nicht wahr ist, dann ist der hashcode natürlich egal.)

Hintergrund ist, wie der Hashcode genutzt wird bzw. genutzt werden kann. Bestes Beispiel ist die HashMap. Für jeden Key wir der HashCode genommen und dann auf Basis des HashCodes der Key abgelegt (z.B. in einem Array aus Listen mit Länge n und hashcode % n wäre die Position im Array.) Wenn Du nun zwei Instanzen hast, die gleich sind aber unterschiedliche HashCodes hast, dann kannst Du den Key über die zweite Instanz nicht wieder auffinden, weil an der falschen Stelle gesucht würde.

Generell kann man sich z.B. Lombok ansehen. Das nutze ich in der Regel um gewisse Dinge zu bauen. Dann wird sowas relativ einfach ein

Code: 
@Data
@AllArgsConstructor
private class Tupel {
        K1 k1;
        K2 k2;
        V v;
}

@Data beinhaltet mehrere Annotations: Getter, Setter, EqualsAndHashcode, ToString und RequiredArgsConstructor

Falls Du das anschauen möchtest: https://projectlombok.org/

Lombok hat den großen Vorteil, dass es nur eine Compile-Zeit Abhängigkeit ist (Also man braucht es später nicht mehr) und es bietet ein "Delombok", das einem den Code als Code erzeugt, so dass man jederzeit Lombok als Abhängigkeit wieder los werden kann.
 
BTW: Statt Lombok bieten sich da auch Records an, noch kürzer und ohne externe Abhängigkeit 🙂
Java: 
private record Tupel(K1 k1, K2 k2, V v) {}
 
mrBrown hat gesagt.:
BTW: Statt Lombok bieten sich da auch Records an, noch kürzer und ohne externe Abhängigkeit 🙂
Java: 
private record Tupel(K1 k1, K2 k2, V v) {}
Zum Vergrößern anklicken....
So man Java 14 nutzen kann: Auf jeden Fall....

Wenn man so ein armes Schwein ist, das noch mit Java 8 arbeiten darf, dann wünscht man sich 11 und träumt noch nicht einmal von Records 🙂
 
Mal eine Frage: Wie würdet ihr einen Hashcode für die Tupel-Klasse implementieren?

Ich hätte als Vorschlag z.B.:
return k1 + 2*k2 + 3*v;
Ich bin mir aber nicht wirklich sicher, ob das nicht rasch zu Kollisionen führen kann. Und was ist mit Überläufen, wenn k2 oder v mal einen recht großen Hash mitbringen?
 
Hashcodes statt addieren einfach per xor verbinden ... das mit der Multiplikation kann man durch ein shiften ersetzen. Ein *2 ist ein shift um eins. Du könntest also prinzipiell dann ein Wert um 1 und den anderen um 2 Bit verschieben.

Das wäre eine Idee, die denkbar wäre.
 
Der Algorithmus aus Effective Java bietet sich da an.
result mit dem Hashcode des ersten Felds initialisieren, für jedes weitere Feld dann result=31*result+Hashcode des Feldes
 
Hm...meinst du stattdessen das: [URL='https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html#hashCode-java.lang.Object:A-']Arrays.hashCode(Object[])[/URL]? Ups, später Abend...ja, das ist nicht dasselbe. (Auch wenn der Test damit funktioniert...)
 
White_Fox hat gesagt.:
Auch wenn der Test damit funktioniert...
Zum Vergrößern anklicken....
Das liegt dann wohl eher an dem (schlechten) Test. Wie gesagt: Der hashCode ist überhaupt nicht stabil - und schon gar nicht für gleiche Objekte auch gleich.
Erzeuge mal ein Objekt, speichere es dir in einer Variablen und rufe dann zweimal hintereinander auf demselben unveränderten Objekt diese hashCode() Methode auf und lasse dir das Ergebnis ausgeben.
 
White_Fox hat gesagt.:
Ich sehe gerade, ich habe nicht mehr gesehen was ich da gestern eingefügt habe. Eigentlich meinte ich Arrays.hashcode({k1, k2, v}).
Zum Vergrößern anklicken....

Dein Arrays.hashCode entspricht dem Objects.hash(....) Aufruf, nur eben erstellst Du das Array da selbst und bei dem Objects,hash Aufruf erstellt es der Compiler aus den Parametern ...

Java: 
   /**
    * Generates a hash code for a sequence of input values. The hash
    * code is generated as if all the input values were placed into an
    * array, and that array were hashed by calling {@link
    * Arrays#hashCode(Object[])}.
    *
    * <p>This method is useful for implementing {@link
    * Object#hashCode()} on objects containing multiple fields. For
    * example, if an object that has three fields, {@code x}, {@code
    * y}, and {@code z}, one could write:
    *
    * <blockquote><pre>
    * &#064;Override public int hashCode() {
    *     return Objects.hash(x, y, z);
    * }
    * </pre></blockquote>
    *
    * <b>Warning: When a single object reference is supplied, the returned
    * value does not equal the hash code of that object reference.</b> This
    * value can be computed by calling {@link #hashCode(Object)}.
    *
    * @param values the values to be hashed
    * @return a hash value of the sequence of input values
    * @see Arrays#hashCode(Object[])
    * @see List#hashCode
    */
    public static int hash(Object... values) {
        return Arrays.hashCode(values);
    }

jdk8/jdk8/jdk: 687fd7c7986d src/share/classes/java/util/Objects.java

hg.openjdk.java.net hg.openjdk.java.net
 
So, mal ein kleines Update:
Ich habe endlich - es war doch weitaus mehr Arbeit als gedacht - die Normalisierung fertig. Performancetest sagt zum Speicherbedarf:
Vor der Normalisierung: 23.403.357 Bytes
Nach der Normalisierung: 12.459.349 Bytes

Unerwarteterweise wurde auch die Ausführungszeit erheblich beeinflußt. Einige Dinge dauern ziemlich genau halb so lange wie vorher, manche doppelt so lange. Die mittlere Dauer eines Testlaufs (hh:mm:ss:SSS):
Vor der Normalisierung: 00:01:10:065
Nach der Normalisierung: 00:00:12:278

Ich hätte eher erwartet daß sich die Testzeit etwas verlängert.
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Collection<Strings> - Liste von Strings verwalten
Antworten: 9
Collection#retainAll(Collection<?> c)
Antworten: 3
Collection in einer Collection
Antworten: 5
Collection in Collection
Antworten: 3
Collection in collection
Antworten: 6

Zurück
Oben