如何使用两个数字作为Map键

Question

我有两个数字，想要将它们一起作为Map的键使用。目前，我正在连接它们的字符串表示。例如，假设关键数字是4和12。 我使用以下代码：

String key = 4 + "," + 12;

这个 map 被声明为 Map<String, Object>。

我认为这样做很糟糕！我想使用除了 String 以外的其他内容作为键！我要找到创建这些键最快的方法。

有谁有好主意吗？

- Koerr

---

我认为逗号分隔的字符串是一个好主意。我一直使用这种方法。 - mob

Answer 1

创建一个对象来保存这两个数字，并将其用作键。例如：

class Coordinates {

  private int x;
  private int y;

  public Coordinates(int x, int y) {
     ...
  }

  // getters

  // equals and hashcode using x and y
}

Map<Coordinates, Location> locations = new HashMap<Coordinates, Location>();

如果你更喜欢用数学方法，可以查看这个StackOverflow答案。

- SingleShot

---

好的 - 现在很明显这是一个家庭作业问题。 正确的 解决方案是使用一个类。该类中 hashcode() 方法的实现是性能发挥作用的地方。 - Kevin Day

如果你将其用作HashMap键，那么你真的想让x和y是可变的吗？ - David Moles

另外，如果您需要从您的 Map 查找内容，而不仅仅是迭代它，您应该重写 hashCode() 和 equals() 方法。这将允许您：A在将来创建坐标对象并从已填充的 Map 中检索内容。否则，即使您使用与 Map 中用作键的 Coordinates 具有相同的 x 和 y 创建 Coordinates ，也不会返回值。B 这将提高从您的 Map 中查找内容的速度。 - Markos Fragkakis

但是，我想问题仍然是如何实现hashCode()方法呢？ - user1947415

这个解决方案的复杂度是theta(1)吗？我猜Java中的Map就像C++中的Map一样，查找元素的复杂度是theta(logn)。 - Jerry Zhao

Answer 2

你应该使用java.awt.Dimension作为你的键。

Dimension key = new Dimension(4, 12);

Dimension有一个非常好的hashCode()方法，为每对正整数生成不同的hashCode，因此(4, 12)和(12, 4)的hashCodes是不同的。因此这些对象实例化快且可用于很好的哈希码。

我希望他们将该类设置为不可变的，但是你可以自己创建一个模仿Dimension的不可变类。

以下是一个表格，显示不同宽度和高度的hashCode：

     0   1   2   3   4  <-- width
  +--------------------
0 |  0   2   5   9  14
1 |  1   4   8  13
2 |  3   7  12
3 |  6  11
4 | 10

^
|
height

如果您按照从0到14的顺序跟随哈希码，就会看到这个模式。

以下是生成此哈希码的代码：

public int hashCode() {
    int sum = width + height;
    return sum * (sum + 1)/2 + width;
}

你可能会在最后一行中认出三角数的公式。这就是为什么表格的第一列包含所有的三角数。

为了提高速度，你应该在构造函数中计算hashCode。因此，你的整个类可能看起来像这样:

public class PairHash {
  private final int hash;
  public PairHash(int a, int b) {
    int sum = a+b;
    hash = sum * (sum+1)/2 + a;
  }
  public int hashCode() { return hash; }
}

当然，如果您可能需要一个equals方法，但限制自己在不会溢出的正整数范围内，您可以添加一个非常快的equals方法：

public class PairHash {
  // PAIR_LIMIT is 23170
  // Keeping the inputs below this level prevents overflow, and guarantees
  // the hash will be unique for each pair of positive integers. This
  // lets you use the hashCode in the equals method.
  public static final int PAIR_LIMIT = (int) (Math.sqrt(Integer.MAX_VALUE))/2;
  private final int hash;

  public PairHash(int a, int b) {
    assert a >= 0;
    assert b >= 0;
    assert a < PAIR_LIMIT;
    assert b < PAIR_LIMIT;
    int sum = a + b;
    hash = sum * (sum + 1) / 2 + a;
  }

  public int hashCode() { return hash; }

  public boolean equals(Object other) {
    if (other instanceof PairHash){
      return hash == ((PairHash) other).hash;
    }
    return false;
  }
}

我们限制这个方法只适用于正数，因为负数会产生一些重复的哈希码。但是在这个限制下，这些代码是可以编写最快的hashCode()和equals()方法的。（当然，在任何不可变类中都可以通过在构造函数中计算hashCode来编写同样快的hashCode。）

如果您无法接受这些限制，您只需要保存参数即可。

