Wie erstelle ich eine HashMap mit zwei Schlüsseln (Schlüsselpaar, Wert)?

118

Ich habe ein 2D-Array von Ganzzahlen. Ich möchte, dass sie in eine HashMap eingefügt werden. Ich möchte jedoch auf die Elemente aus der HashMap zugreifen, die auf dem Array-Index basieren. Etwas wie:

Für A [2] [5], map.get(2,5)das einen diesem Schlüssel zugeordneten Wert zurückgibt. Aber wie erstelle ich eine HashMap mit einem Schlüsselpaar? Oder im Allgemeinen mehrere Schlüssel: Map<((key1, key2,..,keyN), Value)so, dass ich mit get (key1, key2, ... keyN) auf das Element zugreifen kann.

EDIT: 3 Jahre nach dem Posten der Frage möchte ich noch ein bisschen mehr hinzufügen

Ich bin auf einen anderen Weg gestoßen NxN matrix.

Array-Indizes iund jkönnen auf keyfolgende Weise als einzelne dargestellt werden:

int key = i * N + j;
//map.put(key, a[i][j]); // queue.add(key); 

Und die Indizes können auf folgende Weise abgerufen keywerden:

int i = key / N;
int j = key % N;
Crocode
quelle
Eine einfache Lösung besteht darin, einen Schlüssel in einer anderen Hashmap zuzuordnen.
Mihai8
1
Bitte beantworten Sie die Frage in der Frage nicht. Ihre Bearbeitung ist interessant, Sie können sie also gerne als Antwort veröffentlichen.
Ole VV
@Crocode wow! Die Mathematik hinter der Antwort in der Bearbeitung ist schillernd. Ich frage mich nur, ob es im Allgemeinen für zwei beliebige ganze Zahlen i und j funktioniert.
Likejudo
@Crocode werden i und j durchlaufen, wenn sie Vielfache von N sind?
Likejudo

Antworten:

190

Es gibt mehrere Möglichkeiten:

2 Dimensionen

Karte der Karten

Map<Integer, Map<Integer, V>> map = //...
//...

map.get(2).get(5);

Wrapper-Schlüsselobjekt

public class Key {

    private final int x;
    private final int y;

    public Key(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Key)) return false;
        Key key = (Key) o;
        return x == key.x && y == key.y;
    }

    @Override
    public int hashCode() {
        int result = x;
        result = 31 * result + y;
        return result;
    }

}

Umsetzung equals()und hashCode()ist hier entscheidend. Dann verwenden Sie einfach:

Map<Key, V> map = //...

und:

map.get(new Key(2, 5));

Table von Guave

Table<Integer, Integer, V> table = HashBasedTable.create();
//...

table.get(2, 5);

Tableverwendet Karte der Karten darunter.

N Abmessungen

Beachten Sie das Besondere Key Klasse der einzige Ansatz ist, der auf n-Dimensionen skaliert. Sie könnten auch überlegen:

Map<List<Integer>, V> map = //...

Aber das ist aus Sicht der Leistung sowie der Lesbarkeit und Korrektheit schrecklich (keine einfache Möglichkeit, die Listengröße durchzusetzen).

Vielleicht werfen Sie einen Blick auf Scala, wo Sie Tupel und caseKlassen haben (ganze KeyKlasse durch Einzeiler ersetzen ).

Tomasz Nurkiewicz
quelle
3
Hallo, andere haben x'oder die beiden Werte, wenn sie hashCode machen. Warum benutzt du 31? Ich dachte, es hat etwas mit 32-Bit-Ganzzahlen zu tun, aber wenn ich darüber nachdenke, macht es keinen Sinn, weil x = 1 und y = 0 immer noch demselben Hashcode wie x = 0 und y = 31
pete zugeordnet sind
1
@pete Joshua Bloch empfiehlt in Effective Java ch 3. s 9.: "1. Speichern Sie einen konstanten Wert ungleich Null, z. B. 17, in einer int-Variablen namens result ...", was in Bezug auf die Kollision besser funktioniert, wenn dies der Fall ist eine Primzahl. Siehe auch: stackoverflow.com/questions/3613102/…
fncomp
2
Warum nicht anstelle des Wrapper-Schlüsselobjekts Map.Entry<K, V>als Schlüssel verwenden?
Roland
1
Was ist mit Map<Pair<Key1, Key2>, Value>?
Joaquin Iurchuk
1
Beachten Sie, dass hashCode()auch mit einer einzelnen Zeile alsObjects.hash(x,y)
xdavidliu
23

