Jak stworzyć HashMap z dwoma kluczami (para kluczy, wartość)?

118

Mam tablicę liczb całkowitych 2D. Chcę, aby zostały umieszczone w HashMap. Ale chcę uzyskać dostęp do elementów z HashMap w oparciu o indeks tablicy. Coś jak:

Dla A [2] [5], map.get(2,5)która zwraca wartość skojarzoną z tym kluczem. Ale jak utworzyć mapę mieszania za pomocą pary kluczy? Lub ogólnie wiele kluczy: Map<((key1, key2,..,keyN), Value)w taki sposób, że mogę uzyskać dostęp do elementu za pomocą get (klucz1, klucz2, ... kluczN).

EDYCJA: 3 lata po opublikowaniu pytania chcę dodać do niego trochę więcej

Znalazłem inny sposób NxN matrix.

Indeksy tablicowe ii jmożna je przedstawić jako pojedynczy keyw następujący sposób:

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

A indeksy można pobrać z tego keyw ten sposób:

int i = key / N;
int j = key % N;
Crocode
źródło
Prostym rozwiązaniem jest mapowanie jednego klucza w innym skrócie.
Mihai8,
1
Proszę nie odpowiadać na pytanie w pytaniu. Twoja zmiana jest interesująca, więc możesz ją opublikować jako odpowiedź.
Ole VV
@Crocode wow! matematyka stojąca za odpowiedzią w Edycji błyszczy. Zastanawiam się tylko, czy działa to ogólnie dla dowolnych dwóch liczb całkowitych i i j.
likejudo
@Crocode czy i i j będą się powtarzać, jeśli są wielokrotnościami N?
likejudo

Odpowiedzi:

190

Istnieje kilka opcji:

2 wymiary

Mapa map

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

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

Obiekt klucza opakowania

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

}

Wdrażanie equals()i hashCode()jest tutaj kluczowe. Następnie po prostu użyj:

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

i:

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

Table z Guawy

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

table.get(2, 5);

Tableużywa mapy map poniżej.

Wymiary N.

Zauważ, że Keyklasa specjalna jest jedynym podejściem, które skaluje się do n-wymiarów. Możesz również rozważyć:

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

ale to straszne z punktu widzenia wydajności, a także czytelności i poprawności (nie ma łatwego sposobu na wymuszenie rozmiaru listy).

Może spójrz na Scala, gdzie masz krotki i caseklasy (zastępując całą Keyklasę jedną linijką).

Tomasz Nurkiewicz
źródło
3
Cześć, inni mają x'lub dwie wartości podczas wykonywania hashCode. Dlaczego używasz 31? Myślałem, że ma to coś wspólnego z 32-bitową liczbą całkowitą, ale kiedy o tym myślę, nie ma to sensu, ponieważ x = 1 i y = 0 wciąż mapuje ten sam hashcode co x = 0 i y = 31
pete
1
@pete Joshua Bloch, w Effective Java ch 3. s 9., zaleca: „1. Przechowuj stałą niezerową wartość, powiedzmy 17, w zmiennej int o nazwie result ...”, co działa lepiej pod względem kolizji, jeśli liczba pierwsza. Zobacz też: stackoverflow.com/questions/3613102/…
fncomp
2
Dlaczego nie użyć obiektu klucza Wrapper Map.Entry<K, V>jako klucza?
Roland,
1
O co chodzi Map<Pair<Key1, Key2>, Value>?
Joaquin Iurchuk
1
zauważ, że hashCode()można to również zaimplementować z pojedynczą linią jakoObjects.hash(x,y)
xdavidliu
23

Kiedy tworzysz swój własny obiekt pary kluczy, powinieneś zmierzyć się z kilkoma rzeczami.

Po pierwsze, powinieneś być świadomy implementacji hashCode()i equals(). Będziesz musiał to zrobić.

Po drugie, podczas wdrażania hashCode()upewnij się, że rozumiesz, jak to działa. Podany przykład użytkownika

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

jest właściwie jedną z najgorszych implementacji, jakie możesz zrobić. Powód jest prosty: masz dużo równych haszów! A hashCode()powinien zwrócić wartości int, które mają tendencję do być rzadki, wyjątkowy w najlepszym. Użyj czegoś takiego:

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

Jest to szybkie i zwraca unikalne skróty dla kluczy od -2 ^ 16 do 2 ^ 16-1 (od -65536 do 65535). Pasuje to prawie do każdego przypadku. Bardzo rzadko jesteś poza tym zakresem.

Po trzecie, podczas implementacji equals()wiedz również, do czego służy i bądź świadomy tego, jak tworzysz klucze, ponieważ są one obiektami. Często robisz to niepotrzebnie, jeśli stwierdzenia powodują, że zawsze będziesz miał ten sam rezultat.

Jeśli utworzysz klucze w ten sposób: map.put(new Key(x,y),V);nigdy nie będziesz porównywać referencji swoich kluczy. Ponieważ za każdym razem, gdy chcesz uzyskać dostęp do mapy, zrobisz coś takiego map.get(new Key(x,y));. Dlatego equals()nie potrzebujesz takiego oświadczenia if (this == obj). To się nigdy nie wydarzy.

Zamiast if (getClass() != obj.getClass())w equals()lepszym użyciu if (!(obj instanceof this)). Będzie obowiązywać nawet dla podklas.

Więc jedyne, co musisz porównać, to w rzeczywistości X i Y. Więc najlepsza equals()implementacja w tym przypadku to:

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

Ostatecznie twoja kluczowa klasa wygląda tak:

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

}

Możesz podać swoje indeksy wymiarów Xi Ypoziom dostępu publicznego, ponieważ są one ostateczne i nie zawierają poufnych informacji. Nie jestem w 100% pewien, czy privatepoziom dostępu działa poprawnie w każdym przypadku podczas przesyłania Objectdo pliku Key.

