Collections Suche Collection, um Strings mit Indizees versehen

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?
 
K

kneitzel

Gast
Du könntest natürlich zwei Maps nutzen. Dann hättest du halt so beide Richtungen abgedeckt.
 

thecain

Top Contributor
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
 

White_Fox

Top Contributor
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:
K

kneitzel

Gast
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.
 

thecain

Top Contributor
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.
 

White_Fox

Top Contributor
Das einfach mal als mein Senf zu dem Thema in der Hoffnung, dass es hilfreich ist.
Immer gerne...ich stelle das ja gern zur Diskussion. Wie ich immer sage, ich hab doch vom Programmieren eigentlich keine Ahnung. ;)

Aber nach der letzten Information würde ich mir das alles überlegen. Aktuell benötigst du 24MB Speicher. Wo siehst du Bedarf an Optimierungen?
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.
 

LimDul

Top Contributor
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 :)
 
K

kneitzel

Gast
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.
 

sascha-sphw

Top Contributor
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)));
 

White_Fox

Top Contributor
Generell klingt das alles immer mehr nach Datenbank. Hast Du Dir evtl. einmal überlegt, dir einfach eine relationale Datenbank anzusehen?
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?
 

thecain

Top Contributor
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.
 

White_Fox

Top Contributor
Einfach mit beiden Keys einmal in die Map hinzufügen oder 2 Maps pflegen...
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);
}
 
K

kneitzel

Gast
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.
 

White_Fox

Top Contributor
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:

mrBrown

Super-Moderator
Mitarbeiter
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.
Spart in alten JVMs schon etwas Speicher, bei neueren (seit Java 8?) passiert das aber auch einfach automatisch mit String Deduplication.
 

White_Fox

Top Contributor
Ist K2 nicht die Value? wenn du Integer auf String und zurück mappst?
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.
 
K

kneitzel

Gast
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 :)
 
K

kneitzel

Gast
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.


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.
 

White_Fox

Top Contributor
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ß.
 

White_Fox

Top Contributor
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
    }
 

thecain

Top Contributor
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.
 
K

kneitzel

Gast
Dein Tupel hat kein equals.

Da Du beim Insert immer ein neues Tupel erzeugst haben die HashMaps zwar gleiche Keys, aber unterschiedliche Tupel.
 

LimDul

Top Contributor
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 |)
 

White_Fox

Top Contributor
Oh man...ja, Tupel und equals, sicher...

Zudem, wenn equals überschrieben wird, immer auch hashcode überschreiben.
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?
 
K

kneitzel

Gast
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.
 

mrBrown

Super-Moderator
Mitarbeiter
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) {}
 
K

kneitzel

Gast
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) {}
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 :)
 

White_Fox

Top Contributor
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?
 
K

kneitzel

Gast
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.
 

mrBrown

Super-Moderator
Mitarbeiter
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
 

White_Fox

Top Contributor
@thecain
Ich bin wirklich begeistert.
Java:
@Override
public int hashCode() {
    Object[] members = new Object[]{k1, k2, v};
    return members.hashCode();
}
 

White_Fox

Top Contributor
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...)
 

httpdigest

Top Contributor
Auch wenn der Test damit funktioniert...
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.
 
K

kneitzel

Gast
Ich sehe gerade, ich habe nicht mehr gesehen was ich da gestern eingefügt habe. Eigentlich meinte ich Arrays.hashcode({k1, k2, v}).

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);
    }

 

White_Fox

