如何创建一个具有两个键（Key-Pair, Value）的HashMap？

Question

我有一个整数的二维数组。我想将它们放入HashMap中。但是我想要根据数组索引从HashMap中访问元素。例如：

对于A [2] [5]，map.get（2,5），返回与该键相关联的值。但是如何创建带有一对键的HashMap？或者说，如何用多个键创建 Map<((key1, key2,..,keyN), Value)，以便通过使用get(key1,key2,...keyN)来访问元素。

编辑：发布问题3年后，我想再补充一些内容

我遇到了另一种处理NxN矩阵的方法。

可以将数组索引和表示为单个key，如下所示：

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

下面是从key中检索到索引的方法：

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

- Crocode

---

一个简单的解决方案是将一个键映射到另一个哈希表中。 - Mihai8

请不要在问题中回答问题。您的编辑很有趣，可以将其作为答案发布。 - Ole V.V.

@Crocode哇！在编辑中得出答案背后的数学原理令人兴奋。只是想知道它是否适用于任何两个整数i和j。 - likejudo

@Crocode 如果i和j是N的倍数，它们会循环吗？ - likejudo

就像这样简单： map.put(Map.entry(i, j), a[i][j]) - Ashwin Prabhu

Answer 1

有几个选项：

2维度

地图映射

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

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

包装密钥对象

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

}

在这里实现equals()和hashCode()是至关重要的。然后你只需使用：

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

而且：

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

Table from Guava

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

table.get(2, 5);

Table使用映射嵌套实现。

N维

请注意，特殊的Key类是唯一适用于n维度的方法。您还可以考虑以下方式：

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

但从性能、可读性和正确性角度来看，这是糟糕的（没有简单的方法来强制执行列表大小）。

也许可以看一下 Scala ，在那里您可以使用元组和 case 类（用一行代码替换整个 Key 类）。

- Tomasz Nurkiewicz

---

你好，当执行hashCode时，其他人使用异或（x'or）两个值。你为什么使用31？我认为这与32位整数有关，但是仔细一想就不合理了，因为当x = 1且y = 0时映射到的哈希码与x = 0且y = 31相同。 - pete

@pete Joshua Bloch, 在 Effective Java 的第三章第九节中建议：“1. 将一些常量非零值存储在名为 result 的 int 变量中，例如 17...”，如果这是一个质数，在冲突方面会更好。参见：https://dev59.com/y3A65IYBdhLWcg3w1SNC - fncomp

为什么不使用 Map.Entry<K, V> 作为键，而不是使用包装器键对象？ - Roland

Map<Pair<Key1, Key2>, Value> 这个怎么样？ - Joaquin Iurchuk

请注意，hashCode()也可以用一行代码实现，如Objects.hash(x,y)。 - xdavidliu

Answer 2

当您创建自己的密钥对对象时，您应该注意几件事情。

首先，您应该注意实现 hashCode() 和 equals()。 您需要这样做。

其次，在实现 hashCode() 时，请确保您了解它的工作原理。 给出了用户示例

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

实际上，这是你可以做的最糟糕的实现之一。原因很简单：你有很多相等的哈希值！而hashCode()应该返回倾向于稀有、最好是唯一的int值。使用类似这样的东西：

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

这是一种快速且返回介于-2^16和2^16-1（-65536到65535）之间的唯一哈希键的方法。几乎适用于所有情况。很少会超出这个范围。

第三，当实现equals()时，要知道它的用途，并注意如何创建键，因为它们是对象。通常您会做不必要的if语句，因为您始终会得到相同的结果。

如果您像这样创建键：map.put(new Key(x,y),V);，则永远不会比较您的键的引用。因为每次您要访问地图时，都会执行类似于map.get(new Key(x,y));的操作。因此，您的equals()不需要像if (this == obj)这样的语句。它将永远不会出现。

在您的equals()中，与其使用if(getClass() != obj.getClass())，不如使用if(!(obj instanceof this))。即使对于子类也是有效的。

所以您唯一需要比较的事情实际上就是X和Y。因此，在这种情况下最好的equals()实现如下：

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

由于维度索引 X 和 Y 是常量且不包含敏感信息，因此您可以将它们的公共访问级别设置为public。我不能100%确定在将 Object 强制转换为 Key 时，private 访问级别是否在任何情况下都能正常工作。

