Hashmap richtig bauen, die Tripel auf Zahl abbildet?

[berndoa]

Hallo,
ich habe einen mhrere Klassen umspannenden Code, bei dem ein Problem rund um eine Hashmap auftaucht:
Ich will letztlich in einer Hashmap alle möglichen Kombinationen aus 3 Zahlen, wobei die Zahlen aus 1-49 kommen und nichts doppelt vorkommt,
bilden und sie abzählen.
Die Hashmap soll dann einer gegebenen 3er Kombi ihre "Position" in der Gesamtliste angeben.
Halt einfach die Tripel durchzählen und die Hashmap gibt mir zu einem Tripel seine Listenposition an.

Habe nun die Codeteile

    HashMap<Byte[], Short> TripleToCode = new HashMap<Byte[], Short>();

und

    public TripleList() {
        short i = 0;
        // i1=1 bis 47 i2=i1+1 bis 48 i3=i2+1 bis 49 von 1
        for (byte i1 = 1; i1 <= 47; i1++) {
            for (byte i2 = (byte) (i1 + 1); i2 <= 48; i2++) {
                for (byte i3 = (byte) (i2 + 1); i3 <= 49; i3++) {

                    System.out.println("i1,i2,i3=(" + i1 + "," + i2 + "," + i3 + ") with position " + i + "!");
                    TripleToCode.put(new Byte[] { i1, i2, i3 }, i);
                    used[i] = 1;
                    i++;

                }
            }
        }
    }

Die 3 fache for Schleife soll einfach systematisch alle Tripel durchgehen, das mitlaufende i gibt an das wievielte Tripel gerade gebaut wird.
Und das Tripel und i wird eben als key-value Paar in die Hashmap gepackt.

Nun nutze ich anderswo, natürlich nach dem obige Sachen ausgeühfrt wurden,einen Abschnitt

    public void fillList() {
        NumberGenerator numg = new NumberGenerator(6, 49);
        for (int i = 0; i < connections.length; i++) {
            // sixTupel
            byte[] b = numg.getNumber();
            Connection c = connections[i];

            for (byte i1 = 0; i1 < b.length - 2; i1++) {
                for (byte i2 = (byte) (i1 + 1); i2 < b.length - 1; i2++) {
                    for (byte i3 = (byte) (i2 + 1); i3 < b.length; i3++) {
                        //System.out.println("i="+i+", b(i1,i2,i3)="+b[i1]+","+ b[i2]+","+ b[i3]);
                        c.add(tripleList.TripleToCode.get(new Byte[] { b[i1], b[i2], b[i3] }));
                    }
                }
            }
            c.list.trimToSize();
        }
    }

zur Erklärung:
Es gibt eine Array mit Connections, deren Details sind auch eher unwichtig gerade.
Es wird jedenfalls in jedem Durchlauf der äussersten Schleife, also für jedes i,
mittels des

            byte[] b = numg.getNumber();

eine 6 stellige Zahl gezogen.
Mit den 3 verschachtelten for Schleifen werden dann über die Indizes i1,i2,i3
dann 3 zahlen aus diesen 6 genommen und zu einem eigenen Byte[] Array zusammen gefasst.

Und nun soll im Befehl

                        c.add(tripleList.TripleToCode.get(new Byte[] { b[i1], b[i2], b[i3] }));

eben mit ursprünglich erwähnter Hashmap zu diesem Tripel dessen Listenpositionszahl ermittelt werden und dem c Objekt hinzugefügt werden.

Problem nur am Ende:
Offensichtlich klappt das hinzufügen auch schon, nur gibt die Hashmap zu den übergebenen byte[3] immer nur null zurück, kurzum die .get(...) Methode der Hashmap findet angeblich nix!


Meine Vermutung ist dass die hashmap, um für einen EIngabewert zu gucken ob er ein Schlüssel, natürlich nicht die Inhalte des Arrays vergleicht sonderntidiotischerweise den Hashcode des byte[] Objekts.
Der natürlich nicht gleich ist weil die Arrays ja separat erzeugt wurden und "nur" die gleichen Werte beinhalten.
Frage wäre nun, wie kann ich das lösen?
Kann ich der Hashmap irgendwie vorschreiben wie sie eine EIngabe mit Shclüsseln vergleicht, dass sie bei 2 Arraysw die eben nicht anhand irgendwelcher esoterischer Hashcodes vergleicht sondern anhand ihrer Elemente?

 

[KonradN]

Das kann so nicht funktionieren, da zwei Arrays nur gleich sind, wenn die Referenzen gleich sind.

Mach dafür eine Klasse bei der du equals und HashCode überschreibst.

