java - 单线程 Contains(Point(x,y)) 功能最快的 Java 集合是什么？

Question

在我的应用程序中，我需要检查二维坐标 (x,y) 的集合以查看给定坐标是否在集合中，它需要尽可能快并且只能从一个线程访问。 (用于碰撞检查)

有人能给我一个正确的方向吗？

Answer 1

我能想到的绝对最快的方法是维护这些点的二维矩阵:

//just once
int[][] occurrences = new int[X_MAX][Y_MAX];
for (Point p : points ) {
    occurrences[p.x][p.y]++;
}

//sometime later
if ( occurrences[x][y] != 0 ) {
    //contains Point(x, y)
}

如果你不关心有多少，只要一个boolean矩阵会起作用。显然，如果矩阵只创建一次，并且可能随着点添加到集合中而更新，这只会很快。

简而言之，基本的 Collections 对此并不完美(尽管 HashSet 会很接近)。

编辑

这可以很容易地改编为 Set<Point>如果您找不到已经为您完成此操作的图书馆。像这样:

public class PointSet implements Set<Point> {
    private final boolean[][] data; 
    public PointSet(int xSize, int ySize) {
        data = new boolean[xSize][ySize];
    }

    @Override
    public boolean add(Point e) {
         boolean hadIt = data[e.x][e.y];
         data[e.x][e.y] = true;
         return hadIt;
    }

    @Override
    public boolean contains(Object o) {
        Point p = (Point) o;
        return data[p.x][p.y];
    }

    //...other methods of Set<Point>...
}