Wenn Sie Ihr eigenes Schlüsselpaarobjekt erstellen, sollten Sie sich einigen Dingen stellen.

Zunächst sollten Sie sich der Implementierung von hashCode()und bewusst sein equals(). Sie müssen dies tun.

Zweitens hashCode()stellen Sie bei der Implementierung sicher, dass Sie verstehen, wie es funktioniert. Das angegebene Benutzerbeispiel

public int hashCode() {
    return this.x ^ this.y;
}

ist tatsächlich eine der schlechtesten Implementierungen, die Sie tun können. Der Grund ist einfach: Sie haben viele gleiche Hashes! Und die hashCode()sollten int-Werte zurückgeben, die eher selten und im besten Fall einzigartig sind. Verwenden Sie so etwas:

public int hashCode() {
  return (X << 16) + Y;
}

Dies ist schnell und gibt eindeutige Hashes für Schlüssel zwischen -2 ^ 16 und 2 ^ 16-1 (-65536 bis 65535) zurück. Das passt in fast jedem Fall. Sehr selten sind Sie außerhalb dieser Grenzen.

Drittens sollten Sie bei der Implementierung equals()auch wissen, wofür es verwendet wird, und wissen, wie Sie Ihre Schlüssel erstellen, da es sich um Objekte handelt. Oft tun Sie dies unnötig, wenn Anweisungen dazu führen, dass Sie immer das gleiche Ergebnis erzielen.

Wenn Sie Schlüssel wie diesen erstellen: map.put(new Key(x,y),V);Sie werden niemals die Referenzen Ihrer Schlüssel vergleichen. Denn jedes Mal, wenn Sie auf die Karte zugreifen möchten, werden Sie so etwas tun map.get(new Key(x,y));. Daher equals()braucht man keine Aussage wieif (this == obj) . Es wird niemals auftreten.

Anstatt if (getClass() != obj.getClass()) in Ihrer equals()besseren Nutzung if (!(obj instanceof this)). Es gilt auch für Unterklassen.

Das einzige, was Sie vergleichen müssen, ist tatsächlich X und Y. Also das Beste equals() Implementierung in diesem Fall wäre also:

public boolean equals (final Object O) {
  if (!(O instanceof Key)) return false;
  if (((Key) O).X != X) return false;
  if (((Key) O).Y != Y) return false;
  return true;
}

Am Ende sieht Ihre Schlüsselklasse also so aus:

public class Key {

  public final int X;
  public final int Y;

  public Key(final int X, final int Y) {
    this.X = X;
    this.Y = Y;
  }

  public boolean equals (final Object O) {
    if (!(O instanceof Key)) return false;
    if (((Key) O).X != X) return false;
    if (((Key) O).Y != Y) return false;
    return true;
  }

  public int hashCode() {
    return (X << 16) + Y;
  }

}

Sie können Ihre Dimensionsindizes Xund Yeine öffentliche Zugriffsebene angeben, da diese endgültig sind und keine vertraulichen Informationen enthalten. Ich bin mir nicht 100% sicher, ob die privateZugriffsebene in irgendeiner korrekt funktioniert beim Casting Objectauf a FallKey .

Wenn Sie sich über das Finale wundern, erkläre ich alles als endgültig, welcher Wert auf Instanzen gesetzt ist und sich nie ändert - und daher eine Objektkonstante ist.

chrixle
quelle
7

Sie können keine Hash-Map mit mehreren Schlüsseln haben, aber Sie können ein Objekt haben, das mehrere Parameter als Schlüssel verwendet.

Erstellen Sie ein Objekt namens Index, das einen x- und einen y-Wert annimmt.

public class Index {

    private int x;
    private int y;

    public Index(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int hashCode() {
        return this.x ^ this.y;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Index other = (Index) obj;
        if (x != other.x)
            return false;
        if (y != other.y)
            return false;
        return true;
    }
}

Dann müssen Sie HashMap<Index, Value>Ihr Ergebnis erhalten. :) :)

Brad
quelle
4
Sie müssen außer Kraft zu setzen hashCodeund equals.
Tom Hawtin - Tackline
4
Die HashCode-Implementierung unterschied nicht zwischen (2,1) und (1,2)
user1947415
1
Das ist eine Kollision. Hashcode muss nicht für jedes Objekt einen anderen Wert garantieren. @ user1947415
Ajak6
6