Und so Probleme immer im kleinen Ausprobieren. Du kannst einfach einen Vode schreiben, der

• Die HashMap anlegt
• ein Element einfügt
• dieses Element wieder abfragt. (Wieder mit einem new Konstrukt)

Schon wird aus einer Vermutung eine Bestätigung.

Und gewöhn Dir an, mit Klassen zu arbeiten. Dieses Agieren mit komplexen Basistypen macht Code unlesbar und unwartbar.

 

[Neumi5694]

Du musst manchmal einfach nur genau das machen, was du dir als Aufgabe gestellt hast.
Ein Tupel aus verschiedenen Zahlen, immer aufsteigend sortiert? Das nennt sich Treeset. Welche Länge es hat, bestimmst du unterm Strich ja beim Befüllen.
TreeSet bietet dann auch schon gleich die passende Equals-Methode.

Da es sich aber mal wieder um dein Lottoproblem handelt mit stark eingeschränktem Zahlenraum, wär's sinnvoller, eine Long-Zahl mit 3 gesetzten Bits zu verwenden anstatt des Arrays (oder eben des TreeSets).

Zu deinen Speicherproblemen: Implementier das Ganze erst mal für 6 aus 20.
Dann merkst du als erstes mal, wie besch*** der Code ist, weil du an allen Ecken 49 hardcodiert drinstehen hast. Außerdem kannst du das dann auch mal testen, ohne dir Zeit in einem Rechenzentrum mieten zu müssen.

 

[berndoa]

Dann bauen wir uns halt eine Konstante wo 49 drinsteht -.-
Als gäbs keine größeren Probleme...

Das kann so nicht funktionieren, da zwei Arrays nur gleich sind, wenn die Referenzen gleich sind.

Mach dafür eine Klasse bei der du equals und HashCode überschreibst.

Und so Probleme immer im kleinen Ausprobieren. Du kannst einfach einen Vode schreiben, der

• Die HashMap anlegt
• ein Element einfügt
• dieses Element wieder abfragt. (Wieder mit einem new Konstrukt)

Schon wird aus einer Vermutung eine Bestätigung.

Und gewöhn Dir an, mit Klassen zu arbeiten. Dieses Agieren mit komplexen Basistypen macht Code unlesbar und unwartbar.

Ich bin mir nicht ganz sicher ob ich dir folgen kann was ich machen soll....
Soll ich eine Klasse bauen die von HAshmap erbt und dadrin equals und Hashcode Methode überschreiben?
Soweit ich las, sind die 2 Methoden doch mehr dazu da, 2 Hashmaps gegeneinander zu vergleichen bzw. deren Gleichheit zu testen.
Und weniger um die Elemente in der Hashmap bspw. mit eiem Element ausserhalb zu verlgeichen?

Bin mir nicht ganz siche rob ich weiß was du mit deinem Ratschlag genau meintest...

 

[KonradN]

Ich bin mir nicht ganz sicher ob ich dir folgen kann was ich machen soll....

Ein Punkt, den ich Dir ans Herz gelegt habe: Probiere so Dinge einmal schnell aus!

Die Kernfrage ist ja: Kannst Du so ein Array als Key verwenden. Also machen wir das mal schnell:

public class Test {
    public static void main(String[] args) {
        int a=1;
        int b=2;
        int c=3;

        Map<int[], String> map = new HashMap<>();

        map.put(new int[]{a, b, c}, "Hallo");
        System.out.println(map.get(new int[]{a, b, c}));
    }
}

oder - was ich hoffe, dass Du es schon machen kannst:

import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.Map;

import static org.junit.jupiter.api.Assertions.*;

public class HashMapTests {

    @Test
    public void testArrayAsKey() {
        int a=1;
        int b=2;
        int c=3;
        String value = "Hallo";

        Map<int[], String> map = new HashMap<>();

        map.put(new int[]{a, b, c}, value);
        assertEquals(value, map.get(new int[]{a, b, c}));
    }
}

==> Antwort zu der ersten Frage.

Dann muss man überlegen, was das Kernproblem ist - das können wir noch überlegen. Vermutlich sind die Keys nicht gleich. Prüfen wir das doch einfach einmal, in dem wir ein Assert hinzu fügen:

        assertAll(
                () -> assertEquals(value, map.get(new int[]{a, b, c})),
                () -> assertEquals(new int[]{a, b, c}, new int[]{a, b, c})
        );

(Nur das Assert selbst erweitert mit einer zweiten Prüfung. Kann auch ein eigenständiger Test sein, aber sowas ist Basis Verständnis von Java - das muss ich nicht wirklich testen. Daher fliegt der Test eh wieder raus.)

Ergebnis des Tests:

