Comment créer un HashMap avec deux clés (paire de clés, valeur) ?

Question

J'ai un tableau d'entiers en 2D. Je veux qu'ils soient placés dans un HashMap. Mais je veux accéder aux éléments du HashMap en fonction de l'index du tableau. Quelque chose comme :

Pour A[2][5], map.get(2,5) qui renvoie une valeur associée à cette clé. Mais comment créer un hashMap avec une paire de clés ? Ou, en général, plusieurs clés : Map<((key1, key2,..,keyN), Value) de manière à ce que je puisse accéder à l'élément en utilisant get(key1,key2,...keyN).

EDIT : 3 ans après avoir posté la question, je veux y ajouter un peu plus de choses

Je suis tombé sur un autre moyen pour NxN matrix .

Indices de tableau, i y j peut être représenté comme un seul key de la manière suivante :

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

Et les indices peuvent être retraités à partir de l'indice key de cette façon :

int i = key / N;
int j = key % N;

Answer 1

Il existe plusieurs options :

2 dimensions

Carte des cartes

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

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

Objet clé d'enveloppe

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

}

Mise en œuvre de equals() y hashCode() est crucial ici. Ensuite, vous utilisez simplement :

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

et :

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

Table de la goyave

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

table.get(2, 5);

Table utilise carte des cartes en dessous.

N dimensions

Notez que le spécial Key est la seule approche qui s'étend à n dimensions. Vous pouvez également considérer :

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

mais c'est terrible du point de vue des performances, ainsi que de la lisibilité et de la correction (il n'y a pas de moyen facile de faire respecter la taille de la liste).

Jetez un coup d'œil à Scala où vous avez des tuples et des case (en remplaçant des classes entières Key avec une seule ligne).

Answer 2

Lorsque vous créez votre propre objet de paire de clés, vous devez faire face à plusieurs choses.

Tout d'abord, vous devez être conscient de la mise en œuvre hashCode() y equals() . Vous devrez le faire.

Deuxièmement, lors de la mise en œuvre hashCode() assurez-vous de bien comprendre son fonctionnement. L'exemple d'utilisateur donné

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

est en fait l'une des pires implémentations que l'on puisse faire. La raison est simple : vous avez beaucoup de hachages égaux ! Et les hashCode() devrait renvoyer des valeurs int qui tendent à être rares, uniques dans le meilleur des cas. Utilisez quelque chose comme ceci :

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

Cette méthode est rapide et renvoie des hachages uniques pour les clés comprises entre -2^16 et 2^16-1 (-65536 à 65535). Cela convient dans presque tous les cas. Il est très rare que vous soyez en dehors de cette limite.

Troisièmement, lors de la mise en œuvre equals() Sachez également à quoi il sert et faites attention à la façon dont vous créez vos clés, puisqu'il s'agit d'objets. Souvent vous faites des déclarations if inutiles car vous aurez toujours le même résultat.

Si vous créez des clés comme ceci : map.put(new Key(x,y),V); vous ne comparerez jamais les références de vos clés. Parce que chaque fois que vous voulez accéder à la carte, vous ferez quelque chose comme map.get(new Key(x,y)); . Par conséquent, votre equals() n'a pas besoin d'une déclaration comme if (this == obj) . Il jamais occultation.

Au lieu de if (getClass() != obj.getClass()) dans votre equals() meilleure utilisation if (!(obj instanceof this)) . Il sera valable même pour les sous-classes.

Donc la seule chose que vous avez besoin de comparer est en fait X et Y. Donc le meilleur equals() dans ce cas, la mise en œuvre serait :

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

Donc, à la fin, votre classe de clé est comme ceci :

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

}

Vous pouvez donner vos indices de dimension X y Y un niveau d'accès public, du fait qu'ils sont définitifs et ne contiennent pas d'informations sensibles. Je ne suis pas sûr à 100% si private Le niveau d'accès fonctionne correctement dans tout lors de l'introduction de la Object à un Key .

Si vous vous interrogez sur les finales, je déclare comme finale tout ce qui a une valeur fixée lors de l'instanciation et qui ne change jamais - et qui est donc une constante d'objet.

Answer 3

Vous ne pouvez pas avoir une carte de hachage avec plusieurs clés, mais vous pouvez avoir un objet qui prend plusieurs paramètres comme clé.

Créez un objet appelé Index qui prend une valeur x et 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;
    }
}

Alors, demandez à votre HashMap<Index, Value> pour obtenir votre résultat. :)

Answer 4

Mis en œuvre dans les collections communes MultiKeyMap

Answer 5

Deux possibilités. Soit vous utilisez une clé combinée :

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

Ou une carte de carte :

Map<Integer, Map<Integer, Integer>> myMap;