Top Contributor
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.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
M Suche nach String mit unbekannten characters Allgemeine Java-Themen 53
M Binäre Suche Allgemeine Java-Themen 6
M geometrische Suche Allgemeine Java-Themen 8
S Programm schreiben, das mir aufgrund von Schlagwörtern, die ich im Internet suche, relevante Themen sofort anzeigt. Allgemeine Java-Themen 1
I HTML / XHTML Seite nach Excel exportieren. Suche Lib Allgemeine Java-Themen 12
W Suche Ursache für NPE - woher kommt sie? (Hilfe beim Debugging) Allgemeine Java-Themen 19
O Suche Scripter für alt:V Project! Allgemeine Java-Themen 0
D Suche Quellcode! Allgemeine Java-Themen 8
O Suche Unterstützung für ein OpenSource-Projekt (grafischer Editor) Allgemeine Java-Themen 13
B Bei Email: FW / AW... - Hilfe bei String suche Allgemeine Java-Themen 21
J Suche Alternative zu Jasper Reports Allgemeine Java-Themen 4
W Collections Suche etwas Sorted-List-Artiges...hat jemand eine Idee? Allgemeine Java-Themen 13
M Suche Alternative zu JFreeChart Allgemeine Java-Themen 11
S Warmup für Lineare-Suche mit Zeitmessung Allgemeine Java-Themen 2
K OOP Suche Hilfe + Erklärung für eine Hausaufgabe Allgemeine Java-Themen 1
B Suche nach einem Testprogramm für meine BA Allgemeine Java-Themen 0
D Objekt-Suche mit mehreren optionalen Parametern Allgemeine Java-Themen 6
A NetBeans Suche Programmierer für eine Belegarbeit Allgemeine Java-Themen 11
O Suche größeres Beispiel für WebserverAnwendung mit Java Allgemeine Java-Themen 2
G Google-Suche ist nicht auslesbar?! Allgemeine Java-Themen 18
M Suche aktuelle Apache Poi Bibliothek zum Einbinden in mein Programm Allgemeine Java-Themen 2
L Suche nach CalDav Server API Allgemeine Java-Themen 0
HarleyDavidson Best Practice Suche "Container" für Modulapplikationen Allgemeine Java-Themen 0
S Suche Konzept: Korrektheit des Aufrufers feststellen Allgemeine Java-Themen 7
KaffeeFan Methoden Suche Methode um Programm kurz warten zu lassen Allgemeine Java-Themen 22
B Suche geeignete Datenstruktur Allgemeine Java-Themen 5
L Erste Schritte Suche Java Wiki System? Allgemeine Java-Themen 5
L Suche Geräte für Java SE Embedded Allgemeine Java-Themen 0
S Rekursive Suche in einem Netz Allgemeine Java-Themen 5
F Über Java Google Suche nutzen Allgemeine Java-Themen 11
A Suche Android Programmierer Allgemeine Java-Themen 0
W Suche Framework zur Prüfung von IPv4 und IPv6 Allgemeine Java-Themen 2
A Java - Suche nach Datensatz mit DateChooser Allgemeine Java-Themen 0
S Pattern.Match Suche: For Schleife einbinden und in Liste schreiben Allgemeine Java-Themen 3
M Suche Framework/API für Monitoring-Anwendung Allgemeine Java-Themen 3
F Suche kostenlose GUI für Eclipse Allgemeine Java-Themen 10
H Suche mit Wildcards und boolschen Operatoren Allgemeine Java-Themen 4
B Suche passende Datenstruktur für 2 Einträge Allgemeine Java-Themen 19
A Binäre Suche im Array mit StackOverflowError Allgemeine Java-Themen 3
T Verkettete Suche Allgemeine Java-Themen 6
S RxTx - langsame Port suche Allgemeine Java-Themen 3
D Suche Matrix Libraries Allgemeine Java-Themen 11
S Suche Dependency Injection Container Allgemeine Java-Themen 6
J Suche: Tool zum Auffinden gleichnamiger Klassen (Name und Package gleich) in unteschiedlichen JARs Allgemeine Java-Themen 5
BinaryLogic Input/Output Suche Wörterbuch-Datei Einzahl/Mehrzahl Allgemeine Java-Themen 2
A Suche Algorithmus zum Erstellen eines planaren Graphen Allgemeine Java-Themen 5
D Suche Librarys ähnlich datatables.net + Login Allgemeine Java-Themen 3
Gossi Threads Suche ein (einfaches) Beispiel Allgemeine Java-Themen 5
P Erste Schritte Suche in ArrayList mit Maps Allgemeine Java-Themen 4
F Suche Performanceoptimierung bei Stringsortierung Allgemeine Java-Themen 51
B Suche Datenquelle für lizenz-informationen Allgemeine Java-Themen 5
J Lucene suche in Json (CouchDB) Allgemeine Java-Themen 2
X Suche Softwareimplementierung von Cryptographischen Algorithmen Allgemeine Java-Themen 3
S Suche Tipps für Einstieg in JavaCC Allgemeine Java-Themen 2
R Suche in logfiles mit Lucene / Solr Allgemeine Java-Themen 2
P Suche Datenstruktur Allgemeine Java-Themen 2
M Suche Java-Projekt zum Thema Elektrotechnik Allgemeine Java-Themen 6
F Suche Begriff Allgemeine Java-Themen 2
hdi Suche Icon-Sammlung Allgemeine Java-Themen 7
G Suche "richtiges" Framework/Library Allgemeine Java-Themen 14
slawaweis Suche Klassen für Event Managment und Time Allgemeine Java-Themen 2
P Probleme mit wikipedia quellcode zur binären Suche Allgemeine Java-Themen 6
C Suche Permutationsalgo Allgemeine Java-Themen 6
E Suche nach Foto-Dummy Allgemeine Java-Themen 8
B Suche Paket zum auslesen von Metadaten von Bildern. Allgemeine Java-Themen 4
N suche globale Tastenabfrage Allgemeine Java-Themen 6
P SUCHE: gute Geo Library (freeware) Allgemeine Java-Themen 2
P Suche performante PDF Library Allgemeine Java-Themen 20
data89 Bilder mit Java prüfen - suche dringend Hilfe Allgemeine Java-Themen 8
faetzminator Regex zur Suche von "value-losen" Attributen in HTML Tags Allgemeine Java-Themen 7
S Suche im JTree nach Neuaufbau Allgemeine Java-Themen 4
W Problem bei der Suche (binarySearch) vom deutschen Sonderzeichen "ß" im einem Array Allgemeine Java-Themen 6
D Suche nach passender Datenstruktur Allgemeine Java-Themen 4
S suche library die diagramme darstellen kann Allgemeine Java-Themen 2
T Suche Anhaltspunkt für plattformübergreifende, "unique machine id" ... Allgemeine Java-Themen 12
P WebSerive Suche Allgemeine Java-Themen 15
hdi Suche nach Begriff aus der Programmierung Allgemeine Java-Themen 11
X Suche Java Klasse die Feiertage berechnen kann Allgemeine Java-Themen 2
B suche Deutsche Übersetzung für neuste Eclipse Version Allgemeine Java-Themen 6
Daniel_L Suche nach ganzen Wörtern (wholeword) in Strings? Allgemeine Java-Themen 4
G Regex-Suche nach Worten Allgemeine Java-Themen 3
Antoras Suche Projektarbeit für Gruppe mit 3 Leuten Allgemeine Java-Themen 5
G Perfomante Suche in grosser Datei Allgemeine Java-Themen 6
T Suche Tool Allgemeine Java-Themen 11
D Suche sowas wie Map nur für mehrere Werte Allgemeine Java-Themen 13
D Suche Hilfe zum Rechnerübergreifenden Dateizugriff. Allgemeine Java-Themen 3
M suche speziellen Sortieralgorithmus Allgemeine Java-Themen 3
E javax.comm: Suche eine open source Alternative zu rxtx Allgemeine Java-Themen 8
J Suche regex-Pattern fuer Liste von Zahlen zwischen 0-100 Allgemeine Java-Themen 6
T Suche den großen Calendar Thread ! Allgemeine Java-Themen 2
P Suche Benis IP/Netzwerkadresse JTExtField Allgemeine Java-Themen 2
J Suche Doku um generischen Code zu erstellen. Allgemeine Java-Themen 9
G suche Property alternative Allgemeine Java-Themen 4
C Fehler im Quellcode. Suche in einem Baum Allgemeine Java-Themen 3
S Suche Pendant zu einem VB Befehl Allgemeine Java-Themen 2
T Suche gute JAVA Steuerelemente Allgemeine Java-Themen 2
V Suche RegEx zu (gelöstem) Problem Allgemeine Java-Themen 3
B Suche Browser-Control Allgemeine Java-Themen 4
G Suche Programmierumgebung mit Appletviewer Allgemeine Java-Themen 16
G Suche kostenlosen c++ to java converter. Allgemeine Java-Themen 3

Ähnliche Java Themen

Neue Themen


Oben