expected: [I@4009e306<[1, 2, 3]> but was: [I@43c1b556<[1, 2, 3]>
Comparison Failure:
Expected :[I@4009e306
Actual   :[I@43c1b556

Das Ergbnis ist klar - da muss man nichts weiter erläutern, oder?

Also taugt so ein Array nicht als Key. Somit brauche ich irgendwas, was als Key in einer Hashmap taugt. Dazu kannst Du Dir überlegen, was da gelten muss.

Und da kannst Du dann eine eigene Klasse schreiben. So eine Menge an Zahlen ist ggf. ein nTupel und da der Typ int (oder byte) sein soll, dann ein NIntTupel oder so. Das kann man dann schnell schreiben:

Dazu schreiben wir einfach eine neue Klasse:

public class NIntTupel {
    private int[] values;  
}

Das reicht natürlich nicht - wir brauchen noch ein Konstruktor sowie equals und HashCode. Also sagen wir der Entwicklungsumgebung, dass wir das beides wollen und erhalten dann:

import java.util.Arrays;

public class NIntTupel {
    private int[] values;

    public NIntTupel(int[] values) {
        this.values =  values;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        NIntTupel nIntTupel = (NIntTupel) o;
        return Arrays.equals(values, nIntTupel.values);
    }

    @Override
    public int hashCode() {
        return Arrays.hashCode(values);
    }
}

Der Konstruktor ist doof. Das Array kann ja noch nachträglich verändert werden und ich will nicht immer ein Array übergeben. Machen wir also noch eine kleine Anpassung am Konstruktor:

    public NIntTupel(int... values) {
        this.values = Arrays.copyOf(values, values.length);
    }

==> Fast fertig. Wir müssen natürlich noch schauen, ob das korrekt ist. Daher passen wir den Test noch schnell an:

import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.Map;

import static org.junit.jupiter.api.Assertions.*;

public class NIntTupelTests {

    @Test
    public void testNIntTupelAsKey() {
        int a=1;
        int b=2;
        int c=3;
        String value = "Hallo";

        Map<NIntTupel, String> map = new HashMap<>();

        map.put(new NIntTupel(a, b, c), value);
        assertAll(
                () -> assertEquals(value, map.get(new NIntTupel(a, b, c))),
                () -> assertEquals(new NIntTupel(a, b, c), new NIntTupel(a, b, c))
        );
    }
}

Jetzt fehlen natürlich ggf. noch weitere Zugriffe, die Du brauchst. Also z.B. um die Werte aus dem Array auszulesen oder die Länge zu bekommen.
Wichtig ist: Du solltest keine Setter haben, wenn Du es als Key in einer HashMap nutzen willst. Ein veränderter Key verändert den Hashcode und damit wäre ein Element nicht mehr zu finden!

Edit: Der Name ist evtl. als IntNTupel besser. Und dann hätte man ggf. noch NTupel<T> und so (wenn man das als Library bereit stellen wollte. Das fällt mir so nach dem Abschicken auf.

 

[berndoa]

Bei dem

import java.util.Arrays;

public class NIntTupel {
    private int[] values;

    public NIntTupel(int[] values) {
        this.values =  values;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        NIntTupel nIntTupel = (NIntTupel) o;
        return Arrays.equals(values, nIntTupel.values);
    }

    @Override
    public int hashCode() {
        return Arrays.hashCode(values);
    }
}

Werden da da die equals und hascode Methoden der NinTTupel Klasse überschrieben?
Oder wozu gehören die?

 

[KonradN]

Da NIntTupel nicht explizit von einer anderen Klasse erbt, erbt sie von Object. Und die equals / hashCode Methoden von Object werden überschrieben.

 

[temi]

Da NIntTupel nicht explizit von einer anderen Klasse erbt, erbt sie von Object. Und die equals / hashCode Methoden von Object werden überschrieben.

Und das ist erforderlich, damit z. B. die HashMap mit dieser Klasse korrekt arbeiten kann.

 

[Neumi5694]

Dann bauen wir uns halt eine Konstante wo 49 drinsteht -.-
Als gäbs keine größeren Probleme...

Oh, mir würden da noch einige Sachen mehr einfallen, wie z.B. ein paar standardisierte Methoden:

long toBits(int...) {}
int[] fromBits(long)

Damit hast du dann nicht mehr so oft den selben Code stehen und musst nicht so viel warten. Jetzt magst du das nicht als Problem ansehen, aber wenn du mal ein paar Jahre an einem Projekt gearbeitet hast, dann erkennst du die Vorteile.

Ich find nach wie vor die effizienteste, speichersparendste und schnellste Methode für deine Map, deine Zahlen in eine Bitmaske abzubilden.
map.get(toBits(intarray)); Dann muss die Map nur noch nach einem Long-Wert suchen.

Da du nur 14 Millionen verschiedener Long-Werte haben kannst, ließe sich das Ganze sogar noch optimieren, indem man den Index berechnet, den ein Tupel von Zahlen hat. Damit könnte man anstatt einer Map gleich ein Array verwenden und somit die Zugriffszeit minimieren.

 

[berndoa]

Oh, mir würden da noch einige Sachen mehr einfallen, wie z.B. ein paar standardisierte Methoden:

long toBits(int...) {}
int[] fromBits(long)

Damit hast du dann nicht mehr so oft den selben Code stehen und musst nicht so viel warten. Jetzt magst du das nicht als Problem ansehen, aber wenn du mal ein paar Jahre an einem Projekt gearbeitet hast, dann erkennst du die Vorteile.

Ich find nach wie vor die effizienteste, speichersparendste und schnellste Methode für deine Map, deine Zahlen in eine Bitmaske abzubilden.
map.get(toBits(intarray)); Dann muss die Map nur noch nach einem Long-Wert suchen.

Da du nur 14 Millionen verschiedener Long-Werte haben kannst, ließe sich das Ganze sogar noch optimieren, indem man den Index berechnet, den ein Tupel von Zahlen hat. Damit könnte man anstatt einer Map gleich ein Array verwenden und somit die Zugriffszeit minimieren.

Das war eigentlich nicht als Frage gemeint aber trotzdem Danke für die Antwort 🙂

Aktuell habe ich auch den Index des Tripels berechnetlasen, da zu der Zeit Konrad noch nicht geantwortet hatte.
War eine sehr nervige Kleinarbeit von hand diese 3fach Summen zu lösen.

Wird nur schwierig wenn ich 4fach, 5fach oder mehr Summen hätte (also wen ich bspw. nach 5 Richtigen suchen würde).
Weil ich da , mal von der mathematischen Heidenarbeit abgesehen, Formeln für die Summe der ersten n ^4 Zahlen oder ^5 Zahlen bräuchte, für die es vermutlich gar keine Formel gibt.


Ich bin mir nicht ganz sicher wie ich 13 millionen kombinationen in eine long Zahl reinpacken kann, ich meine, die hat doch nur 64 Stellen, oder?
Oder meisnt dud as mit, dass ich in 49 bits davon 6 Einsen unterbringe?
Hm dann nur die Frage wie ich dazu die int zahl kreiere.
Aktuell lasse ich einfach mitzählen während ich die einzelnen 6tupel oder 3tupel kreiere und speichere die laufvariable gleich ab.

 

[Neumi5694]

Das war eigentlich nicht als Frage gemeint aber trotzdem Danke für die Antwort 🙂


Ich bin mir nicht ganz sicher wie ich 13 millionen kombinationen in eine long Zahl reinpacken kann, ich meine, die hat doch nur 64 Stellen, oder?
Oder meisnt dud as mit, dass ich in 49 bits davon 6 Einsen unterbringe?
Hm dann nur die Frage wie ich dazu die int zahl kreiere.
Aktuell lasse ich einfach mitzählen während ich die einzelnen 6tupel oder 3tupel kreiere und speichere die laufvariable gleich ab.

Mit Long kann man einiges abbilden 🙂 2^64 ist ein bisserl mehr als 14 Millionen.

Anm: die 14 Millionen beziehen sich auf Sechserkombinationen. Du willst hier ja aber nur Dreierkombinationen, es gibt also nur 49 über 3 Möglichkeiten =>18424.

Es sind doch jeweils nur 3 Bits gesetzt. Du machst das doch schon seit Anfang des Projekts.
Die Int-Zahlen 2,7,12 werden abgebildet nach -> 0...0100001000010 (von rechts nach links).
Damit hat jede Kombination aus verschiedenen Integerzahlen im Bereich [1 bis 49] einen eindeutigen Long-Wert, anstatt nach einem Array mit genau diesen 3 Zahlen zu suchen suchst du eben nur nach dem einen Longwert.

Edit: Eine noch bessere Möglichkeit, aus solchen 3 Zahlen zu einem Long-Wert zu kommen, wäre
a*50*50+b*50+c
Oder, damit sie auch alle schön bitweise nebeneinander stehen (mit jeweils 6 Bits):
a*64*64+b*64+c
bzw a<<12 | b << 6 | c
Damit würde man nur 18 Bit belegen, anstatt Long würde auch Integer ausreichen. Dies klappt aber nur, weil es nur so wenige und so kleine Zahlen sind. Die Methode mit der Bitmaske erlaubt mehrere verschiedene Zahlen (bis zu 63) im Bereich von [1..63]