如果您对这些常量有疑问，我会将任何值在实例化时设置并且永远不会更改的内容声明为常量 - 因此是对象常量。

- chrixle

Answer 3

你不能用多个键来创建一个哈希图，但是你可以创建一个接受多个参数作为键的对象。

创建一个名为 Index 的对象，该对象接受 x 和 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;
    }
}

然后使用您的HashMap<Index, Value>获取结果。 :)

- Brad

---

дљ†йЬАи¶БйЗНеЖЩ hashCode еТМ equals жЦєж≥ХгАВ - Tom Hawtin - tackline

hashCode的实现没有区分(2,1)和(1,2)。 - user1947415

这是一次碰撞。Hashcode不需要保证每个不同对象的值都不同。@user1947415 - Ajak6

Answer 4

在common-collections中实现多键映射MultiKeyMap

- Mike

---

@Wilson 我已经修复了链接，现在正在等待同行审查。 - computingfreak

@computingfreak 看起来有一个赞同的观点。万岁！顺便提一下，这是我认为最好的答案。除非你想花几个小时与专业的Apache工程师竞争一些非常有用（像往常一样）但最终却平凡无奇的功能。 - mike rodent

Answer 5

Java 7+ 包含一个新的 Map.Entry<K,V> 类，您可以将其用作地图的键（或集合的条目）。Java 9+ 还包含一个 Map.entry(K k, V v) 方法，以轻松创建新的 Map.Entry 对象。

用法：

Map<Map.Entry<Integer,Integer>, Integer> map = new HashMap<>();
map.put(Map.entry(1, 2), 0);

在javafx.util中也有Pair<K, V>

Map<Pair<Integer,Integer>, Integer> map = new HashMap<>();
map.put(new Pair(1, 2), 0);

- Rajat Shah

Answer 6

有两种可能性。要么使用组合键：

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

或者是一个Map的Map：

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

- Cyrille Ka

---

只有在您不关心性能或内存使用（即，映射很小），或者有许多具有相同第一个索引的键时才使用嵌套的映射 - 因为此解决方案意味着为每个唯一的第一个索引支付HashMap对象的开销。 - BeeOnRope

为了改进这个答案，这里提供了有关覆盖hashCode和equals方法的信息。 - Pshemo

Answer 7

在HashMap中使用Pair作为键。JDK没有提供Pair类型，但您可以使用第三方库，如http://commons.apache.org/lang，或编写自己的Pair类型。

- MrSmith42

Answer 8

创建一个值类来表示您的复合键，例如：

class Index2D {
  int first, second;

  // overrides equals and hashCode properly here
}

请注意正确覆盖 equals() 和 hashCode() 方法。如果这似乎是很多工作，您可以考虑使用一些现成的通用容器，例如 Apache Commons 提供的 Pair 等。

这里还有许多类似的问题，提供其他想法，比如使用 Guava 的Table，虽然允许键具有不同的类型，但在您的情况下可能会过度（在内存使用和复杂性方面）。我理解您的键都是整数。

- BeeOnRope

Answer 9

如果它们是两个整数，你可以尝试一个快速而简单的技巧：Map<String, ?>，使用i+"#"+j作为键。 如果键i+"#"+j与j+"#"+i相同，则尝试使用min(i,j)+"#"+max(i,j)。

- arutaku

---

真的不是个好主意。首先，它就很糟糕。其次，这种技术会被复制到其他类型中，其中不同的键可能会被映射到相同的“String”，从而导致令人啼笑皆非的后果。 - Tom Hawtin - tackline

@Matthieu，5#5和5#5反转有什么区别？ - enrey

@enrey 没有。这就是我指出的。这真的取决于你对键盘的了解程度。 - Matthieu

@Matthieu 啊哈，我知道你的意思。我认为 @arutaku 的意思是当你希望 5#3 和 3#5 具有相同的哈希值时，你可以使用 min/max 来强制按照 3#5 这个顺序。 - enrey

@enrey 没错。除非顺序很重要。再次强调，关键是你对自己的键拥有的知识（顺序，重复等等）。 - Matthieu

Answer 10

您可以像这样创建您的密钥对象：

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

}

这样做的好处在于：它总是确保您覆盖了Equals的所有情况。 注意：您的key1和key2应该是不可变的。只有这样，您才能构建一个稳定的键对象。

- Andy