Implementiert in MultiKeyMap mit allgemeinen Sammlungen

Mike
quelle
@ Wilson Ich habe den Link jetzt repariert und auf Peer Review gewartet
Computingfreak
@computingfreak scheint eine positive Sicht durchgekommen zu sein. Hurra! NB das ist meiner Meinung nach die beste Antwort. Es sei denn, Sie möchten Stunden damit verbringen, mit den erfahrenen Apache-Ingenieuren um einige sehr nützliche (wie immer), aber letztendlich alltägliche Funktionen zu konkurrieren.
Mike Nagetier
4

Zwei Möglichkeiten. Verwenden Sie entweder einen kombinierten Schlüssel:

class MyKey {
    int firstIndex;
    int secondIndex;
    // important: override hashCode() and equals()
}

Oder eine Karte der Karte:

Map<Integer, Map<Integer, Integer>> myMap;
Cyrille Ka
quelle
2
Verwenden Sie eine Karte mit Karten nur, wenn Sie sich nicht für die Leistung oder die Speichernutzung interessieren (dh die Karte ist klein) oder wenn es viele Schlüssel mit demselben ersten Index gibt - da diese Lösung bedeutet, den Overhead eines HashMap-Objekts zu bezahlen jeder einzelne eindeutige erste Index.
BeeOnRope
1
Um diese Antwort zu verbessern, finden Sie hier Informationen zu Überschreibungen hashCodeund equalsMethoden.
Pshemo
2

Verwenden Sie a Pairals Schlüssel für die HashMap. JDK hat kein Paar, aber Sie können entweder ein Bibliothekar eines Drittanbieters wie http://commons.apache.org/lang verwenden oder ein eigenes Paar schreiben.

MrSmith42
quelle
1

Erstellen Sie eine Wertklasse, die Ihren zusammengesetzten Schlüssel darstellt, z.

class Index2D {
  int first, second;

  // overrides equals and hashCode properly here
}

Achten Sie darauf, zu überschreiben equals()und hashCode()richtig. Wenn das nach viel Arbeit aussieht, können Sie einige fertige generische Container in Betracht ziehen, wie sie beispielsweise Pairvon Apache Commons bereitgestellt werden.

Es gibt hier auch viele ähnliche Fragen mit anderen Ideen, wie beispielsweise die Verwendung von Guavas Tabelle , obwohl die Schlüssel unterschiedliche Typen haben können, was in Ihrem Fall (in Bezug auf Speichernutzung und Komplexität) zu viel des Guten sein kann , da ich verstehe, dass Ihre Schlüssel beide Ganzzahlen sind.

BeeOnRope
quelle
1

Wenn es sich um zwei Ganzzahlen handelt, können Sie einen schnellen und schmutzigen Trick ausprobieren: Map<String, ?>Verwenden Sie den Schlüssel als i+"#"+j.

Wenn der Schlüssel i+"#"+jmit j+"#"+itry identisch ist min(i,j)+"#"+max(i,j).

Arutaku
quelle
2
Wirklich schlechte Idee. Erstens ist es einfach schlecht. Zweitens wird diese Technik für andere Typen kopiert, bei denen unterschiedliche Schlüssel Stringmit komischen Konsequenzen auf denselben abgebildet werden können .
Tom Hawtin - Tackline
Es scheint mir , dass , i#j = j#iwenn i == jso die Verwendung min/maxTrick nicht.
Matthieu
1
@Matthieu was ist der Unterschied zwischen 5#5und 5#5vertauscht?
Enrey
@enrey Keine. Darauf habe ich hingewiesen. Es hängt wirklich von dem Wissen ab, das Sie über Ihre Schlüssel haben.
Matthieu
@Matthieu aha Ich verstehe was du meinst. Ich denke, was @arutaku bedeutete, war, wenn Sie 5#3den gleichen Hash wie haben möchten 3#5, dann verwenden Sie min / max, um 3#5in dieser Reihenfolge durchzusetzen .
Enrey
1

Sie können hierfür auch die Implementierung der Guaventabelle verwenden .

Die Tabelle stellt eine spezielle Zuordnung dar, in der zwei Schlüssel kombiniert angegeben werden können, um auf einen einzelnen Wert zu verweisen. Es ähnelt dem Erstellen einer Karte mit Karten.

