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

Question

我有两个号码,我想将它们一起用作一个键Map.目前,我正在连接他们的字符串表示.例如,假设密钥号是4和12.我使用:

String key = 4 + "," + 12;

地图声明为Map<String, Object>.

我觉得这太糟了!我喜欢用别的东西String作为钥匙!我想要以最快的方式创建这些密钥.

谁有个好主意？

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答案.

Answer 2

您应该使用java.awt.Dimension作为密钥.

尺寸键=新尺寸(4,12);

Dimension有一个非常好的hashCode()方法,它为每对正整数产生不同的hashCode,因此(4,12)和(12,4)的hashCodes是不同的.因此,这些可以快速实例化并生成非常好的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的顺序执行hashCodes,您将看到该模式.

这是生成此hashCode的代码:

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方法,但是你将自己限制为不会溢出的正整数,你可以添加一个非常快的:

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,您可以在任何不可变类中快速编写hashCodes.)

如果你不能忍受这些限制,你只需要保存参数.

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方法,可以正常工作.此方法将从两个短值生成散列键.限制是您的输入需要是正值短值.这保证不会溢出,并且通过将中间和转换为long,它具有比前一方法更宽的范围:它适用于所有正的短值.

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

Answer 3

如果您使用对象解决方案,请确保您的密钥对象是不可变的.

否则,如果某人改变了该值,它不仅不再等于其他明显相同的值,而且存储在地图中的哈希码将不再与该hashCode()方法返回的哈希码相匹配.那时你基本上是SOL.

例如,使用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

Answer 4

你可以像这样存储两个整数,

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