public class PairHash {
  private final int a, b, hash;
  public PairHash(int a, int b) {
    this.a = a;
    this.b = b;
    int sum = a+b;
    hash = sum * (sum+1)/2 + a;
  }
  public int hashCode() { return hash; }
  public boolean equals(Object other) {
    if (other instanceof PairHash) {
      PairHash otherPair = (PairHash)other;
      return a == otherPair.a && b == otherPair.b;
    }
    return false;
}

但这是重点。你根本不需要这个类。由于该公式为每对数字提供唯一的整数，因此您可以将该整数用作映射键。Integer类具有自己的快速equals()和hashCode()方法，这些方法将正常工作。此方法将从两个short值生成哈希键。限制是您的输入需要是正的short值。这保证不会溢出，并且通过将中间总和转换为长整型，它的范围比之前的方法更广：它适用于所有正的short值。

static int hashKeyFromPair(short a, short b) {
  assert a >= 0;
  assert b >= 0;
  long sum = (long) a + (long) b;
  return (int) (sum * (sum + 1) / 2) + a;
}

- MiguelMunoz

---

对于好奇的人，本答案中使用的函数称为Cantor配对函数。 - qxz

Answer 3

如果您采用对象解决方案，请确保您的关键对象是不可变的，否则，如果有人更改了该值，它将不再等于其他明显相同的值，并且存储在映射中的哈希码将不再与hashCode()方法返回的哈希码相匹配。此时你基本上就遇到了麻烦。

例如，使用java.awt.Point -- 看起来就像是您想要的东西--以下内容：

  public static void main(String[] args) {
    Map<Point, Object> map = new HashMap<Point, Object>();

    Point key = new Point(1, 3);
    Object val = new Object();

    map.put(key, val);

    System.out.println(map.containsKey(key));
    System.out.println(map.containsKey(new Point(1, 3)));

    // equivalent to setLeft() / setRight() in ZZCoder's solution,
    // or setX() / setY() in SingleShot's
    key.setLocation(2, 4);

    System.out.println(map.containsKey(key));
    System.out.println(map.containsKey(new Point(2, 4)));
    System.out.println(map.containsKey(new Point(1, 3)));
  }

打印：

true
true
false
false
false

- David Moles

Answer 4

您可以像这样在 long 类型中存储两个整数：

   long n = (l << 32) | (r & 0XFFFFFFFFL);

您可以使用以下的Pair<Integer, Integer>类，

public class Pair<L, R> {

    private L l;
    private R r;

    public Pair() {
    }

    public Pair(L l, R r) {
        this.l = l;
        this.r = r;
    }

    public L getLeft() {
        return l;
    }

    public R getRight() {
        return r;
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Pair)) {
            return false;
        }
        Pair obj = (Pair) o;
        return l.equals(obj.l) && r.equals(obj.r);
    }

    @Override
    public int hashCode() {
        return l.hashCode() ^ r.hashCode();
    }
} 

- ZZ Coder

---

我会为这个巧妙的int -> long解决方案点赞，但我也会因为使“Pair”可变而对其进行反对。 - David Moles

你不能将原始类型用作泛型参数。 - Tadeusz Kopec for Ukraine

不错的技巧，但是一旦它们被存储在一个长整型中，我就很难从中提取这两个整数。你可以使用哪些位运算来提取这两个整数（r和l）？ - Eternal Rubyist

hashCode 对于 (1,2) 和 (2,1) 是相同的。 - user1947415

Answer 5

一种切实可行的回答是：

hashCode = a + b * 17;

...其中a、b和hashCode都是整数。17只是一个任意的质数。你的哈希值不会是唯一的，但没关系。这种东西在Java标准库中随处可见。

- cbare

Answer 6

另一种方法是使用嵌套的映射：

Map<Integer,Map<Integer,Object>>

在这里，您不需要创建键的额外开销。但是，您需要更多的开销来正确地创建和检索条目，并且您始终需要映射访问才能找到所需的对象。

- Wolfgang

Answer 7

为什么编写所有额外代码以创建一个不需要的完整类，比使用简单的字符串好？计算该类的实例哈希码是否比字符串快得多？我认为并不是。

除非您在极度有限的计算能力环境中运行，否则制作和散列字符串的开销不应该明显大于实例化自定义类的开销。

我想最快的方法是按照 ZZ Coder 的建议将 int 打包成单个 Long，但无论如何，我不指望速度的增益会很大。

- MAK

Answer 8

你需要编写正确的equals和hashcode方法，否则会产生一些错误。

- Peter Lee