//create a table
  Table<String, String, String> employeeTable = HashBasedTable.create();

  //initialize the table with employee details
  employeeTable.put("IBM", "101","Mahesh");
  employeeTable.put("IBM", "102","Ramesh");
  employeeTable.put("IBM", "103","Suresh");

  employeeTable.put("Microsoft", "111","Sohan");
  employeeTable.put("Microsoft", "112","Mohan");
  employeeTable.put("Microsoft", "113","Rohan");

  employeeTable.put("TCS", "121","Ram");
  employeeTable.put("TCS", "122","Shyam");
  employeeTable.put("TCS", "123","Sunil");

  //get Map corresponding to IBM
  Map<String,String> ibmEmployees =  employeeTable.row("IBM");
slisnychyi
quelle
1

Sie können Ihr Schlüsselobjekt folgendermaßen erstellen:

öffentliche Klasse MapKey {

public  Object key1;
public Object key2;

public Object getKey1() {
    return key1;
}

public void setKey1(Object key1) {
    this.key1 = key1;
}

public Object getKey2() {
    return key2;
}

public void setKey2(Object key2) {
    this.key2 = key2;
}

public boolean equals(Object keyObject){

    if(keyObject==null)
        return false;

    if (keyObject.getClass()!= MapKey.class)
        return false;

    MapKey key = (MapKey)keyObject;

    if(key.key1!=null && this.key1==null)
        return false;

    if(key.key2 !=null && this.key2==null)
        return false;

    if(this.key1==null && key.key1 !=null)
        return false;

    if(this.key2==null && key.key2 !=null)
        return false;

    if(this.key1==null && key.key1==null && this.key2 !=null && key.key2 !=null)
        return this.key2.equals(key.key2);

    if(this.key2==null && key.key2==null && this.key1 !=null && key.key1 !=null)
        return this.key1.equals(key.key1);

    return (this.key1.equals(key.key1) && this.key2.equals(key2));
}

public int hashCode(){
    int key1HashCode=key1.hashCode();
    int key2HashCode=key2.hashCode();
    return key1HashCode >> 3 + key2HashCode << 5;
}

}}

Dies hat den Vorteil, dass immer sichergestellt ist, dass Sie auch alle Szenarien von Equals abdecken.

HINWEIS : Ihr Schlüssel1 und Schlüssel2 sollten unveränderlich sein. Nur dann können Sie ein stabiles Schlüsselobjekt erstellen.

Andy
quelle
1

Wir können eine Klasse erstellen, die mehr als einen Schlüssel oder Wert übergibt, und das Objekt dieser Klasse kann als Parameter in der Karte verwendet werden.

import java.io.BufferedReader; 
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

 public class key1 {
    String b;
    String a;
    key1(String a,String b)
    {
        this.a=a;
        this.b=b;
    }
  }

public class read2 {

private static final String FILENAME = "E:/studies/JAVA/ReadFile_Project/nn.txt";

public static void main(String[] args) {

    BufferedReader br = null;
    FileReader fr = null;
    Map<key1,String> map=new HashMap<key1,String>();
    try {

        fr = new FileReader(FILENAME);
        br = new BufferedReader(fr);

        String sCurrentLine;

        br = new BufferedReader(new FileReader(FILENAME));

        while ((sCurrentLine = br.readLine()) != null) {
            String[] s1 = sCurrentLine.split(",");
            key1 k1 = new key1(s1[0],s1[2]);
            map.put(k1,s1[2]);
        }
        for(Map.Entry<key1,String> m:map.entrySet()){  
            key1 key = m.getKey();
            String s3 = m.getValue();
               System.out.println(key.a+","+key.b+" : "+s3);  
              }  
  //            }   
        } catch (IOException e) {

        e.printStackTrace();

    } finally {

        try {

            if (br != null)
                br.close();

            if (fr != null)
                fr.close();

        } catch (IOException ex) {

            ex.printStackTrace();

        }

    }

    }

 }
Vikas Pal
quelle
0

Sie können es über den folgenden Link herunterladen: https://github.com/VVS279/DoubleKeyHashMap/blob/master/src/com/virtualMark/doubleKeyHashMap/DoubleKeyHashMap.java

https://github.com/VVS279/DoubleKeyHashMap

Sie können den doppelten Schlüssel verwenden: Wert-Hashmap,

   DoubleKeyHashMap<Integer, Integer, String> doubleKeyHashMap1 = new 
   DoubleKeyHashMap<Integer, Integer, String>();

   DoubleKeyHashMap<String, String, String> doubleKeyHashMap2 = new 
   DoubleKeyHashMap<String, String, String>();
VISHAL SINGH
quelle