Jeśli zastanawiasz się nad finałami, deklaruję wszystko jako ostateczne, którego wartość jest ustawiona na instancji i nigdy się nie zmienia - i dlatego jest stałą obiektową.

chrixle
źródło
7

Nie możesz mieć mapy skrótów z wieloma kluczami, ale możesz mieć obiekt, który przyjmuje wiele parametrów jako klucz.

Utwórz obiekt o nazwie Index, który przyjmuje wartości x i y.

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

Następnie miej HashMap<Index, Value>swój wynik. :)

Ćwiek
źródło
4
Musisz zastąpić hashCodei equals.
Tom Hawtin - tackline
4
implementacja hashCode nie rozróżnia między (2,1) a (1,2)
user1947415
1
To jest zderzenie. Hashcode nie musi gwarantować innej wartości dla każdego innego obiektu. @ user1947415
Ajak6
6

Zaimplementowane we wspólnych kolekcjach MultiKeyMap

Mikrofon
źródło
@Wilson Naprawiłem teraz link, czekając na recenzję
computingfreak
Wydaje się, że @computingfreak pojawił się pozytywny widok. Hurra! NB to najlepsza odpowiedź IMHO. Chyba że masz ochotę spędzać godziny rywalizując z ekspertami inżynierów Apache o bardzo przydatne (jak zawsze), ale ostatecznie przyziemne funkcje.
mike gryzoń
4

Dwie możliwości. Albo użyj łączonego klucza:

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

Lub mapa mapy:

Map<Integer, Map<Integer, Integer>> myMap;
Cyrille Ka
źródło
2
Używaj mapy map tylko wtedy, gdy nie zależy ci na wydajności lub wykorzystaniu pamięci (tj. Mapa jest mała) lub istnieje wiele kluczy z tym samym pierwszym indeksem - ponieważ to rozwiązanie oznacza płacenie narzutu za obiekt HashMap za każdy unikalny pierwszy indeks.
BeeOnRope
1
Aby poprawić tę odpowiedź, oto informacje o zastępowaniu hashCodei equalsmetodach.
Pshemo
2

Użyj Pairjako kluczy do HashMap. JDK nie ma pary, ale możesz skorzystać z biblioteki innej firmy, takiej jak http://commons.apache.org/lang, lub napisać własny typ pary.

MrSmith42
źródło
1

Utwórz klasę wartości, która będzie reprezentować Twój klucz złożony, na przykład:

class Index2D {
  int first, second;

  // overrides equals and hashCode properly here
}

dbając o to, aby zastąpić equals()i hashCode()poprawnie. Jeśli wydaje się, że to dużo pracy, możesz rozważyć kilka gotowych ogólnych kontenerów, takich jak Pairmiędzy innymi dostarczone przez apache commons.

Jest tu również wiele podobnych pytań , z innymi pomysłami, takimi jak użycie tabeli guawy , chociaż pozwala na to, aby klucze miały różne typy, co może być przesadą (w przypadku użycia pamięci i złożoności) w twoim przypadku, ponieważ rozumiem, że oba klucze są liczbami całkowitymi.

BeeOnRope
źródło
1

Jeśli są to dwie liczby całkowite, możesz wypróbować szybką i nieprzyjemną sztuczkę: Map<String, ?>używając klucza as i+"#"+j.

Jeśli klucz i+"#"+jjest taki sam jak j+"#"+itry min(i,j)+"#"+max(i,j).

arutaku
źródło
2
Naprawdę zły pomysł. Po pierwsze, jest po prostu źle. Po drugie, ta technika zostanie skopiowana dla innych typów, w których inny klucz może zostać przypisany do tego samego Stringz zabawnymi konsekwencjami.
Tom Hawtin - tackline
Wydaje mi się, że i#j = j#iprzy i == jtakim użyciu min/maxsztuczki nie da się.
Matthieu
1
@Matthieu jaka jest różnica między 5#5i 5#5zamienione?
enrey
@enrey None. To właśnie wskazywałem. To naprawdę zależy od wiedzy, jaką masz na temat kluczy.
Matthieu
@Matthieu aha Rozumiem, co masz na myśli. Myślę, że @arutaku miało na myśli to, że gdy chcesz 5#3mieć taki sam hash 3#5, wtedy używasz min / max, aby wymusić 3#5w tej kolejności.
enrey
1

Możesz również użyć do tego implementacji stołu z guawy .

Tabela reprezentuje specjalną mapę, na której można określić dwa klucze w połączeniu w celu odniesienia się do jednej wartości. Jest to podobne do tworzenia mapy map.

//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
źródło
1

Możesz stworzyć swój kluczowy obiekt mniej więcej tak:

public class 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;
}

}

Zaletą takiego rozwiązania jest to, że zawsze upewni się, że uwzględniasz również wszystkie scenariusze Równości.

UWAGA : Twoje key1 i key2 powinny być niezmienne. Tylko wtedy będziesz w stanie zbudować stabilny kluczowy Obiekt.

Andy
źródło
1

możemy stworzyć klasę przekazującą więcej niż jeden klucz lub wartość, a obiekt tej klasy może być użyty jako parametr w mapie.

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
źródło
0

Możesz go pobrać z poniższego linku: https://github.com/VVS279/DoubleKeyHashMap/blob/master/src/com/virtualMark/doubleKeyHashMap/DoubleKeyHashMap.java

https://github.com/VVS279/DoubleKeyHashMap

Możesz użyć podwójnego klucza: wartość hashmap,

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

   DoubleKeyHashMap<String, String, String> doubleKeyHashMap2 = new 
   DoubleKeyHashMap<String, String, String>();
VISHAL SINGH
źródło