什么是O(1)搜索内存有效的数据结构来存储成对的整数？

Question

请考虑以下接口：

public interface CoordinateSet {
    boolean contains(int x, int y);
    default boolean contains(Coordinate coord) {
        return contains(coord.x, coord.y);
    }
}

我们有很多方法可以实现这样的接口。计算效率最高的是由数组备份的实现：

public class ArrayCoordinateSet implements CoordinateSet {
    private final boolean[][] coords = new boolean[SIZE][SIZE];
    // ...
    @Override
    public boolean contains(int x, int y) {
        return coords[x][y];
    }
    public void add(int x,  int y) {
        coords[x][y] = true;
    }
    // ...

}

但是，如果size很大，例如1000，并且在1000×10000矩形的四个角度中，只有例如4个坐标属于集合，这意味着单元格空间的绝对大部分被false值所消耗。对于这样稀疏的CoordinateSet，我们最好使用基于hashset的CoordinateSet:

public final class Coordinate {
    public final int x;
    public final int y;
    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
    // .equals() and hashCode()
}
public class HashBasedCoordinateSet implements CoordinateSet {
    private final Set<Coordinate> coords = new HashSet<>();
    @Override
    public boolean contains(int x, int y) {
        return coords.contains(new Coordinate(x, y));
    }
    @Override
    public boolean contains(Coordinate coord) {
         return coords.contains(coord);
    }
    public void add(Coordinate coord) {
        coords.add(coord);
    }
}

但是，对于HashBasedCoordinateSet我们有这样一个问题：

for (int x=0; x<1000; x++) {
  for (int y=0; y<1000; y++) {
    hashBasedCoordinateSet.contains(x, y);
  }
}

当我们具有值x和y并且希望检查HashBasedCoordinateSet.contains(x,y)时，那么这将需要在每次方法调用时创建一个新对象（由于我们总是需要在HashSet中搜索对象，仅有对象的数据是不够的）。这将是对CPU时间的真正浪费（它需要创建所有的coordine对象，然后抓取收集它们，因为似乎无法对这些代码执行escape-analysis优化）。

所以最后，我的问题是：

1. 具有O(1)包含（int x,int y)操作；
2. 有效地使用空间（与基于数组的实现不同）；
3. 在包含（int x,int y）期间不必创建额外的对象？

Answer 1

在Java中，long的大小是整数的两倍，因此可以在一个long中存储两个int。那这样怎么样？

public class CoordinateSet {
    private HashSet<Long> coordinates = new HashSet<>();

    public void add(int x, int y) {
        coordinates.add((x | (long) y << 32));
    }

    public boolean contains(int x, int y) {
        return coordinates.contains((x | (long) y << 32));
    }
}

我非常肯定contains方法上的long存储在堆栈上。